van_der_corput

van_der_corput, an Octave code 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)
0	0	.0	0.0
1	1	.1	0.5
2	10	.01	0.25
3	11	.11	0.75
4	100	.001	0.125
5	101	.101	0.625
6	110	.011	0.375
7	111	.111	0.875
8	1000	.0001	0.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 an Octave version and a Python version.

Related Data and Programs:

van_der_corput_test

halton, an Octave code which computes elements of a Halton sequence.

hammersley, an Octave code which computes elements of a Hammersley Quasi Monte Carlo (QMC) sequence, using a simple interface.

latin_center, an Octave code which computes elements of a Latin Hypercube dataset, choosing center points.

latin_edge, an Octave code which computes elements of a Latin Hypercube dataset, choosing edge points.

latin_random, an Octave code which computes elements of a Latin Hypercube dataset, choosing points at random.

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

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:

• circle_unit_van_der_corput, picks a van der Corput point on the unit circle.
• i4_to_van_der_corput, computes an element of a van der Corput sequence.
• i4_to_van_der_corput_sequence, computes several consecutive elements of a van der Corput sequence.
• r8mat_write.m, writes an R8MAT file.
• r8vec_transpose_print.m, prints an R8VEC transposed.
• van_der_corput_base_get.m, gets the van der Corput base.
• van_der_corput_base_set.m, sets the van der Corput base.
• van_der_corput_key_get.m, gets the van der Corput key.
• van_der_corput_key_set.m, sets the van der Corput key.
• van_der_corput.m, computes an element of the van der Corput sequence.
• van_der_corput_sequence.m, computes several elements of the van der Corput sequence.
• vdc.m, computes the next element of the van der Corput sequence in base 2.
• vdc_base.m, computes the next element of a van der Corput sequence in base B.
• vdc_inverse.m, given the element of the van der Corput sequence base 2, returns the index.
• vdc_numerator_sequence.m, van der Corput numerator sequence base 2..
• vdc_sequence.m, returns a sequence of elements of the van der Corput sequence base 2.