Pseudorandom number generator

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)
B-spline
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