PRNGs maintain a state variable, a bitwise superset of the random number, initialized by a random seed - a constant for the same sequence each time, i.e. for Zobrist keys, otherwise, something like system time to produce varying pseudo randoms. Each call of the PRNG routine performs certain operations or bit-twiddling on that state, leaving the next pseudo random number. For various applications more or less important features are randomness, resolution, (uniform) distribution, and periodicity - topic of various randomness tests - and further performance, and portability.

A common method used in many library functions, such as C/C++ rand() is the linear congruential generator based on multiply, add, modulo with integers, where some past implementations had serious shortcomings in the randomness, distribution and period of the sequence ^{[4]}. Due to such issues in rand() implementations, where lower bits are less random than higher bits, it is recommended not to use modulo X to reduce the integer range from RAND_MAX to X, but division by (RAND_MAX div X) ^{[5]} - or to use C++11's random number generation facilities to replace rand ^{[6]}.

George Marsaglia (1985). A Current View of Random Number Generators. Proceedings, Computer Science and Statistics: 16th Symposium on the Interface, Elsevier

^ "In the past, some implementations of rand() have had serious shortcomings in the randomness, distribution and period of the sequence produced (in one well-known example, the low-order bit simply alternated between 1 and 0 between calls) rand() is not recommended for serious random-number generation needs, like cryptography. It is recommended to use C++11's random number generation facilities to replace rand()." rand - cppreference.com

Home * Programming * Algorithms * Pseudorandom Number GeneratorPseudorandom Number Generator(PRNG),an algorithmic gambling device for generating pseudorandom numbers, a deterministic sequence of numbers which appear to be random with the property of reproducibility. They are useful in simulation, sampling, computer programming, decision making, cryptography, aesthetics and recreation

^{[1]}- in computer chess, beside randomization of game playing, primarily used to generate keys for Zobrist hashing.Games of chance, such as Backgammon and EinStein würfelt nicht! require PRNGs for rolling a dice. Chess and game playing programs use PRNGs to randomly choose one of several possible moves of a position from an opening book, or use random fluctuations in learning and automated tuning tasks. Game playing programs performing a Monte-Carlo Tree Search, use random playouts in their simulation phase. Don Beal and Martin C. Smith demonstrated that deeper search with random leaf values in chess yields to better play, with some interesting insights in minimax search and implications for designing and testing evaluation terms

^{[2]}.^{[3]}## Table of Contents

## Methods

PRNGs maintain a state variable, a bitwise superset of the random number, initialized by a random seed - a constant for the same sequence each time, i.e. for Zobrist keys, otherwise, something like system time to produce varying pseudo randoms. Each call of the PRNG routine performs certain operations or bit-twiddling on that state, leaving the next pseudo random number. For various applications more or less important features are randomness, resolution, (uniform) distribution, and periodicity - topic of various randomness tests - and further performance, and portability.A common method used in many library functions, such as C/C++ rand() is the linear congruential generator based on multiply, add, modulo with integers, where some past implementations had serious shortcomings in the randomness, distribution and period of the sequence

^{[4]}. Due to such issues in rand() implementations, where lower bits are less random than higher bits, it is recommended not to use modulo X to reduce the integer range from RAND_MAX to X, but division by (RAND_MAX div X)^{[5]}- or to use C++11's random number generation facilities to replace rand^{[6]}.Zobrist hashing with about 12*64 keys has less issues with randomness and period, but with distribution, and requires linear independence so that a small subset of all keys doesn't xor to zero. Despite selected hard-coded random constants used at compile time, many programs use an own PRNG based on recurrence relation in GF(2) such as Mersenne Twister or Xorshift. Stockfish (since 2.0) uses an implementation by Heinz van Saanen based on Bob Jenkins' RKISS, a member of George Marsaglia's Xorshift familly. Amy by Thorsten Greiner

^{[7]}uses an implementation of Agner Fog's RANROT B3^{[8]}, also recommended by Stefan Meyer-Kahlen as used in Shredder^{[9]}. Arasan 20.x switched to C++11 random number support using std::mt19937_64^{[10]}^{[11]}## Applications

