Abstract
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.
Supported by the project of European Commission - BIS 21 under contract ICA1- CT-2000-70016 and by the Ministry of Education and Science of Bulgaria under contracts NSF I-811/98 and NSF MM-902/99
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Sobol', I. M.: The distribution of points in a cube and approximate evaluation of integrals. Zh. Vychisl. Mat. Mat. Fiz. 7 (1967) 784–802 (in Russian).
Sobol', I. M.: Multi-dimensional Quadrature Formulae and Haar Functions. Nauka, Moscow (1969)
Owen, A.: Monte Carlo Extension of Quasi-Monte Carlo. In: Medieiros, D. J., Watson, E. F., Manivannan, M., and Carson, J. (eds.): Proceedings of WSC’98 (1998) 571–577.
Paskov, S. and Traub, J.: Faster Valuation of Financial Derivatives. Journal of Portfolio Management, 22:1, Fall (1995) 113–120.
ANSI/IEEE Standard 754-1985: Standard for Binary Floating Point Arithmetic.
Atanassov, E. I.: Measuring the Performance of a Power PC Cluster. Sloot, Peter M. A., Kenneth Tan, C. J., Dongarra, Jack, and Hoekstra, Alfons G. (eds.): dvxProceedings of the 2002 International Conference on Computational Science (ICCS 2002). Lecture Notes in Computer Science, Vol. 2329, Springer-Verlag, Berlin (2002) 628–634.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Atanassov, E.I. (2003). A New Efficient Algorithm for Generating the Scrambled Sobol' Sequence. In: Dimov, I., Lirkov, I., Margenov, S., Zlatev, Z. (eds) Numerical Methods and Applications. NMA 2002. Lecture Notes in Computer Science, vol 2542. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36487-0_8
Download citation
DOI: https://doi.org/10.1007/3-540-36487-0_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00608-4
Online ISBN: 978-3-540-36487-0
eBook Packages: Springer Book Archive