Generator of Uniform Twister Sequences of Random Integer Numbers without Storage Arrays

Mersenne Twister random integer number generators may use arrays to implement twister shift operations internally. This technology provides excellent results for random number arrays in short and medium sequences. However, today's generators tend towards fairly long sequences, arrays of which may overflow the computer's random-access memory. These options make the older array technology unusable, since then there is no place anymore for applications and the operating system. We propose a new technology of generating twister sequences without using congruent twister arrays. It makes it possible to create uniform random integer sequences of arbitrary length that do not use up random access memory. Simulation results confirm that the random numbers obtained feature a perfectly uniform distribution over a range of unique sequences. Moreover, combining this new approach with the twister generation adjustment algorithm allows for significant increases in the length of sequences created, not involving any extra random-access memory

References

[1] Shamir A. On the generation of cryptographically strong pseudorandom sequences. ACM TOCS, 1983, vol. 1, iss. 1, pp. 38–44. DOI: 10.1145/357353.357357

[2] Lewko A.B., Waters B. Efficient pseudorandom functions from the decisional linear assumption and weaker variants. Proc. 16th ACM Conf. on Computer and Communications Security, 2009, pp. 112–120. DOI: 10.1145/1653662.1653677

[3] Claessen K., Palka M.H. Splittable pseudorandom number generators using cryptographic hashing. Proc. 2013 ACM SIGPLAN Symposium on Haskell, 2013, vol. 48, iss. 12, pp. 47–58. DOI: 10.1145/2503778.2503784

[4] Eichenauer-Herrmann J., Niederreiter H. Digital inversive pseudorandom numbers. ACM TOMACS, 1994, vol. 4, iss. 4, pp. 339–349. DOI: 10.1145/200883.200896

[5] Hellekalek P. Inversive pseudorandom number generators: concepts, results and links. Proc. 27th Conf. on Winter Simulation, 1995, pp. 255–262. DOI: 10.1145/224401.224612

[6] Sussman M., Crutchfield W., Papakipos M. Pseudorandom number generation on the GPU. Proc. 21st ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware, 2006, pp. 87–94. DOI: 10.1145/1283900.1283914

[7] Mandal K., Fan X., Gong G. Design and implementation of warbler family of lightweight pseudorandom number generators for smart devices. ACM TECS, 2016, vol. 15, iss. 1, art. 1. DOI: 10.1145/2808230

[8] Li M. Generation of teletraffic of generalized Cauchy type. Phys. Scr., 2010, vol. 81, iss. 2, art. 025007. DOI: 10.1088/0031-8949/81/02/025007

[9] Li M. Record length requirement of long-range dependent teletraffic. Physica A: Statistical Mechanics and its Applications, 2017, vol. 472, pp. 164–187. DOI: 10.1016/j.physa.2016.12.069

[10] Niederreiter H. New methods for pseudorandom numbers and pseudorandom vector generation. Proc. 24th Conf. on Winter Simulation, 1992, pp. 264–269. DOI: 10.1145/167293.167348

[11] Meka R., Zuckerman D. Pseudorandom generators for polynomial threshold functions. STOC10 Proc. 42nd ACM Symposium on Theory of Computing, 2010, pp. 427–436. DOI: 10.1145/1806689.1806749

[12] Gopalan P., Meka R., Reingold O., Zuckerman D. Pseudorandom generators for combinatorial shapes. STOC11 Proc. 43rd Annual ACM Symposium on Theory of Computing, 2011, pp. 253–262. DOI: 10.1145/1993636.1993671

[13] Leva J.L. A fast normal random number generator. ACM TOMS, 1992, vol. 18, iss. 4, pp. 449–453. DOI: 10.1145/138351.138364

[14] Applebaum B. Pseudorandom generators with long stretch and low locality from random local one-way functions. SNOC12 Proc. 44th Annual ACM Symposium on Theory of Computing, 2012, pp. 805–816. DOI: 10.1145/2213977.2214050

[15] White D.R., Clark J., Jacob J., Poulding S.M. Searching for resource-efficient programs: low-power pseudorandom number generators. GECCO08 Proc. 10th Annual Conf. on Genetic and Evolutionary Computation, 2008, pp. 1775–1782. DOI: 10.1145/1389095.1389437

[16] Langdon W.B. A fast high quality pseudorandom number generator for nVidia CUDA. GECCO09 Proc. 11th Annual Conf. on Genetic and Evolutionary Computation, 2009, pp. 2511–2514. DOI: 10.1145/1570256.1570353

