A van der Corput sequence is an example of the simplest one-dimensional low-discrepancy sequence over the unit interval; it was first described in 1935 by the Dutch mathematician J. G. van der Corput. It is constructed by reversing the base-n representation of the sequence of natural numbers (1, 2, 3, …).

The b-ary representation of the positive integer n (≥ 1) is

\( n=\sum _{{k=0}}^{{L-1}}d_{k}(n)b^{k},

where b is the base in which the number n is represented, and 0 ≤ dk(n) < b, i.e. the k-th digit in the b-ary expansion of n. The n-th number in the van der Corput sequence is

\( g_{b}(n)=\sum _{{k=0}}^{{L-1}}d_{k}(n)b^{{-k-1}}.

Illustration of the filling of the unit interval (horizontal axis) using the first *n* terms of the decimal Van der Corput sequence, for *n* from 0 to 999 (vertical axis)

Examples

For example, to get the decimal van der Corput sequence, we start by dividing the numbers 1 to 9 in tenths (x/10), then we change the denominator to 100 to begin dividing in hundredths (x/100). In terms of numerator, we begin with all two-digit numbers from 10 to 99, but in backwards order of digits. Consequently, we will get the numerators grouped by the end digit. Firstly, all two-digit numerators that end with 1, so the next numerators are 01, 11, 21, 31, 41, 51, 61, 71, 81, 91. Then the numerators ending with 2, so they are 02, 12, 22, 32, 42, 52, 62, 72, 82, 92. An after the numerators ending in 3: 03, 13, 23 and so on...

Thus, the sequence begins

\( {\displaystyle \left\{{\tfrac {1}{10}},{\tfrac {2}{10}},{\tfrac {3}{10}},{\tfrac {4}{10}},{\tfrac {5}{10}},{\tfrac {6}{10}},{\tfrac {7}{10}},{\tfrac {8}{10}},{\tfrac {9}{10}},{\tfrac {1}{100}},{\tfrac {11}{100}},{\tfrac {21}{100}},{\tfrac {31}{100}},{\tfrac {41}{100}},{\tfrac {51}{100}},{\tfrac {61}{100}},{\tfrac {71}{100}},{\tfrac {81}{100}},{\tfrac {91}{100}},{\tfrac {2}{100}},{\tfrac {12}{100}},{\tfrac {22}{100}},{\tfrac {32}{100}},\ldots \right\},} \)

or in decimal representation:

0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61, 0.71, 0.81, 0.91, 0.02, 0.12, 0.22, 0.32, …,

The same can be done for the binary numeral system, and the binary van der Corput sequence is

0.12, 0.012, 0.112, 0.0012, 0.1012, 0.0112, 0.1112, 0.00012, 0.10012, 0.01012, 0.11012, 0.00112, 0.10112, 0.01112, 0.11112, …

or, equivalently,

\( \tfrac{1}{2}, \tfrac{1}{4}, \tfrac{3}{4}, \tfrac{1}{8}, \tfrac{5}{8}, \tfrac{3}{8}, \tfrac{7}{8}, \tfrac{1}{16}, \tfrac{9}{16}, \tfrac{5}{16}, \tfrac{13}{16}, \tfrac{3}{16}, \tfrac{11}{16}, \tfrac{7}{16}, \tfrac{15}{16}, \ldots. \)

The elements of the van der Corput sequence (in any base) form a dense set in the unit interval; that is, for any real number in [0, 1], there exists a subsequence of the van der Corput sequence that converges to that number. They are also equidistributed over the unit interval.

C implementation

double corput(int n, int base){

double q=0, bk=(double)1/base;

while (n > 0) {

q += (n % base)*bk;

n /= base;

bk /= base;

}

return q;

}

See also

Bit-reversal permutation

Constructions of low-discrepancy sequences

Halton sequence, a natural generalization of the van der Corput sequence to higher dimensions

References

van der Corput, J.G. (1935), "Verteilungsfunktionen (Erste Mitteilung)" (PDF), Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam (in German), 38: 813–821, Zbl 0012.34705

Kuipers, L.; Niederreiter, H. (2005) [1974], Uniform distribution of sequences, Dover Publications, p. 129,158, ISBN 0-486-45019-8, Zbl 0281.10001

External links

Van der Corput sequence at MathWorld

Undergraduate Texts in Mathematics

Graduate Studies in Mathematics

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License