โ† Wiki Index / Computation & Algorithms / Van der Corput Sequence
๐Ÿ’ป Computation & Algorithms

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:

nBinary (n2)Reversed Fractionφ2(n) (Decimal)
1120.121/2 = 0.5000
21020.0121/4 = 0.2500
31120.1123/4 = 0.7500
410020.00121/8 = 0.1250
510120.10125/8 = 0.6250
611020.01123/8 = 0.3750
711120.11127/8 = 0.8750
8100020.000121/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

  1. 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
  2. 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
  3. 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
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision