Main Article Content
Abstract
Purpose of the study: The quasi-Monte Carlo method is an essential tool for modeling and analyzing 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.
Keywords
Article Details
Authors retain the copyright without restrictions for their published content in this journal. IJSRTM is a SHERPA ROMEO Journal.
Publishing License
This is an open-access article distributed under the terms of 
References
- Antonov I. A. & Saleev V. M. (1979). An economical method of computing LP τ-sequences. USSR Computational Mathematics and Mathematical Physics, 19, 252–256. https://doi.org/10.1016/0041-5553(79)90085-5 DOI: https://doi.org/10.1016/0041-5553(79)90085-5
- Halton, J. (1964). Algorithm 247: Radical-inverse quasi-random point sequence. Communications of the ACM, 7, 701-702. https://doi.org/10.1145/355588.365104 DOI: https://doi.org/10.1145/355588.365104
- Hammersley, J. M. & Handscomb, D. C. (1964). Monte Carlo Methods, New York: John Wiley & Sons. https://doi.org/10.1007/978-94-009-5819-7 DOI: https://doi.org/10.1007/978-94-009-5819-7
- PMid:14223010
- 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. Accessed 7 May 2019.
- 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. https://doi.org/10.1145/641876.641879 DOI: https://doi.org/10.1145/641876.641879
- Joe S. & Kuo F. Y. (2008). Constructing Sobol′ sequences with better two-dimensional projections, SIAM Journal on Scientific Computing. 30, 2635–2654. https://doi.org/10.1137/070709359 DOI: https://doi.org/10.1137/070709359
- Joe S. & Kuo F. Y. Sobol sequence generator. https://web.maths.unsw.edu.au/~fkuo/sobol/. Accessed 7 May 2019.
- Lyuu, Y.-D. (2002). Financial Engineering and Computation, Cambridge, UK: Cambridge University Press.
- Morokoff, W. J. & Caflisch R. E. (1995). Quasi-Monte Carlo Integration. Journal of Computational Physics. 122 (2), 218-230. https://doi.org/10.1006/jcph.1995.1209 DOI: https://doi.org/10.1006/jcph.1995.1209
- Niederreiter, H. (1992). Random Number Generation and Quasi-Monte Carlo Methods, Philadelphia, PA: Society for Industrial and Applied Mathematics. Sobol, I.M. (1967). Distribution of points in a cube and approximate evaluation of integrals. USSR Computational Mathematics and Mathematical Physics, 7, 86–112. https://doi.org/10.1016/0041-5553(67)90144-9 DOI: https://doi.org/10.1016/0041-5553(67)90144-9
References
Antonov I. A. & Saleev V. M. (1979). An economical method of computing LP τ-sequences. USSR Computational Mathematics and Mathematical Physics, 19, 252–256. https://doi.org/10.1016/0041-5553(79)90085-5 DOI: https://doi.org/10.1016/0041-5553(79)90085-5
Halton, J. (1964). Algorithm 247: Radical-inverse quasi-random point sequence. Communications of the ACM, 7, 701-702. https://doi.org/10.1145/355588.365104 DOI: https://doi.org/10.1145/355588.365104
Hammersley, J. M. & Handscomb, D. C. (1964). Monte Carlo Methods, New York: John Wiley & Sons. https://doi.org/10.1007/978-94-009-5819-7 DOI: https://doi.org/10.1007/978-94-009-5819-7
PMid:14223010
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. Accessed 7 May 2019.
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. https://doi.org/10.1145/641876.641879 DOI: https://doi.org/10.1145/641876.641879
Joe S. & Kuo F. Y. (2008). Constructing Sobol′ sequences with better two-dimensional projections, SIAM Journal on Scientific Computing. 30, 2635–2654. https://doi.org/10.1137/070709359 DOI: https://doi.org/10.1137/070709359
Joe S. & Kuo F. Y. Sobol sequence generator. https://web.maths.unsw.edu.au/~fkuo/sobol/. Accessed 7 May 2019.
Lyuu, Y.-D. (2002). Financial Engineering and Computation, Cambridge, UK: Cambridge University Press.
Morokoff, W. J. & Caflisch R. E. (1995). Quasi-Monte Carlo Integration. Journal of Computational Physics. 122 (2), 218-230. https://doi.org/10.1006/jcph.1995.1209 DOI: https://doi.org/10.1006/jcph.1995.1209
Niederreiter, H. (1992). Random Number Generation and Quasi-Monte Carlo Methods, Philadelphia, PA: Society for Industrial and Applied Mathematics. Sobol, I.M. (1967). Distribution of points in a cube and approximate evaluation of integrals. USSR Computational Mathematics and Mathematical Physics, 7, 86–112. https://doi.org/10.1016/0041-5553(67)90144-9 DOI: https://doi.org/10.1016/0041-5553(67)90144-9