Sobol Sequence - A Fast Algorithm For The Construction of Sobol Sequences

A Fast Algorithm For The Construction of Sobol Sequences

A more efficient Gray code implementation was proposed by Antonov and Saleev.

As for the generation of Sobol numbers, they are clearly aided by the use of Gray code instead of n for constructing the n-th point draw.

Suppose we have already generated all the Sobol sequence draws up to n − 1, and kept in memory the values x_n−1,j for all the required dimensions. Since the Gray code G(n) differs from that of the preceding one G(n − 1) by just a single, say the k-th, bit (which is a rightmost bit of n − 1), all that needs to be done is a single XOR operation for each dimension in order to propagate all of the x_n−1 to x_n, i.e.