[17] Juratli M.A., Menyaev Y.A., Sarimollaoglu M., Siegel E.R., Nedosekin D.A., Suen J.Y., Melerzanov A.V., Juratli T.A., Galanzha E.I., Zharov V.P. Real-time label-free embolus detection using in vivo photoacoustic flow cytometry. PLoS One, vol. 11, no. 5, art. e0156269. DOI: 10.1371/journal.pone.0156269

[18] Juratli M.A., Menyaev Y.A., Sarimollaoglu M., Siegel E.R., Nedosekin D.A., Suen J.Y., Melerzanov A.M., Juratli T.A., Galanzha E.I., Zharov V.P. Bioinspired hemozoin nanocrystals as high contrast photoacoustic agents for ultrasensitive malaria diagnosis. J. Nanomed. Nanotechnol., 2016, vol. 7, no. 3, pp. 49. DOI: 10.4172/2157–7439.C1.031

[19] Cai C., Nedosekin D.A., Menyaev Y.A., Sarimollaoglu M., Proskurnin M.A., Zharov V.P. Photoacoustic flow cytometry for single sickle cell detection in vitro and in vivo. Anal. Cell. Pathol., 2016, vol. 2016, art. 2642361. DOI: 10.1155/2016/2642361 Available at: https://www.hindawi.com/journals/acp/2016/2642361

[20] Menyaev Y.A., Nedosekin D.A., Sarimollaoglu M., Juratli M.A., Galanzha E.I., Tuchin V.V., Zharov V.P. Optical clearing in photoacoustic flowcytometry. Biomed. Opt. Express, 2013, vol. 4, iss. 12, pp. 3030–3041. DOI: 10.1364/BOE.4.003030

[21] Menyaev Y.A., Carey K.A., Nedosekin D.A., Sarimollaoglu M., Galanzha E.I., Stumhofer J.S., Zharov V.P. Preclinical photoacoustic models: application for ultrasensitive single cell malaria diagnosis in large vein and artery. Biomed. Opt. Express, 2016, vol. 7, iss. 9, pp. 3643–3658. DOI: 10.1364/BOE.7.003643

[22] Matsumoto M., Nishimura T. Mersenne twister: a 623-dimensionally equidistributed uniform pseudorandom number generator. ACM TOMACS, 1998, vol. 8, iss. 1, pp. 3–30. DOI: 10.1145/272991.272995

[23] Matsumoto M., Saito M., Haramoto H., Nishimura T. Pseudorandom number generation: impossibility and compromise. J. Univers. Comput. Sci., 2006, vol. 12, iss. 6, pp. 672–690. DOI: 10.3217/jucs-012-06-0672

[24] Matsumoto M., Wada I., Kuramoto A., Ashihara H. Common defects in initialization of pseudorandom number generators. ACM TOMACS, 2007, vol. 17, iss. 4, art. 15. DOI: 10.1145/1276927.1276928

[25] Bos J.W., Kleinjung T., Lenstra A.K., Montgomery P.L. Efficient SIMD arithmetic modulo a Mersenne number. Proc. 2011 IEEE 20th Symposium on Computer Arithmetic, 2011, pp. 213–221. DOI: 10.1109/ARITH.2011.37

[26] Deon A., Menyaev Y. Parametrical tuning of twisting generators. J. Comput. Sci., 2016, vol. 12, iss. 8, pp. 363–378. DOI: 10.3844/jcssp.2016.363.378

[27] Deon A.F., Menyaev Yu.A. Uniform random quantity generator using complete vortex array technology. Vestn. Mosk. Gos. Tekh. Univ. im. N.E. Baumana, Priborostr. [Herald of the Bauman Moscow State Tech. Univ., Instrum. Eng.], no. 2, pp. 86–110 (in Russ.). DOI: 10.18698/0236-3933-2017-2-86-110

[28] Saito M., Matsumoto M. SIMD-oriented fast Mersenne twister: a 128-bit pseudorandom number generator. A. Keller, S. Heinrich, H. Niederreiter, eds. In: Monte Carlo and quasi-Monte Carlo methods 2006. Springer, 2008, pp. 607–622.

[29] Deon A., Menyaev Y. The complete set simulation of stochastic sequences without repeated and skipped elements. J. Univers. Comput. Sci., 2016, vol. 22, iss. 8, pp. 1023–1047.

[30] Deon A.F., Menyaev Yu.A. Complete factorial simulation of integer random number uniform sequences. Vestn. Mosk. Gos. Tekh. Univ. im. N.E. Baumana, Priborostr. [Herald of the Bauman Moscow State Tech. Univ., Instrum. Eng.], 2017, no. 5, pp. 132–149 (in Russ.). DOI: 10.18698/0236-3933-2017-5-132-149