List of random number generators

Random number generators are important in many kinds of technical applications, including physics, engineering or mathematical computer studies (e.g., Monte Carlo simulations), cryptography and gambling (on game servers).

This list includes many common types, regardless of quality.

Pseudorandom number generators (PRNGs)

Whenever using a pseudorandom number generator, keep in mind John von Neumann's dictum "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."[1]

The following algorithms are pseudorandom number generators.

Generator Date First proponents References Notes
Middle-square method 1946 J. von Neumann [2] In its original form, it is of poor quality and of historical interest only.
Lehmer generator 1951 D. H. Lehmer [3] One of the very earliest and most influential designs.
Linear congruential generator (LCG) 1958 W. E. Thomson; A. Rotenberg [4][5] A generalisation of the Lehmer generator and historically the most influential and studied generator.
Lagged Fibonacci generator (LFG) 1958 G. J. Mitchell and D. P. Moore [6]
Linear feedback shift register (LFSR) 1965 R. C. Tausworthe [7] A hugely influential design. Also called Tausworthe generators.
Wichmann–Hill generator 1982 B. A. Wichmann and D. I. Hill [8] A combination of three small LCGs, suited to 16-bit CPUs. Widely used in many programs, e.g. it is used in Excel 2003 and later versions for the function RAND[9] and it was the default generator in the language Python up to version 2.2.[10]
Rule 30 1983 S. Wolfram [11] Based on cellular automata.
Inversive congruential generator (ICG) 1986 J. Eichenauer and J. Lehn [12]
Park-Miller generator 1988 S. K. Park and K. W. Miller [13] A specific implementation of a Lehmer generator, widely used because built-in in the C and C++ languages as the function `minstd'.
ACORN generator (discovered 1984) 1989 R. S. Wikramaratna [14] [15] The Additive Congruential Random Number generator.

Simple to implement, fast, but not widely known. With appropriate initialisations, passes all current empirical test suites, and is formally proven to converge. Easy to extend for arbitrary period length and improved statistical performance over higher dimensions and with higher precision.

MIXMAX generator 1991 G. K. Savvidy and N. G. Ter-Arutyunyan-Savvidy [16] It is a member of the class of matrix linear congruential generator, a generalisation of LCG. The rationale behind the MIXMAX family of generators relies on results from ergodic theory and classical mechanics.
Add-with-carry (AWC) 1991 G. Marsaglia and A. Zaman [17] A modification of Lagged-Fibonacci generators.
Subtract-with-borrow (SWB) 1991 G. Marsaglia and A. Zaman [17] A modification of Lagged-Fibonacci generators. A SWB generator is the basis for the RANLUX generator,[18] widely used e.g. for particle physics simulations.
Maximally periodic reciprocals 1992 R. A. J. Matthews [19] A method with roots in number theory, although never used in practical applications.
KISS 1993 G. Marsaglia [20] Prototypical example of a combination generator.
Multiply-with-carry (MWC) 1994 G. Marsaglia; C. Koç [21][22]
Complementary-multiply-with-carry (CMWC) 1997 R. Couture and P. L’Ecuyer [23]
Mersenne Twister (MT) 1998 M. Matsumoto and T. Nishimura [24] Closely related with LFSRs. In its MT19937 implementation is probably the most commonly used modern PRNG. Default generator in R and the Python language starting from version 2.3.
Xorshift 2003 G. Marsaglia [25] It is a very fast sub-type of LFSR generators. Marsaglia also suggested as an improvement the xorwow generator, in which the output of a xorshift generator is added with a Weyl sequence. The xorwow generator is the default generator in the CURAND library of the nVidia CUDA application programming interface for graphics processing units.
Well equidistributed long-period linear (WELL) 2006 F. Panneton, P. L'Ecuyer and M. Matsumoto [26] A LFSR closely related with Mersenne Twister, aiming at remedying some of its shortcomings.
A small noncryptographic PRNG (JSF) 2007 Bob Jenkins [27]
Advanced Randomization System (ARS) 2011 J. Salmon, M. Moraes, R. Dror and D. Shaw [28] A simplified version of the AES block cipher, leading to very fast performance on system supporting the AES-NI.
Threefry 2011 J. Salmon, M. Moraes, R. Dror and D. Shaw [28] A simplified version of the Threefish block cipher, suitable for GPU implementations.
Philox 2011 J. Salmon, M. Moraes, R. Dror and D. Shaw [28] A simplification and modification of the block cipher Threefish with the addition of an S-box.
SplitMix 2014 G. L. Steele, D. Lea and C. H. Flood [29] Based upon the final mixing function of MurmurHash3. Included in Java Development Kit 8 and above.
Permuted Congruential Generator (PCG) 2014 M. E. O'Neill [30] A modification of LCG.
Random Cycle Bit Generator (RCB) 2016 R. Cookman [31] RCB is described as a bit pattern generator made to overcome some of the shortcomings with Mersenne Twister and short periods/bit length restriction of shift/modulo generators.
Middle Square Weyl Sequence PRNG 2017 B. Widynski [32] A variation on John von Neumann's original middle-square method, this generator may be the fastest PRNG that passes all the statistical tests.
Xoroshiro128+ 2018 D. Blackman, S. Vigna [33] A modification of Marsaglia's Xorshift generators, one of the fastest generators on modern 64-bit CPUs. Related generators include xoroshiro128**, xoshiro256+ and xoshiro256**.
64-bit MELG 2018 S. Harase, T. Kimoto [34] An implementation of 64-bit maximally equidistributed F2-linear generators with Mersenne prime period.
Squares RNG 2020 B. Widynski [35] A counter-based version of Middle Square Weyl Sequence PRNG. According to the author this appears to be one of the fastest counter-based generators.

Cryptographic algorithms

Cipher algorithms and cryptographic hashes can be used as very high-quality pseudorandom number generators. However, generally they are considerably slower (typically by a factor 2-10) than fast, non-cryptographic random number generators.

These include:

A few cryptographically secure pseudorandom number generators do not rely on cipher algorithms but try to link mathematically the difficulty of distinguishing their output from a `true' random stream to a computationally difficult problem. These approaches are theoretically important but are too slow to be practical in most applications. They include:

