Linear congruential generator

related topics
{math, number, function}
{system, computer, user}
{rate, high, increase}
{food, make, wine}
{@card@, make, design}

A Linear Congruential Generator (LCG) represents one of the oldest and best-known pseudorandom number generator algorithms.[1] The theory behind them is easy to understand, and they are easily implemented and fast.

The generator is defined by the recurrence relation:

where Xn is the sequence of pseudorandom values, and

are integer constants that specify the generator.

Contents

Period length

The period of a general LCG is at most m, and for some choices of a much less than that. Provided that c is nonzero, the LCG will have a full period for all seed values if and only if:[2]

While LCGs are capable of producing decent pseudorandom numbers, this is extremely sensitive to the choice of the parameters c, m, and a.

Historically, poor choices had led to ineffective implementations of LCGs. A particularly illustrative example of this is RANDU which was widely used in the early 1970s and lead to many results which are currently being questioned because of the use of this poor LCG.[3]

Parameters in common use

The most efficient LCGs have an m equal to a power of 2, most often m = 232 or m = 264, because this allows the modulus operation to be computed by merely truncating all but the rightmost 32 or 64 bits. The following table lists the parameters of LCGs in common use, including built-in rand() functions in runtime libraries of various compilers.

[citation needed]

As shown above, LCG's do not always use all of the bits in the values they produce. The Java implementation produces 48 bits with each iteration but only returns the 32 most significant bits from these values. This is because the higher-order bits have longer periods than the lower order bits (see below). LCG's that use this technique produce much better values than those that do not.

Advantages and disadvantages of LCGs

LCGs are fast and require minimal memory (typically 32 or 64 bits) to retain state. This makes them valuable for simulating multiple independent streams.

LCGs should not be used for applications where high-quality randomness is critical.

Full article ▸

related documents
Euphoria (programming language)
PILOT
S-expression
De Moivre's formula
Nash embedding theorem
Uncountable set
Reverse Polish notation
Identity element
Parity (mathematics)
Chomsky normal form
Greedy algorithm
Compiler-compiler
Box-Muller transform
Normal subgroup
Simple LR parser
Lagrange's theorem (group theory)
Hidden Markov model
Binary function
Divisor
Logical disjunction
Complement (set theory)
CYK algorithm
PSPACE-complete
Lipschitz continuity
Toeplitz matrix
Congruence relation
Graded algebra
Ordered field
Metrization theorem
Amicable number