van_der_corput


van_der_corput, a C++ code which computes the van der Corput Quasi Monte Carlo (QMC) sequence, using a simple interface.

The van der Corput sequence generates a sequence of points in [0,1] which never repeats. For positive index I, the elements of the van der Corput sequence are strictly between 0 and 1.

The I-th element of the van der Corput sequence is computed by writing I in the base B (usually 2) and then reflecting its digits about the decimal point. For example, if we start with I = 11, its binary expansion is 1011, and so its reflected binary expansion is 0.1101 which is 1/2+1/4+1/16=0.8125.

The generation is quite simple. Given an index I, the expansion of I in base B is generated. Then, essentially, the result R is generated by writing a decimal point followed by the digits of the expansion of I, in reverse order. This decimal value is actually still in base B, so it must be properly interpreted to generate a usable value.

Here is an example in base 2:
I (decimal) I (binary) R (binary) R (decimal)
00.00.0
11.10.5
210.010.25
311.110.75
4100.0010.125
5101.1010.625
6110.0110.375
7111.1110.875
81000.00010.0625

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

van_der_corput is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

BOX_BEHNKEN, a C++ code which computes a Box-Behnken design, that is, a set of arguments to sample the behavior of a function of multiple parameters;

CVT, a C++ code which computes points in a Centroidal Voronoi Tessellation.

FAURE, a C++ code which computes Faure sequences.

HALTON, a C++ code which computes elements of a Halton Quasi Monte Carlo (QMC) sequence, using a simple interface.

HAMMERSLEY, a C++ code which computes elements of a Hammersley Quasi Monte Carlo (QMC) sequence, using a simple interface.

IHS, a C++ code which computes improved Latin Hypercube datasets.

LATIN_CENTER, a C++ code which computes Latin square data choosing the center value.

LATIN_EDGE, a C++ code which computes Latin square data choosing the edge value.

LATIN_RANDOM, a C++ code which computes Latin square data choosing a random value in the square.

NIEDERREITER2, a C++ code which computes Niederreiter sequences with base 2.

NORMAL, a C++ code which computes a sequence of pseudorandom normally distributed values.

SOBOL, a C++ code which computes Sobol sequences.

UNIFORM, a C++ code which computes uniform random values.

van_der_corput_test

Reference:

  1. J G van der Corput,
    Verteilungsfunktionen I & II,
    Nederl. Akad. Wetensch. Proc.,
    Volume 38, 1935, pages 813-820, pages 1058-1066.

Source Code:


Last revised on 09 April 2020.