Полное факториальное моделирование равномерных последовательностей целых случайных величин

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

Литература

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

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

[3] White D.R., Clark J., Jacob J., Poulding S.M. Searching for resource-efficient programs: Low-power pseudorandom number generators // Proc. 10th Annual Conf. on Genetic and Evolutionary Computation. New York, ACM, 2008. P. 1775–1782. DOI: 10.1145/1389095.1389437 URL: http://dl.acm.org/citation.cfm?doid=1389095.1389437

[4] Langdon W.B. A fast high quality pseudo random number generator for nVidia CUDA // Proc. 11th Annual Conf. on Genetic and Evolutionary Computation. New York, ACM, 2009. P. 2511–2514. DOI: 10.1145/1570256.1570353 URL: http://dl.acm.org/citation.cfm?doid=1570256.1570353

[5] Deon A.F., Menyaev Y.A. The complete set simulation of stochastic sequences without repeated and skipped elements // Journal of Universal Computer Science. 2016. Vol. 22. Iss. 8. P. 1023–1047. DOI: 10.3217/jucs-022-08-1023

[6] 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. New York, ACM, 2009. P. 112–120. DOI: 10.1145/1653662.1653677

[7] Claessen K., Palka M.H. Splittable pseudorandom number generators using cryptographic hashing // Proc. 2013 ACM SIGPLAN Symp. on Haskell. New York, ACM, 2013. P. 47–58. DOI: 10.1145/2503778.2503784

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

[9] Mandal K., Fan X., Gong G. Design and implementation of warbler family of lightweight pseudo-random number generators for smart devices // TECS. 2016. Vol. 15. Iss. 1. Article No. 1. DOI: 10.1145/2808230

[10] 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

[11] Juratly M.A., Menyaev Y.A., Sarimollaoglu M., et al. Real-time label-free embolus detection using in vivo photoacoustic flow cytometry // PLoS One. 2016. Vol. 11. No. 5. P. e0156269. DOI: 10.1371/journal.pone.0156269 URL: http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0156269

[12] Cai C., Carey K.A., Nedosekin D.A., et al. In vivo photoacoustic flow cytometry for early malaria diagnosis // Cytometry A. 2016. Vol. 89. Iss. 6. P. 531–542. DOI: 10.1002/cyto.a.22854

[13] Menyaev Y.A., Carey K.A., Nedosekin D.A., et al. Preclinical photoacoustic models: Application for ultrasensitive single cell malaria diagnosis in large vein and artery // Biomed. Opt. Express. 2016. Vol. 7. Iss. 9. P. 3643–3658. DOI: 10.1364/BOE.7.003643

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

[15] Matsumoto M., Nishimura T. Mersenne twister: A 623-dimensionnally equidistributed uniform pseudorandom number generator // TOMACS. 1998. Vol. 8. Iss. 1. P. 3–30. DOI: 10.1145/272991.272995

[16] Matsumoto M., Saito M., Haramoto H., Nishimura T. Pseudorandom number generation: Impossibility and compromise // Journal of Universal Computer Science. 2016. Vol. 12. Iss. 6. P. 672–690. DOI: 10.3217/jucs-012-06-0672

[17] Deon A., Menyaev Y. Parametrical tuning of twisting generators // Journal of Computer Science. 2016. Vol. 12. Iss. 8. P. 363–378. DOI: 10.3844/jcssp.2016.363.378

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

[19] Deon A.F., Menyaev Y.A. Twister generator of arbitrary uniform sequences // Journal of Universal Computer Science. 2017. Vol. 23. Iss. 4. P. 353–384.

[20] Box G.E.P., Muller M.E. A note on the generation of random normal deviates // The Annals of Mathematical Statistics. 1958. Vol. 29. No. 2. P. 610–611. DOI: 10.1214/aoms/1177706645

[21] Набебин А.А. Дискретная математика. М.: Научный мир, 2010. 512 с.

[22] Гнеденко Б.В. Курс теории вероятностей. М.: Едиториал УРСС, 2005. 448 с.