Sobol sequence

Description

A Sobol sequence is a sequence of points in $[0,1)^s$ built from binary digits. For each coordinate $j = 1, \ldots, s$ one fixes direction numbers $v_{j,1}, v_{j,2}, \ldots \in (0,1)$, constructed as follows.

1. Choose a primitive polynomial over $\F_2$ $x^{d} + c_1 x^{d-1} + \cdots + c_{d-1} x + 1$ of degree $d = d_j$, with different polynomials for different $j$.
2. Choose odd integers $m_1, \ldots, m_d$ with $m_k < 2^k$.
3. For $k > d$ set $m_k = 2 c_1 m_{k-1} \oplus 2^2 c_2 m_{k-2} \oplus \cdots \oplus 2^{d-1} c_{d-1} m_{k-d+1} \oplus 2^d m_{k-d} \oplus m_{k-d}$, where $\oplus$ is the bitwise exclusive or of binary integers.
4. Set $v_{j,k} = m_k / 2^k$.

Write $n \ge 0$ in binary as $n = \sum_{k \ge 1} \beta_k 2^{k-1}$ with $\beta_k \in \set{0,1}$. The $j$-th coordinate of the $n$-th point is $$x_{n,j} = \beta_1 v_{j,1} \oplus \beta_2 v_{j,2} \oplus \cdots,$$ where $\oplus$ now acts digit by digit on binary expansions. The first coordinate usually takes $v_{1,k} = 2^{-k}$, which gives the van der Corput sequence in base $2$.