EFFICIENT COMPUTATION OF SOBOL’ QUASI-RANDOM GENERATOR
Main Article Content
Keywords
algorithm, time complexity, quasi-random generator, Sobol’ sequence, quasi-Monte Carlo simulation
Abstract
Purpose of the study: The quasi-Monte Carlo method is an important tool for modelling and analysing various complex problems in engineering, physical sciences, finance and business. The crucial element of the method is a sequence of deterministic quasi-random values, which is often obtained by using the Sobol’ quasi-random generator. The purpose of this study is to consider the time complexity of generating the Sobol’ sequence.
Methodology: Algorithms for determining the Sobol’ sequence have been studied. The algorithms have been implemented in the Python programming language.
Main Findings: It is established that this sequence can be generated in the linear time provided that generated numbers are based on 32-bit or 64-bit integers. The main result of the paper is the algorithm which enables this time-bound.
Applications of this study: The study can be applied in engineering, physical sciences, finance and business.
Novelty/Originality of this study: It is shown that Sobol’ sequence can be generated in linear time.
Downloads
References
2. Halton, J. (1964). Algorithm 247: Radical-inverse quasi-random point sequence. Communications of the ACM, 7, 701-702.
3. Hammersley, J. M. & Handscomb, D. C. (1964). Monte Carlo Methods, New York: John Wiley & Sons.
4. Hofert, M. Prasad. A. Zhu, M. Quasi-random number generators for multivariate distributions based on generative neural networks. https://arxiv.org/pdf/1811.00683.pdf. Accesed 7 May 2019.
5. Joe S. & Kuo F. Y. (2003). Remark on Algorithm 659: Implementing Sobol’s quasi-random sequence generator. ACM Transactions on Mathematical Software, 29, 49–57.
6. Joe S. & Kuo F. Y. (2008). Constructing Sobol′ sequences with better two-dimensional projections, SIAM Journal on Scientific Computing. 30, 2635–2654.
7. Joe S. & Kuo F. Y. Sobol sequence generator. https://web.maths.unsw.edu.au/~fkuo/sobol/. Accesed 7 May 2019.
8. Lyuu, Y.-D. (2002). Financial Engineering and Computation, Cambridge, UK: Cambridge University Press.
9. Morokoff, W. J. & Caflisch R. E. (1995). Quasi-Monte Carlo Integration. Journal of Computational Physics. 122 (2), 218-230.
10. Niederreiter, H. (1992). Random Number Generation and Quasi-Monte Carlo Methods, Philadelphia, PA: Society for Industrial and Applied Mathematics.
11. Sobol, I.M. (1967). Distribution of points in a cube and approximate evaluation of integrals. USSR Computational Mathematics and Mathematical Physics, 7, 86–112.
Article Sidebar
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors retain copyright for the published content.