list of random number generators
{{Short description|none}}
{{use dmy dates|date=February 2025}}
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 or applicability to a given use case.
Pseudorandom number generators (PRNGs)
The following algorithms are pseudorandom number generators.
| style="text-align: center;" class="wikitable sortable"
!rowspan=1|Generator !rowspan=1|Date !rowspan=1|First proponents !rowspan=1|References !rowspan=1|Notes |
| {{rh}}|Middle-square method
|1946 |In its original form, it is of poor quality and of historical interest only. |
| {{rh}}|Lehmer generator
|1951 |One of the very earliest and most influential designs. |
| {{rh}}|Linear congruential generator (LCG)
|1958 |W. E. Thomson; A. Rotenberg |{{Cite journal|last=Thomson|first=W. E.|date=1958|title=A Modified Congruence Method of Generating Pseudo-random Numbers|journal=The Computer Journal|volume=1|issue=2|pages=83|doi=10.1093/comjnl/1.2.83|doi-access=free}}{{Cite journal|last=Rotenberg|first=A.|date=1960|title=A New Pseudo-Random Number Generator|journal=Journal of the ACM|volume=7|issue=1|pages=75–77|doi=10.1145/321008.321019|s2cid=16770825 |doi-access=free}} |A generalisation of the Lehmer generator and historically the most influential and studied generator. |
| {{rh}}|Lagged Fibonacci generator (LFG)
|1958 |G. J. Mitchell and D. P. Moore | |
| {{rh}}|Linear-feedback shift register (LFSR)
|1965 |R. C. Tausworthe |A hugely influential design. Also called Tausworthe generators. |
| {{rh}}|Wichmann–Hill generator
|1982 |B. A. Wichmann and D. I. Hill |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 Excel function RAND{{Cite web|url=https://support.microsoft.com/en-us/help/828795/description-of-the-rand-function-in-excel|title=Microsoft Support - Description of the RAND function in Excel|date=Apr 17, 2018}} and it was the default generator in the language Python up to version 2.2.{{Cite web|url=https://docs.python.org/2/library/random.html|title=Documentation » The Python Standard Library » 9. Numeric and Mathematical Modules » 9.6. random — Generate pseudo-random numbers}} |
| {{rh}}|Rule 30
|1983 |S. Wolfram |Based on cellular automata. |
| {{rh}}|Inversive congruential generator (ICG)
|1986 |J. Eichenauer and J. Lehn | |
| {{rh}}|Blum Blum Shub
|1986 |M. Blum, L. Blum and M. Shub |Blum-Blum-Shub is a PRNG algorithm that is considered cryptographically secure. Its base is based on prime numbers. |
| {{rh}}|Park-Miller generator
|1988 |S. K. Park and K. W. Miller |A specific implementation of a Lehmer generator, widely used because it is included in C++ as the function |
| {{rh}}|ACORN generator
|1989 (discovered 1984) |R. S. Wikramaratna |{{Cite journal|last=Wikramaratna|first=R. S.|date=1989|title=ACORN — A new method for generating sequences of uniformly distributed Pseudo-random Numbers|journal=Journal of Computational Physics|volume=83|issue=1|pages=16–31|doi=10.1016/0021-9991(89)90221-0|bibcode=1989JCoPh..83...16W}}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}} |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. |
| {{rh}}|MIXMAX generator
|1991 |G. K. Savvidy and N. G. Ter-Arutyunyan-Savvidy |{{cite journal |doi=10.1016/0021-9991(91)90015-D|title=On the Monte Carlo simulation of physical systems|journal=Journal of Computational Physics|volume=97|issue=2|pages=566|year=1991|last1=Savvidy|first1=G.K|last2=Ter-Arutyunyan-Savvidy|first2=N.G|bibcode=1991JCoPh..97..566S}} |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. |
| {{rh}}|Add-with-carry (AWC)
|1991 |G. Marsaglia and A. Zaman |A modification of Lagged-Fibonacci generators. |
| {{rh}}|Subtract-with-borrow (SWB)
|1991 |G. Marsaglia and A. Zaman | A modification of Lagged-Fibonacci generators. A SWB generator is the basis for the RANLUX generator,{{Cite journal|last=Martin|first=Lüscher|date=1994|title=A portable high-quality random number generator for lattice field theory simulations|journal=Computer Physics Communications|volume= 79| issue = 1|pages=100–110|doi=10.1016/0010-4655(94)90232-1|arxiv=hep-lat/9309020|bibcode=1994CoPhC..79..100L|s2cid=17608961 }} widely used e.g. for particle physics simulations. |
| {{rh}}|Maximally periodic reciprocals
|1992 |R. A. J. Matthews |A method with roots in number theory, although never used in practical applications. |
| {{rh}}|KISS
|1993 |G. Marsaglia |Prototypical example of a combination generator. |
| {{rh}}|Multiply-with-carry (MWC)
|1994 |G. Marsaglia; C. Koç |Post by George Marsaglia on the newsgroup sci.stat.math dated 1 August 2018 with title '[https://groups.google.com/forum/#!searchin/sci.stat.math/Yet$20another$20rng%7Csort:date/sci.stat.math/p7aLW3TsJys/QGb1kti6kN0J Yet another RNG]'.{{Cite journal|last=Koç|first=Cemal|date=1995|title=Recurring-with-Carry Sequences|journal=Journal of Applied Probability|volume= 32|issue=4|pages=966–971|jstor=3215210|doi=10.2307/3215210|s2cid=123798320 }} | |
| {{rh}}|Complementary-multiply-with-carry (CMWC)
|1997 |R. Couture and P. L’Ecuyer | |
| {{rh}}|Mersenne Twister (MT)
|1998 |M. Matsumoto and T. Nishimura |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. |
| {{rh}}|Xorshift
|2003 |G. Marsaglia | first=George | last=Marsaglia | author-link=George Marsaglia | title=Xorshift RNGs | journal=Journal of Statistical Software | volume=8 | issue=14 | date=July 2003 | doi=10.18637/jss.v008.i14| doi-access=free }} |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. |
| {{rh}}|Well equidistributed long-period linear (WELL)
|2006 |F. Panneton, P. L'Ecuyer and M. Matsumoto |A LFSR closely related with Mersenne Twister, aiming at remedying some of its shortcomings. |
| {{rh}}|A small noncryptographic PRNG (JSF)
|2007 |Bob Jenkins | |
| {{rh}}|Small Fast Chaotic PRNG (SFC)
|2010 |Chris Doty-Humphrey |{{Cite web |title=RNG_engines.txt |url=https://pracrand.sourceforge.net/RNG_engines.txt |last=Doty-Humphrey |first=Chris |url-status=live |archive-url=https://web.archive.org/web/20241217212817/https://pracrand.sourceforge.net/RNG_engines.txt |archive-date=2024-12-17 |access-date=2025-02-13 |website=Practically Random}}{{Cite web |title=SFC64 Small Fast Chaotic PRNG |url=https://numpy.org/doc/2.2/reference/random/bit_generators/sfc64.html |url-status=live |archive-url=https://web.archive.org/web/20250213181906/https://numpy.org/doc/2.2/reference/random/bit_generators/sfc64.html |archive-date=2025-02-13 |access-date=2025-02-13 |website=NumPy v2.2 Manual}} | |
| {{rh}}|Advanced Randomization System (ARS)
|2011 |J. Salmon, M. Moraes, R. Dror and D. Shaw |A simplified version of the AES block cipher, leading to very fast performance on systems supporting the AES-NI. |
| {{rh}}|Threefry
|2011 |J. Salmon, M. Moraes, R. Dror and D. Shaw |A simplified version of the Threefish block cipher, suitable for GPU implementations. |
| {{rh}}|Philox
|2011 |J. Salmon, M. Moraes, R. Dror and D. Shaw |A simplification and modification of the block cipher Threefish with the addition of an S-box. |
| {{rh}}|WELLDOC
|2013 |L. Balkova, M. Bucci, A. de Luca, J. Hladky, S. Puzynina |Aperiodic pseudorandom number generators based on infinite words technique. |
| {{rh}}|SplitMix
|2014 |G. L. Steele, D. Lea and C. H. Flood |Based upon the final mixing function of MurmurHash3. Included in Java Development Kit 8 and above. |
| {{rh}}|Permuted Congruential Generator (PCG)
|2014 |M. E. O'Neill |A modification of LCG. |
| {{rh}}|Random Cycle Bit Generator (RCB)
|2016 |R. Cookman |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. |
| {{rh}}|Middle-Square Weyl Sequence RNG (see also middle-square method)
|2017 |B. Widynski |{{cite arXiv |last=Widynski |first=Bernard|eprint=1704.00358 |title=Middle-Square Weyl Sequence RNG|class=cs.CR |year=2017 }}{{cite book | title = Random Numbers and Computers | last = Kneusel | first = Ron | publisher = Springer | year = 2018 | edition = 1 | pages = 13–14 | isbn = 9783319776972 |url=https://books.google.com/books?id=7ZJUDwAAQBAJ}} |A variation on John von Neumann's original middle-square method, this generator may be the fastest RNG that passes all the statistical tests. |
| {{rh}}|xorshiftr+
|2018 |U. C. Çabuk, Ö. Aydın, and G. Dalkılıç |A modification of xorshift+. Significantly faster than the predecessor and passes all tests in the BigCrush suite. |
| {{rh}}|Xoroshiro128+
|2018 |D. Blackman, S. Vigna |A modification of Marsaglia's Xorshift generators, one of the fastest generators on modern 64-bit CPUs. Related generators include xoroshiro128**, xoshiro256+ and xoshiro256**. |
| {{rh}}|64-bit MELG (MELG-64)
|2018 |S. Harase, T. Kimoto |An implementation of 64-bit maximally equidistributed F2-linear generators with Mersenne prime period. |
| {{rh}}|Squares RNG
|2020 |B. Widynski |A counter-based version of Middle-Square Weyl Sequence RNG. Similar to Philox in design but significantly faster. |
| {{rh}}|Collatz-Weyl Generators
|2023 |Tomasz R. Działa |A class of chaotic counter-based generators applying a broad class of non-invertible generalized Collatz mappings and Weyl sequences, enabling the generation of multiple independent streams. Leveraging 128-bit arithmetic allows for a highly efficient implementation, especially on modern 64-bit architectures. |
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:
- Stream ciphers. Popular choices are Salsa20 or ChaCha (often with the number of rounds reduced to 8 for speed), ISAAC, HC-128 and RC4.
- Block ciphers in counter mode. Common choices are AES (which is very fast on systems supporting it in hardware), TwoFish, Serpent and Camellia.
- Cryptographic hash functions
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:
- Blum–Micali algorithm (1984)
- Blum Blum Shub (1986)
- Naor–Reingold pseudorandom function (1997)
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.).
/dev/random– Unix-like systems- CryptGenRandom – Microsoft Windows
- Fortuna
- RDRAND instructions (called Intel Secure Key by Intel), available in Intel x86 CPUs since 2012. They use the AES generator built into the CPU, reseeding it periodically.
- True Random Number Generator using Corona Discharge.True Random Number Generator using Corona Discharge: Indian Patent Office.
Patent Application Number: 201821026766
See also
- Diceware
- Diehard tests – statistical test suite for random number generators
- Non-uniform random variate generation
- Hardware random number generator
- Random number generator attack
- Randomness
- TestU01 – statistical test suite for random number generators
References
{{reflist}}
External links
- [http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf SP800-90 series on Random Number Generation], NIST
- [https://www.gnu.org/software/gsl/manual/html_node/Random-Number-Generation.html Random Number Generation in the GNU Scientific Library Reference Manual]
- [http://www.nag.com/numeric/FL/nagdoc_fl24/html/G05/g05conts.html Random Number Generation Routines in the NAG Numerical Library]
- [https://lomont.org/papers/2008/Lomont_PRNG_2008.pdf Chris Lomont's overview of PRNGs, including a good implementation of the WELL512 algorithm]
- [http://bytesandpieces.org/?p=368 Source code to read data from a TrueRNG V2 hardware TRNG]
{{DEFAULTSORT:Random number generators}}
Category:Computing-related lists