
related topics 
{math, number, function} 
{system, computer, user} 
{rate, high, increase} 
{law, state, case} 
{work, book, publish} 

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG)^{[1]}, is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom numbers are important in practice for simulations (e.g., of physical systems with the Monte Carlo method), and are central in the practice of cryptography and procedural generation. Common classes of these algorithms are linear congruential generators, Lagged Fibonacci generators, linear feedback shift registers, feedback with carry shift registers, and generalised feedback shift registers. Recent instances of pseudorandom algorithms include Blum Blum Shub, Fortuna, and the Mersenne twister.
Careful mathematical analysis is required to have any confidence a PRNG generates numbers that are sufficiently "random" to suit the intended use. Robert R. Coveyou of Oak Ridge National Laboratory once titled an article, "The generation of random numbers is too important to be left to chance."^{[2]} As John von Neumann joked, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."^{[3]}
Contents
Periodicity
A PRNG can be started from an arbitrary starting state using a seed state. It will always produce the same sequence thereafter when initialized with that state. The maximum length of the sequence before it begins to repeat is determined by the size of the state, measured in bits. However, since the length of the maximum period potentially doubles with each bit of 'state' added, it is easy to build PRNGs with periods long enough for many practical applications.
Full article ▸


related documents 
Integer (computer science) 
Sheffer stroke 
Minimum spanning tree 
Haskell (programming language) 
A* search algorithm 
Associative array 
Parameter 
Banach space 
Topological vector space 
Optimization (mathematics) 
Bspline 
Document Type Definition 
Normal space 
Universal quantification 
Character encodings in HTML 
Partially ordered set 
Graph theory 
Ordered pair 
Free group 
Geometric series 
Expander graph 
Stokes' theorem 
Algebraically closed field 
Net (mathematics) 
LL parser 
Henri Lebesgue 
Knapsack problem 
Direct product 
NP (complexity) 
Integer factorization 
