Van der Corput Sequence
The van der Corput sequence is the simplest one-dimensional low-discrepancy sequence, constructed by reversing the base-b digits of the natural numbers to achieve O((log N)/N) numerical integration error.
The van der Corput sequenceโintroduced by Dutch mathematician Johannes van der Corput in 1935โis the foundational one-dimensional low-discrepancy (quasi-random) sequence over the unit interval [0, 1). Constructed by taking the natural numbers n = 1, 2, 3, ..., expressing each integer in a fixed integer base b ≥ 2, and reflecting its digits across the radix point (radical inverse function φb(n)), the sequence fills [0, 1) far more uniformly than independent pseudorandom sampling, reducing quasi-Monte Carlo (QMC) numerical integration error from O(N−1/2) to O((log N) / N).
Definition: Radical Inverse Construction in Base b
Let n ≥ 1 be a positive integer written in base b ≥ 2 as:
n = ∑k=0L dk(n) bk, where each digit dk(n) ∈ {0, 1, ..., b − 1}.
The base-b radical inverse function φb(n) reverses the order of digits and places them after the decimal/radix point:
φb(n) = ∑k=0L dk(n) b−k−1
For the standard binary (base-2) van der Corput sequence, the first eight terms (n = 1, ..., 8) are:
| n | Binary (n2) | Reversed Fraction | φ2(n) (Decimal) |
|---|---|---|---|
| 1 | 12 | 0.12 | 1/2 = 0.5000 |
| 2 | 102 | 0.012 | 1/4 = 0.2500 |
| 3 | 112 | 0.112 | 3/4 = 0.7500 |
| 4 | 1002 | 0.0012 | 1/8 = 0.1250 |
| 5 | 1012 | 0.1012 | 5/8 = 0.6250 |
| 6 | 1102 | 0.0112 | 3/8 = 0.3750 |
| 7 | 1112 | 0.1112 | 7/8 = 0.8750 |
| 8 | 10002 | 0.00012 | 1/16 = 0.0625 |
Notice the recursive interval-splitting property: n = 1 bisects [0, 1); n = 2, 3 bisect the two halves; n = 4, 5, 6, 7 bisect all four quarters simultaneously. Because every new power of b subdivides existing gaps evenly, the sequence never produces large empty clusters or clumps.
Star Discrepancy Bounds and Quasi-Monte Carlo Integration
Uniformity on [0, 1) is measured by the star discrepancy (DN*), the worst-case difference between the fraction of the first N points falling in [0, u) and the interval length u. Whereas N independent random points exhibit DN = O(N−1/2 √(log log N))* by the law of the iterated logarithm, any base-b van der Corput sequence satisfies:
DN ≤ Cb (log N) / *N**
By the KoksmaโHlawka inequality, the error of approximating an integral ∫01 f(x) dx by the sample mean (1/N) ∑ f(xn) is bounded by V(f) · DN* (where V(f) is total variation), delivering nearly O(1/N) convergenceโorders of magnitude faster than standard Monte Carlo.
Multidimensional Extensions and Computer Graphics Applications
The van der Corput sequence is the core building block of higher-dimensional low-discrepancy point sets:
- Halton Sequence: Assigns distinct prime bases b1 = 2, b2 = 3, b3 = 5, ... across s dimensions: ( φ2(n), φ3(n), ..., φps(n) ).
- Hammersley Point Set: Pairs (n/N, φ2(n), ...) when total sample count N is fixed in advance.
- Sobol' and Faure Sequences: Generalize digit reversal via linear matrix scramblings over finite fields F2 and Fp to avoid correlation artifacts in high dimensions.
In mechanically based ray tracing, Monte Carlo rendering, financial derivative pricing, and hyperparameter optimization, base-2 van der Corput (bit-reversal) sampling is computable in a single CPU instruction (rbit / bit-masking) and supports progressive, anytime rendering with zero variance spikes.
Scrambling, Algorithmic Implementation, and Variance Reduction
In practical randomized quasi-Monte Carlo (RQMC) workflows, deterministic van der Corput and Halton sequences are combined with random digit shifting (CranleyโPatterson rotation) or Owen nested uniform scrambling. Adding a single uniform random shift U ∈ [0, 1) modulo 1 (x'n = (xn + U) mod 1) preserves the optimal O((log N)/N) discrepancy of the sequence while making every sample point unbiased (E[f(x'n)] = ∫ f), enabling rigorous variance and confidence-interval estimation across R independent random shifts.
Computationally, generating the n-th base-2 van der Corput number requires only bit-reversing the 32- or 64-bit integer n and dividing by 232 or 264, making it virtually overhead-free inside GPU shaders, path tracers, and stochastic simulation engines.
Frequently Asked Questions
Why is the van der Corput sequence deterministic rather than random?
It is quasi-random (deterministic) because its goal is uniform coverage (low discrepancy) rather than statistical unpredictability; deliberately avoiding random clustering reduces numerical integration variance from O(N−1/2) to O((log N)/N).
What happens if you use the van der Corput sequence in high dimensions without changing the base?
Using the same base b across dimensions correlates coordinates linearly; higher dimensions must either use coprime bases (Halton sequence) or apply Owen scrambling / digit permutations to break cross-dimensional correlations.
References
- Halton, J. H. (1960). On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik, 2(1), 84โ90. https://doi.org/10.1007/bf01386213
- Ichikawa, Y., & Mori, M. (2004). Discrepancy of van der Corput sequences generated by piecewise linear transformations. Monte Carlo Methods and Applications, 10(3โ4), 311โ320. https://doi.org/10.1515/156939604777303217
- Hartinger, J., & Kainhofer, R. (2006). Non-uniform low-discrepancy sequence generation and integration of singular integrands. In Monte Carlo and Quasi-Monte Carlo Methods 2004 (pp. 163โ179). Springer. https://doi.org/10.1007/3-540-31186-6_11