Editing Sobol sequence (section)

== A fast algorithm ==

A more efficient [[Gray code]] implementation was proposed by Antonov and Saleev.<ref name=AS79>Antonov, I.A. and Saleev, V.M. (1979) "An economic method of computing LP<sub>τ</sub>-sequences". ''Zh. Vych. Mat. Mat. Fiz.'' '''19''': 243–245 (in Russian); ''U.S.S.R. Comput. Maths. Math. Phys.'' '''19''': 252–256 (in English).</ref>

As for the generation of Sobol’ numbers, they are clearly aided by the use of Gray code <math>G(n)=n \oplus \lfloor n/2 \rfloor</math> instead of ''n'' for constructing the ''n''-th point draw.

Suppose we have already generated all the Sobol’ sequence draws up to ''n''&nbsp;&minus;&nbsp;1 and kept in memory the values ''x''<sub>''n''&minus;1,''j''</sub> for all the required dimensions. Since the Gray code ''G''(''n'') differs from that of the preceding one ''G''(''n''&nbsp;&minus;&nbsp;1) by just a single, say the ''k''-th, bit (which is a rightmost zero bit of ''n''&nbsp;&minus;&nbsp;1), all that needs to be done is a single [[XOR]] operation for each dimension in order to propagate all of the ''x''<sub>''n''&minus;1</sub> to ''x''<sub>''n''</sub>, i.e.

:<math>
x_{n,i} = x_{n-1,i} \oplus v_{k,i}.
</math>