Quasi Monte Carlo Integration

Note. I denote the modulo operation with [\dummyarg]_n. In particular [\dummyarg]_1 is the fractional part.

\mod{a}_b ≜ a - b ⋅ \floor{\frac a b}

Roberts sequence

Definition. The d-dimensional Roberts sequence is a particularly elegant low-discrepancy sequence:

\begin{aligned} \vec x_i &≜ \mod{i ⋅ \vec ϕ_d}_1 & \vec ϕ_d &≜ \begin{bmatrix} ϕ_d \\\\ ϕ_d^2 \\\\ \vdots \\\\ ϕ_d^d \end{bmatrix} \end{aligned}

where ϕ_d is the unique positive root of x^{d+1} + x^d - 1 and \mod{\dummyarg}_1 is taken element wise over vectors.

Note. The root will be in (\frac 12, 1). Closed form solutions for ϕ_1 and ϕ_2 are the reciprocals of the golden ratio and the plastic number:

\begin{aligned} ϕ_1 &= \frac{\sqrt{5} - 1}{2} & ϕ_2 &= \sqrt[3]{\frac{25 + \sqrt{207}}{54}} + \sqrt[3]{\frac{25 - \sqrt{207}}{54}} -\frac 1 3 \end{aligned}

Note. In Roberts' notes the ϕ_d is defined in reciprocal form compared to here. These definitions are algebraically identical.

To do. A procedure to compute the nearest odd number k to ϕ_d^j ⋅ 2^{64}, this number will iterate through all 2^{64} numbers and can be implemented with a single overflowing multiplication or iterated addition:

\begin{aligned} n_i &= \mod{i ⋅ k}\_{2^{64}} & n_{i + 1} &= \mod{n_i + k}_{2^{64}} \end{aligned}

To do

Does this work for rendering too?

https://www.cs.cmu.edu/~kmcrane/Projects/MonteCarloGeometryProcessing/paper.pdf

References

http://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/

https://news.ycombinator.com/item?id=17873284

https://statweb.stanford.edu/~owen/mc/Ch-quadrature.pdf

https://statweb.stanford.edu/~owen/mc/