METHODS OF CHOOSING A RANDOM NUMBER GENERATOR FOR MODELING STOCHASTIC PROCESSES
DOI:
https://doi.org/10.18372/2225-5036.30.18613Keywords:
Mersenne twister generator, Xorshift generator, inverse function method, Monte Carlo method, Pearson chi-square test, numerical flow post-processing, algorithm, method, nonlinear system, stability, forecasting, information technologyAbstract
Modern computer modeling is an important stage in the design of control systems for the distribution of information flows in computer networks and in modern control systems for complex technological processes. The core of any computer model is a source of randomness, which should generate a uniformly distributed stream of random integers or real numbers. In addition to the uniformity of distribution, such a source must meet the requirements of economic use of computing system resources. An analysis of simple arithmetic generators is given and, based on it, it is shown that generators such as the Fibonacci sequence generator with a delay and the Xorshift generator proposed by J. Marsaglia are suitable as a generator for the needs of modeling stochastic processes, which are an alternative to the random number generators built into existing programming environment. On the basis of the conducted research, it was concluded that any unevenness of the numbers at the output of the generator chosen as a source of randomness significantly affects the quality of the process to be modeled, and because of this, the numerical flows from such generators should be additionally processed by methods extraction of that part of them that provides maximum randomness. The method of performing such extraction by "slicing" the input stream, the criteria used in this, and the results of its experimental research for the Xorshift128 generator are presented. A conclusion is made about the advantages of using simple and economical generators in a heap with post-processing procedures performed at the level of integers or real numbers. The results of the evaluation of the Xorshift generator, taking into account the methods described in the work, are given, and a conclusion is made about the feasibility of its use for the needs of modeling stochastic processes.
References
Smile Markovski, Danilo Gligoroski, Ljupco Kocarev. Unbiased Random Sequences from Qua-sigroup String Transformations. Part of the Lecture Notes in Computer Science book series (LNSC, volume 3557). URL: https:// www.iacr.org /archive/fse2005/35570161 /355¬70161.pdf.
Dichtl, M.: Bad and good ways of post-processing biased physical random numbers. In: Biryu-kov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 127-152. Springer, Heidelberg (2007) URL: https://link.springer.com/content/pdf/10.1007/978-3-540-74619-5_9.pdf.
Smile Markovski, Danilo Gligoroski Ljupco Kocarev. Unbiased Random Sequences from Qua-sigroup String Transformations. International Work-shop on Fast Software Encryption FSE 2005: Fast Soft-ware Encryption pp 163-180 URL: https://www.iacr.org/archive/fse2005 /35570161/35570161.pdf.
Makoto Matsumoto and Takuji Nishimura. 1998. Mersenne Twister: A 623-dimensionally Equidis-tributed Uniform Pseudo-Random Number Generator. ACM Trans. Model. Comput. Simul. 8, 1 (Jan. 1998), 3-30. https://doi.org/10.1145/272991.272995 URL: https://dl. acm.org/doi/pdf/10.1145/272991.272995.
François Panneton and Pierre L’Ecuyer. 2005. On the Xorshift Random Number Generators. ACM Trans. Model. Comput. Simul. 15, 4 (Oct. 2005), 346-361. https://doi.org/10.1145/1113316.1113319. URL: https: //web.archive.org/web/20210126143346/http://www. iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf.
Niederreiter H. Quasi-Monte Carlo methods and pseudo-random number. doi: https://doi.org/10. 1090/S0002-9904-1978-14532-7. URL: https://www.ams. org/journals/bull/1978-84-06/S0002-9904-1978-14532-7/S0002-9904-1978-14532-7.pdf.
D. E. Knuth. The Art of Computer Program-ming, Volume 2: Seminumerical Algorithms, 3rd. ed., Boston, Mass, USA: Addison-Wesley, Longman Pub-lishing, Addison-Wesley, Reading, Mass, 1998. URL: http:// publ.lib.ru/ARCHIVES/K / KNUT_Donal%27d_ Ervin/ Knut_D.E._I skusstvo _ programmirovaniya._T.2. (2001). [djv-fax].zip.
Yurii Shcherbyna, Nadiia Kazakova, Oleksii Fraze-Frazenko. The Mersenne Twister Output Stream Postprocessing. INTERNATIONAL SCIENTIFIC AND PRACTICAL CONFERENCE. September 2021. pp 277-285 URL: https://ceur-ws.org/Vol-3200/paper39.pdf.
J. von Neumann. Various techniques for use in connection with random digits. Applied Math Series, Notes by G. E. Forsythe, in National Bureau of Stand-ards, Vol. 12, 36-38, 1951. URL: https://mcnp.lanl.gov/pdf_ files/nbs_vonneumann.pdf.
Trevisan L. Extractors and Pseudorandom Ge¬ nerators 1999. Journal of the ACM. URL: http://theory.stanford.edu/~trevisan/pubs/extractor-full.pdf.
Siew-Hwee Kwok, Yen-Ling Ee, Guanhan Chew, Kanghong Zheng, Khoongming Khoo, Chik-How Tan. A Comparison of Post-Processing Tech-niques for Biased Random Number Generators. WISTP 2011: Information Security Theory and Practice. Securi-ty and Privacy of Mobile Devices in Wireless Commu-nication. pp 175–190. URL: https://link.springer.com/content/pdf/ 10.1007/978-3-540-74619-5_9.pdf.
George Marsaglia. Random Number Genera-tors. 2003. DOI 10.22237/jmasm/1051747320 URL: https: //digitalcommons.wayne.edu/jmasm/vol2/iss1/2/.
George Marsaglia. Xorshift RNGs. 2003. DOI: 10.18637/jss.v008.i14. URL: https: // www.researchgate. net/publication/5142825_Xorshift_RNGs.
Shcherbyna, Y. Using the Xorshift generator to simulate stochastic processes // Przetwarzanie, transmit¬sja i bezpieczeństwo informacji // monografia / Yurii SHCHERBYNA, Nadiia KAZAKOVA, Oleksii FRAZE-FRAZENKO; Bielsko - Biała: Wydawnictwo Naukowe Akademii Techniczno-Humanistycznej w Bielsku-Białej, 2022. pp 313-144. ISBN 978-83-67652-00-1 DOI: https:// doi.org/10.53052/9788367652001.
The Mersenne Twister Output Stream Post-processing. Shcherbyna, Y., Kazakova, N., Fraze-Frazenko, O. CEUR Workshop https://ceur-ws.org/Vol-3200/paper39.pdf, 2021, 3200, pp. 265-273.
Yevseiev, S., Melenti, Y., Voitko, O., Hrebe-niuk, V., Korchenko, A., Mykus, S., Milov, O., Pro-kopenko, O., Sievierinov, O., Chopenko, D. Develop-ment of a Concept for Building a Critical Infrastructure Facilities Security System (2021) Eastern-European Journal of Enterprise Technologies, 3, pp. 63-83. DOI: 10.15587/1729-4061.2021. 233533.