Random number generators that use external entropy

These approaches combine a pseudo-random number generator (often in the form of a block or stream cipher) with an external source of randomness (e.g., mouse movements, delay between keyboard presses etc.).

Random number servers

The following (non-exhaustive) list of websites claim to provide random numbers generated from a truly random source, with many providing additional randomisation services:

Well-known PRNG APIs

See also

References
  1. Von Neumann, John (1951). "Various techniques used in connection with random digits" (PDF). National Bureau of Standards Applied Mathematics Series. 12: 36–38.
  2. Some of von Neumann's 1949 papers were printed only in 1951. John von Neumann, “Various techniques used in connection with random digits,” in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol. 12 (Washington, D.C.: U.S. Government Printing Office, 1951): pp. 36-38.
  3. Lehmer, Derrick H. (1951). "Mathematical methods in large-scale computing units". Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery: 141–146.
  4. Thomson, W. E. (1958). "A Modified Congruence Method of Generating Pseudo-random Numbers". The Computer Journal. 1 (2): 83. doi:10.1093/comjnl/1.2.83.
  5. Rotenberg, A. (1960). "A New Pseudo-Random Number Generator". Journal of the ACM. 7 (1): 75–77. doi:10.1145/321008.321019.
  6. D. E. Knuth, The Art of Computer Programming, Vol. 2 Seminumerical Algorithms, 3rd ed., Addison Wesley Longman (1998); See pag. 27.
  7. Tausworthe, R. C. (1965). "Random Numbers Generated by Linear Recurrence Modulo Two" (PDF). Mathematics of Computation. 19 (90): 201–209. doi:10.1090/S0025-5718-1965-0184406-1.
  8. Wichmann, Brian A.; Hill, David I. (1982). "Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Series C (Applied Statistics). 31 (2): 188–190. doi:10.2307/2347988. JSTOR 2347988.
  9. "Microsoft Support - Description of the RAND function in Excel". Apr 17, 2018.
  10. "Documentation » The Python Standard Library » 9. Numeric and Mathematical Modules » 9.6. random — Generate pseudo-random numbers".
  11. Wolfram, S. (1983). "Statistical mechanics of cellular automata". Rev. Mod. Phys. 55 (3): 601–644. Bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601.
  12. Eichenauer, Jürgen; Lehn, Jürgen (1986). "A nonlinear congruential pseudorandom number generator". Statistische Hefte. 27: 315–326. doi:10.1007/BF02932576.
  13. Park, Stephen K.; Miller, Keith W. (1988). "Random Number Generators: Good Ones Are Hard To Find" (PDF). Communications of the ACM. 31 (10): 1192–1201. doi:10.1145/63039.63042.
  14. Wikramaratna, R. S. (1989). "ACORN — A new method for generating sequences of uniformly distributed Pseudo-random Numbers". Journal of Computational Physics. 83 (1): 16–31. Bibcode:1989JCoPh..83...16W. doi:10.1016/0021-9991(89)90221-0.
  15. Wikramaratna, R.S. Theoretical and empirical convergence results for additive congruential random number generators, Journal of Computational and Applied Mathematics (2009), doi:10.1016/j.cam.2009.10.015
  16. Savvidy, G.K; Ter-Arutyunyan-Savvidy, N.G (1991). "On the Monte Carlo simulation of physical systems". Journal of Computational Physics. 97 (2): 566. Bibcode:1991JCoPh..97..566S. doi:10.1016/0021-9991(91)90015-D.
  17. George, Marsaglia; Zaman, Arif (1991). "A new class of random number generators". Annals of Applied Probability. 1 (3): 462–480. doi:10.1214/aoap/1177005878.
  18. Martin, Lüscher (1994). "A portable high-quality random number generator for lattice field theory simulations". Computer Physics Communications. 79 (1): 100–110. arXiv:hep-lat/9309020. Bibcode:1994CoPhC..79..100L. doi:10.1016/0010-4655(94)90232-1.
  19. Matthews, Robert A. J. (1992). "Maximally periodic reciprocals". Bull. Inst. Math. Appl. 28: 147–148.
  20. Marsaglia, George; Zaman, Arif (1993). "The KISS generator". Technical Report, Department of Statistics, Florida State University, Tallahassee, FL, USA.
  21. Post by George Marsaglia on the newsgroup sci.stat.math dated 1 August 2018 with title 'Yet another RNG'.
  22. Koç, Cemal (1995). "Recurring-with-Carry Sequences". Journal of Applied Probability. 32 (4): 966–971. doi:10.2307/3215210. JSTOR 3215210.
  23. Couture, Raymond; L'Ecuyer, Pierre (1997). "Distribution properties of multiply-with-carry random number generators" (PDF). Mathematics of Computation. 66 Number. 218 (218): 591–607. Bibcode:1997MaCom..66..591C. doi:10.1090/S0025-5718-97-00827-2.
  24. Matsumoto, M.; Nishimura, T. (1998). "MersenneTwister: A623-dimensionally Equidistributed Uniform Pseudo-Random Number Generator". ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995.
  25. Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14). doi:10.18637/jss.v008.i14.
  26. Panneton, François O.; l'Ecuyer, Pierre; Matsumoto, Pierre (March 2006). "Improved long-period generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. CiteSeerX 10.1.1.73.5499. doi:10.1145/1132973.1132974.
  27. Jenkins, Bob (2009). "A small noncryptographic PRNG".
  28. Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Parallel random numbers: as easy as 1, 2, 3". Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16. doi:10.1145/2063384.2063405.
  29. Steele, Guy L. Jr.; Lea, Doug; Flood, Christine H. (2014). "Fast splittable pseudorandom number generators" (PDF). OOPSLA '14 Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications.
  30. O'Neill, Melissa E. (2014). "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation" (PDF). Technical Report.
  31. Cookman, Richard (2016). "random cycle bit generator (rcb_generator)". Technical Report.
  32. Widynski, Bernard (2017). "Middle Square Weyl Sequence RNG". arXiv:1704.00358v5 [cs.CR].
  33. Blackman, David; Vigna, Sebastiano (2018). "Scrambled Linear Pseudorandom Generators". arXiv:1805.01407 [cs.DS].
  34. Harase, S.; Kimoto, T. (2018). "Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period". ACM Transactions on Mathematical Software. 44 (3): 30:1–30:11. arXiv:1505.06582. doi:10.1145/3159444.
  35. Widynski, Bernard (2020). "Squares: A Fast Counter-Based RNG". arXiv:2004.06278v3 [cs.DS].
  36. True Random Number Generator using Corona Discharge: Indian Patent Office. Patent Application Number: 201821026766
  37. Thomas Symul; Syed M. Assad; Ping Koy Lam (2011-06-07), "Real time demonstration of high bitrate quantum random number generation with coherent laser light", Applied Physics Letters, 98 (23): 231103, arXiv:1107.4438, Bibcode:2011ApPhL..98w1103S, doi:10.1063/1.3597793
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.