VAN_DER_CORPUT The van der Corput Quasi Monte Carlo (QMC) sequence

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

A more sophisticated library is available in VAN_DER_CORPUT_ADVANCED, but I find this simple version to be preferable for everyday use!

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

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++ library 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++ library which computes points in a Centroidal Voronoi Tessellation.

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

GRID, a C++ library which computes points on a grid.

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

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

HEX_GRID, a C++ library which computes sets of points in a 2D hexagonal grid.

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

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

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

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

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

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

SEQUENCE_STREAK_DISPLAY, a MATLAB program which makes a "streak file" of a sequence.

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

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

VAN_DER_CORPUT, a dataset directory which contains datasets of van der Corput sequences.

VAN_DER_CORPUT_ADVANCED, a C++ library which computes elements of a 1D van der Corput Quasi Monte Carlo (QMC) sequence, allowing the user more advanced and sophisticated input.

Reference:

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

List of Routines:

• R8VEC_TRANSPOSE_PRINT prints an R8VEC "transposed".
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• VDC_BASE computes an element of the van der Corput sequence in any base.
• VDC_INVERSE inverts an element of the van der Corput sequence.
• VDC computes an element of the van der Corput sequence.
• VDC_SEQUENCE computes a sequence of elements of the van der Corput sequence.

You can go up one level to the C++ source codes.

Last revised on 10 August 2016.