Complete Factorial Simulation of Integer Random Number Uniform Sequences

Random sequences are widely used in theoretical and practical areas of interests in human and technical activities. An important part of these fields refers to the procedures of producing stochastic values. One direction adapts the sequenced generation of pseudorandom numbers and the other direction uses a complete set of all stochastic sequences. The first direction is well studied and traditionally applied in varies areas ranging from cryptography and technical systems to medical and biological trials. The second direction generally uses systems for preliminary universal testing. In this paper, we follow the second direction, where the underlying approaches in modern generators of random numbers are considered. In some of the modern random numbers generators the skipping and repeating random values may be found. We have formed the requirements that if followed help to solve the problems of skipping and repeating. Moreover, we propose novel algorithms based on factorial expansion which provide fast generation of such sequences. Finally, we describe advantages and disadvantages of findings of our research

References

[1] Leva J.L. A fast normal random number generator. TOMS, 1992, vol. 18, iss. 4, pp. 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, pp. 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, pp. 1775–1782. DOI: 10.1145/1389095.1389437 Available at: 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, pp. 2511–2514. DOI: 10.1145/1570256.1570353 Available at: 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, pp. 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, pp. 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, pp. 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, pp. 87–94. DOI: 10.1145/1283900.1283914

[9] Mandal K., Fan X., Gong G. Design and implementation of warbler family of lightweight pseudorandom 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, pp. 164–187. DOI: 10.1016/j.physa.2016.12.069

[11] 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., Cai Ch. Real-time label-free embolus detection using in vivo photoacoustic flow cytometry. PLoS One, 2016, vol. 11, no. 5, pp. e0156269. DOI: 10.1371/journal.pone.0156269 Available at: http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0156269

[12] Cai C., Carey K.A., Nedosekin D.A., Menyaev Y.A., Sarimollaoglu M., Galanzha E.I., Stumhofer J.S., Zharov V.P. In vivo photoacoustic flow cytometry for early malaria diagnosis. Cytometry A, 2016, vol. 89, iss. 6, pp. 531–542. DOI: 10.1002/cyto.a.22854

[13] Menyaev Yulian A., Carey Kai A., Nedosekin Dmitry A., Sarimollaoglu Mustafa, Galanzha Ekaterina I., Stumhofer Jason S., Zharov Vladimir 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

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

[15] Matsumoto M., Nishimura T. Mersenne twister: A 623-dimensionnally equidistributed uniform pseudorandom number generator. TOMACS, 1998, vol. 8, iss. 1, pp. 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, pp. 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, pp. 363–378. DOI: 10.3844/jcssp.2016.363.378

[18] 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.], 2017, no. 2, pp. 86–110 (in Russ.). 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, pp. 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, pp. 610–611. DOI: 10.1214/aoms/1177706645

[21] Nabebin A.A. Diskretnaya matematika [Discrete mathematics]. Moscow, Nauchnyy mir Publ., 2010. 512 p.

[22] Gnedenko B.V. Kurs teorii veroyatnostey [Theory of probability course]. Moscow, Editorial URSS Publ., 2005. 448 p.