Corput

The Van der Corput sequence is a low-discrepancy sequence, also known as a quasi-random or sub-random sequence. It's used to generate points that are more evenly distributed than purely random points, making it useful in numerical integration, Monte Carlo methods, and other applications where uniform sampling is desirable.

The Corput sequence is constructed by reflecting the sequence of natural numbers in different bases. For a given base b, the nth number in the sequence is obtained by writing n in base b, reversing the digits, and placing a radix point at the beginning. This effectively scrambles the digits of n in a specific way that ensures even distribution.

Different bases yield different Corput sequences. The most commonly used base is 2, resulting in the binary Van der Corput sequence. Using different prime numbers as bases for multiple Corput sequences can generate low-discrepancy point sets in higher dimensions, often referred to as Halton sequences (though the Halton sequence also involves a specific indexing order).

The key property of the Corput sequence is its low discrepancy. This means that the difference between the proportion of points falling within a given interval and the length of that interval tends to be smaller than for random sequences. This property is crucial for reducing errors in numerical computations that rely on sampling.

While the individual points in a Corput sequence are deterministically generated, their distribution mimics randomness in a desirable way, offering advantages over both purely random and purely regular sampling schemes.