## See also

## Selected Publications

## 1950 ...

1951).Mathematical methods in large-scale computing units. Proceedings of a 2nd Symposium on Large Scale Digital Computing Machinery, 1949, Harvard University Press, pp. 141–1461955).A Million Random Digits with 100,000 Normal Deviates. pdf, online## 1960 ...

1963).Various techniques used in connection with random digits. von Neumann's Collected Works, Vol. 5, Pergamon Press, pdf1965).Uniform Random Number Generators. Journal of the ACM, Vol. 12, No. 11969).The Art of Computer Programming (TAOCP) - Volume 2 - Seminumerical Algorithms. Chapter 3 – Random numbers, 1st edition## 1970 ...

1970).Pseudo-random numbers. Computing, Vol. 6, No. 11972).The Structure of Linear Congruential Sequences. in S. K. Zaremba (ed.)Applications of Number Theory to Numerical Analysis. Academic Press1973).A combinatorial method for the generation of normally distributed random numbers. Computing, Vol. 11, No. 2## 1980 ...

1981).A Very Fast Shift-Register Sequence Random Number Generator. Journal of Computational Physics, Vol. 40, No. 21985).A Current View of Random Number Generators. Proceedings, Computer Science and Statistics: 16th Symposium on the Interface, Elsevier1988).Efficient and Portable combined random number generators. Communications of the ACM, Vol. 31, No. 6## 1990 ...

1990).Random numbers for simulation. Communications of the ACM, Vol. 33, No. 101992).Numerical Recipes in C: The Art of Scientific Computing, 2nd edition. Chapter 7. Random Numbers1992).Distributed Random Number Generation. Journal of Functional Programming, Vol. 2, No. 2, pdf1997).The Art of Computer Programming (TAOCP) - Volume 2 - Seminumerical Algorithms. Chapter 3 – Random numbers, 3rd edition1997).Cycle parity random number generators, and a general random number library. Ph.D. thesis, Rensselaer Polytechnic Institute, advisor Mukkai S. Krishnamoorthy.1998).Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, pdf preprint1998).Programowe generatory liczb pseudolosowych. Znacie - to posłuchajcie.Software 11/1998 (Polish)## 2000 ...

2000).A collection of classical pseudorandom number generators with linear structures - advanced version.2001).Chaotic Random Number Generators with Random Cycle Lengths. pdf2002).Random number generators. Journal of Modern Applied Statistical Methods, Vol. 2, No. 2.2003).Xorshift RNGs. Journal of Statistical Software, Vol. 8, No. 142004).Random Number Generation. pdf2007).Numerical Recipes. The Art of Scientific Computing, 3rd edition. (C++ code)## 2010 ...

2015).When Completely Random is Just not Random Enough. AI Factory, February 2015## Forum Posts

## 1982 ...

## 1990 ...

Re: Hash tables - Clash!!! What happens next? by Jonathan Schaeffer, March 17, 1994

## 1995 ...

## 2000 ...

Re: random book moves/ random generator by Thorsten Greiner, CCC, January 13, 2000

Re: About random numbers and hashing by Sven Reichard, CCC, December 05, 2001

## 2005 ...

## 2010 ...

^{[12]}## 2015 ...

## External Links

## Randomness

## Methods

Lehmer random number generator from Wikipedia

Park-Miller-Carta Pseudo-Random Number Generators

RANDU from Wikipedia

Mersenne Twister - Home Page

## Language Support

## Basic

## C

## C++

## C#

## D

## Fortran

## Go

## Java

## Lisp

## Pascal

## Python

## Tests

## Misc

## References

1997).The Art of Computer Programming (TAOCP) - Volume 2 - Seminumerical Algorithms. Chapter 3 – Random numbers1994).Random Evaluations in Chess. Advances in Computer Chess 72002).Pompeji. Hirmer Verlag, Munich, ISBN: 3-7774-9530-1, p. 146, Wikimedia Commons, History of randomness from Wikipedia2001).Chaotic Random Number Generators with Random Cycle Lengths. pdf## What links here?

Up one Level