Генератор равномерных вихревых последовательностей целых случайных величин без запоминающего массива

Вихревые генераторы целых случайных величин могут привлекать массивы для внутренней реализации операций вихревого сдвига. Такая технология дает отличные результаты, когда используются массивы случайных величин в последовательностях малого и среднего размера. Однако в современных генераторах наблюдается тенденция к достаточно длинным последовательностям, массивы которых могут потребовать всю оперативную память компьютера. В таких вариантах прежняя технология применения массивов непригодна, поскольку тогда в компьютере не остается места для самих программ и операционной системы. Предложена новая технология генерации вихревых последовательностей без использования конгруэнтно-вихревых массивов. Это позволяет создавать вихревые равномерные целые случайные последовательности произвольного размера, не занимая оперативную память компьютера. Результаты моделирования подтверждают, что получаемые случайные величины имеют абсолютно равномерное распределение во множестве уникальных последовательностей. Кроме того, комбинирование этого нового подхода с алгоритмом настройки вихревой генерации позволяет существенно увеличить длину создаваемых последовательностей без использования дополнительной оперативной памяти компьютера

Литература

[1] Shamir A. On the generation of cryptographically strong pseudorandom sequences // ACM TOCS. 1983. Vol. 1. Iss. 1. P. 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. P. 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. P. 47–58. DOI: 10.1145/2503778.2503784

[4] Eichenauer-Herrmann J., Niederreiter H. Digital inversive pseudorandom numbers // ACM TOMACS. 1994. Vol. 4. Iss. 4. P. 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. P. 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. P. 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. P. 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. P. 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. P. 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. P. 253–262. DOI: 10.1145/1993636.1993671

[13] Leva J.L. A fast normal random number generator // ACM TOMS. 1992. Vol. 18. Iss. 4. P. 449–453. DOI: 10.1145/138351.138364

[14] Applebaum B. Pseudorandom generators with long stretch and low locality from random local one-way functions // STO12 Proc. 44th Annual ACM Symposium on Theory of Computing. 2012. P. 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. P. 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. P. 2511–2514. DOI: 10.1145/1570256.1570353

[17] Real-time label-free embolus detection using in vivo photoacoustic flow cytometry / M.A. Juratly, Y.A. Menyaev, M. Sarimollaoglu, E.R. Siegel, et al. // PLoS One. 2016. Vol. 11. No. 5. Art. e0156269. DOI: 10.1371/journal.pone.0156269

[18] Bioinspired hemozoin nanocrystals as high contrast photoacoustic agents for ultrasensitive malaria diagnosis / K.A. Carey, Y.A. Menyaev, C. Cai, J.S. Stumhofer, et al. // J. Nanomed. Nanotechnol. 2016. Vol. 7. No. 3. P. 49. DOI: 10.4172/2157–7439.C1.031

[19] Photoacoustic flow cytometry for single sickle cell detection in vitro and in vivo / C. Cai, D.A. Nedosekin, Y.A. Menyaev, M. Sarimollaoglu, et al. // Anal. Cell. Pathol. 2016. Vol. 2016. Art. 2642361. DOI: 10.1155/2016/2642361 URL: https://www.hindawi.com/journals/acp/2016/2642361

[20] Optical clearing in photoacoustic flowcytometry / Y.A. Menyaev, D.A. Nedosekin, M. Sarimollaoglu, M.A. Juratli, et al. // Biomed. Opt. Express. 2013. Vol. 4. Iss. 12. P. 3030–3041. DOI: 10.1364/BOE.4.003030

[21] Preclinical photoacoustic models: application for ultrasensitive single cell malaria diagnosis in large vein and artery / Y.A. Menyaev, K.A. Carey, D.A. Nedosekin, M. Sarimollaoglu, et al. // Biomed. Opt. Express. 2016. Vol. 7. Iss. 9. P. 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. P. 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. P. 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. P. 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. P. 363–378. DOI: 10.3844/jcssp.2016.363.378

[27] Деон А.Ф., Меняев Ю.А. Генератор равномерных случайных величин по технологии полного вихревого массива // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2. С. 86–110. DOI: 10.18698/0236-3933-2017-2-86-110

[28] Saito M., Matsumoto M. SIMD-oriented fast Mersenne twister: a 128-bit pseudoran-dom number generator / A. Keller, S. Heinrich, H. Niederreiter, eds. Monte Carlo and quasi-Monte Carlo methods 2006. Springer, 2008. P. 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. P. 1023–1047.

[30] Деон А.Ф., Меняев Ю.А. Полное факториальное моделирование равномерных последовательностей целых случайных величин // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 5. С. 132–149. DOI: 10.18698/0236-3933-2017-5-132-149