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 xn−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 xn−1 to xn, i.e.


x_{n,i}=x_{n-1,i} \oplus v_{k,i}. \,

Read more about this topic:  Sobol Sequence

Famous quotes containing the words fast and/or construction:

    Today’s pressures on middle-class children to grow up fast begin in early childhood. Chief among them is the pressure for early intellectual attainment, deriving from a changed perception of precocity. Several decades ago precocity was looked upon with great suspicion. The child prodigy, it was thought, turned out to be a neurotic adult; thus the phrase “early ripe, early rot!”
    David Elkind (20th century)

    There is, I think, no point in the philosophy of progressive education which is sounder than its emphasis upon the importance of the participation of the learner in the formation of the purposes which direct his activities in the learning process, just as there is no defect in traditional education greater than its failure to secure the active cooperation of the pupil in construction of the purposes involved in his studying.
    John Dewey (1859–1952)