A New Efficient Algorithm for Generating the Scrambled Sobol' Sequence

The Sobol’ sequence is the most widely deployed low-discrepancy sequence, and is used for calculating multi-dimensional integrals and in quasi-Monte Carlo simulation. Owen first proposed the idea of scrambling this sequence in a manner that maintained its low discrepancy. One of his motivations was to use these scrambled sequences to provide quasi-Monte Carlo methods with simple error estimates like those in normal Monte Carlo. In fact, it is now common for the Sobol’ sequence as well as (t, m, s)-nets and (t, s)-sequences to be used with scrambling. However, many have pointed out that scrambling is often dificult to implement and time consuming. In this paper we describe a new generation algorithm that allows consecutive terms of the scrambled Sobol’ sequence to be obtained with essentially only two operations per coordinate: one floating point addition and one bit-wise xor operation. Note: this omits operations that are needed only once per tuple. This scrambling is achieved at no additional computational cost over that of unscrambled generation as it is accomplished totally in the initialization. In addition, the terms of the sequence are obtained in their normal order, without the usual permutation introduced by Gray code ordering used to minimize the cost of computing the next Sobol’ element. This algorithm is relatively simple and is quite suitable for parallelization and vectorization. An example implementation of the algorithm, written in pseudo-code is presented. Possible improvements of the algorithm are discussed along with the presentation of some timing results.