Linear congruential generator


A linear congruential generator is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.
The generator is defined by recurrence relation:
where is the sequence of pseudorandom values, and
are integer constants that specify the generator. If c = 0, the generator is often called a multiplicative congruential generator, or Lehmer RNG. If c ≠ 0, the method is called a mixed congruential generator.
When c ≠ 0, a mathematician would call the recurrence an affine transformation, not a linear one, but the misnomer is well-established in computer science.

Period length

A benefit of LCGs is that with appropriate choice of parameters, the period is known and long. Although not the only criterion, too short a period is a fatal flaw in a pseudorandom number generator.
While LCGs are capable of producing pseudorandom numbers which can pass formal tests for randomness, the quality of the output is extremely sensitive to the choice of the parameters m and a. For example, a = 1 and c = 1 produces a simple modulo-m counter, which has a long period, but is obviously non-random.
Historically, poor choices for a have led to ineffective implementations of LCGs. A particularly illustrative example of this is RANDU, which was widely used in the early 1970s and led to many results which are currently being questioned because of the use of this poor LCG.
There are three common families of parameter choice:

''m'' prime, ''c'' = 0

This is the original Lehmer RNG construction. The period is m−1 if the multiplier a is chosen to be a primitive element of the integers modulo m. The initial state must be chosen between 1 and m−1.
One disadvantage of a prime modulus is that the modular reduction requires a double-width product and an explicit reduction step. Often a prime just less than a power of 2 is used, so that the reduction modulo m = 2e − d can be computed as + d . This must be followed by a conditional subtraction of m if the result is too large, but the number of subtractions is limited to ad/m, which can be easily limited to one if d is small.
If a double-width product is unavailable, and the multiplier is chosen carefully, Schrage's method may be used. To do this, factor m = qa+r, i.e. and. Then compute ax mod m =. Since x mod q < q ≤ m/a, the first term is strictly less than am/a = m. If a is chosen so that r ≤ q, then the second term is also less than m: r  ≤ rx/q = x ≤ x < m. Thus, both products can be computed with a single-width product, and the difference between them lies in the range , so can be reduced to with a single conditional add.
A second disadvantage is that it is awkward to convert the value 1 ≤ x < m to uniform random bits. If a prime just less than a power of 2 is used, sometimes the missing values are simply ignored.

''m'' a power of 2, ''c'' = 0

Choosing m to be a power of 2, most often m = 232 or m = 264, produces a particularly efficient LCG, because this allows the modulus operation to be computed by simply truncating the binary representation. In fact, the most significant bits are usually not computed at all. There are, however, disadvantages.
This form has maximal period m/4, achieved if a ≡ 3 or a ≡ 5. The initial state X0 must be odd, and the low three bits of X alternate between two states and are not useful. It can be shown that this form is equivalent to a generator with a modulus a quarter the size and c ≠ 0.
A more serious issue with the use of a power-of-two modulus is that the low bits have a shorter period than the high bits. The lowest-order bit of X never changes, and the next two bits alternate between two states., then bit 1 never changes and bit 2 alternates. If a ≡ 3 Bit 3 repeats with a period of 4, bit 4 has a period of 8, and so on. Only the most significant bit of X achieves the full period.

''c'' ≠ 0

When c ≠ 0, correctly chosen parameters allow a period equal to m, for all seed values. This will occur if and only if:
  1. and are relatively prime,
  2. is divisible by all prime factors of,
  3. is divisible by 4 if is divisible by 4.
These three requirements are referred to as the Hull–Dobell Theorem.
This form may be used with any m, but only works well for m with many repeated prime factors, such as a power of 2; using a computer's word size is the most common choice. If m were a square-free integer, this would only allow a ≡ 1, which makes a very poor PRNG; a selection of possible full-period multipliers is only available when m has repeated prime factors.
Although the Hull–Dobell theorem provides maximum period, it is not sufficient to guarantee a good generator. For example, it is desirable for a − 1 to not be any more divisible by prime factors of m than necessary. Thus, if m is a power of 2, then a − 1 should be divisible by 4 but not divisible by 8, i.e. a ≡ 5 .
Indeed, most multipliers produce a sequence which fails one test for non-randomness or another, and finding a multiplier which is satisfactory to all applicable criteria is quite challenging. The spectral test is one of the most important tests.
Note that a power-of-2 modulus shares the problem as described above for c = 0: the low k bits form a generator with modulus 2k and thus repeat with a period of 2k; only the most significant bit achieves the full period. If a pseudorandom number less than r is desired, is a much higher-quality result than X mod r. Unfortunately, most programming languages make the latter much easier to write, so it is the more commonly used form.
The generator is not sensitive to the choice of c, as long as it is relatively prime to the modulus, so the value c=1 is commonly chosen.
The series produced by other choices of c can be written as a simple function of the series when c=1. Specifically, if Y is the prototypical series defined by Y0 = 0 and Yn+1 = aYn+1 mod m, then a general series Xn+1 = aXn+c mod m can be written as an affine function of Y:
More generally, any two series X and Z with the same multiplier and modulus are related by

Parameters in common use

The following table lists the parameters of LCGs in common use, including built-in rand functions in runtime libraries of various compilers. This table is to show popularity, not examples to emulate; many of these parameters are poor. Tables of good parameters are available.
Sourcemodulus
m		multiplier
a		increment
c		output bits of seed in rand or Random
Numerical Recipes2³²16645251013904223
Borland C/C++2³²226954771bits 30..16 in rand, 30..0 in lrand
glibc 2³¹110351524512345bits 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++
C90, C99, C11: Suggestion in the ISO/IEC 9899, C18		2³¹110351524512345bits 30..16
Borland Delphi, Virtual Pascal2³²1347758131bits 63..32 of '
Turbo Pascal2³²134775813 1
Microsoft Visual/Quick C/C++2³²214013 2531011 bits 30..16
Microsoft Visual Basic 2²⁴1140671485 12820163
RtlUniform from Native API2³¹ − 12147483629 2147483587
Apple CarbonLib, C++11's minstd_rand02³¹ − 1168070see MINSTD
C++11's minstd_rand2³¹ − 1482710see MINSTD
MMIX by Donald Knuth2⁶⁴63641362238467930051442695040888963407
Newlib, Musl2⁶⁴63641362238467930051bits 63..32
VMS's MTH$RANDOM', old versions of glibc2³²69069 1
Java's java.utilRandom, POSIX rand48, glibc rand482⁴⁸25214903917 11bits 47..16

random0		134456 = 2³7⁵812128411
POSIX rand48, glibc rand482⁴⁸25214903917 11bits 47..15
POSIX rand48, glibc rand482⁴⁸25214903917 11bits 47..0
cc652²³65793 4282663 bits 22..8
cc652³²16843009 826366247 bits 31..16
Formerly common:'' 2³¹655390

As shown above, LCGs do not always use all of the bits in the values they produce. For example, the Java implementation operates with 48-bit values at each iteration but returns only their 32 most significant bits. This is because the higher-order bits have longer periods than the lower-order bits. LCGs that use this truncation technique produce statistically better values than those that do not. This is especially noticeable in scripts that use the mod operation to reduce range; modifying the random number mod 2 will lead to alternating 0 and 1 without truncation.

Advantages and disadvantages

LCGs are fast and require minimal memory to retain state. This makes them valuable for simulating multiple independent streams. LCGs are not intended, and must not be used, for cryptographic applications; use a cryptographically secure pseudorandom number generator for such applications.
s of a linear congruential generator in three dimensions. This structure is what the spectral test measures.
Although LCGs have a few specific weaknesses, many of their flaws come from having too small a state. The fact that people have been lulled for so many years into using them with such small moduli can be seen as a testament to strength of the technique. A LCG with large enough state can pass even stringent statistical tests; a modulo-2 LCG which returns the high 32 bits passes TestU01's SmallCrush suite, and a 96-bit LCG passes the most stringent BigCrush suite.
For a specific example, an ideal random number generator with 32 bits of output is expected to begin duplicating earlier outputs after ≈ 216 results. Any PRNG whose output is its full, untruncated state will not produce duplicates until its full period elapses, an easily detectable statistical flaw. For related reasons, any PRNG should have a period longer than the square of the number of outputs required. Given modern computer speeds, this means a period of 264 for all but the least demanding applications, and longer for demanding simulations.
One flaw specific to LCGs is that, if used to choose points in an n-dimensional space, the points will lie on, at most, hyperplanes. This is due to serial correlation between successive values of the sequence Xn. Carelessly chosen multipliers will usually have far fewer, widely spaced planes, which can lead to problems. The spectral test, which is a simple test of an LCG's quality, measures this spacing and allows a good multiplier to be chosen.
The plane spacing depends both on the modulus and the multiplier. A large enough modulus can reduce this distance below the resolution of double precision numbers. The choice of the multiplier becomes less important when the modulus is large. It is still necessary to calculate the spectral index and make sure that the multiplier is not a bad one, but purely probabilistically it becomes extremely unlikely to encounter a bad multiplier when the modulus is larger than about 264.
Another flaw specific to LCGs is the short period of the low-order bits when m is chosen to be a power of 2. This can be mitigated by using a modulus larger than the required output, and using the most significant bits of the state.
Nevertheless, for some applications LCGs may be a good option. For instance, in an embedded system, the amount of memory available is often severely limited. Similarly, in an environment such as a video game console taking a small number of high-order bits of an LCG may well suffice. The low order bits go through very short cycles. In particular, any full-cycle LCG, when m is a power of 2, will produce alternately odd and even results.
LCGs should be evaluated very carefully for suitability in non-cryptographic applications where high-quality randomness is critical. For Monte Carlo simulations, an LCG must use a modulus greater and preferably much greater than the cube of the number of random samples which are required. This means, for example, that a 32-bit LCG can be used to obtain about a thousand random numbers; a 64-bit LCG is good for about 221 random samples, etc. For this reason, in practice LCGs are not suitable for large-scale Monte Carlo simulations.

Sample Python code

The following is an implementation of an LCG in Python:

def lcg:
"""Linear congruential generator."""
while True:
seed = % modulus
yield seed

Sample Free Pascal code

Free Pascal uses a Mersenne Twister as its default pseudo random number generator whereas Delphi uses a LCG. Here is a Delphi compatible example in Free Pascal based on the information in the table above. Given the same RandSeed value it generates the same sequence of random numbers as Delphi.

unit lcg_random;
interface
function LCGRandom: extended; overload;inline;
function LCGRandom:longint;overload;inline;
implementation
function IM:cardinal;inline;
begin
RandSeed := RandSeed * 134775813 + 1;
Result := RandSeed;
end;
function LCGRandom: extended; overload;inline;
begin
Result := IM * 2.32830643653870e-10;
end;
function LCGRandom:longint;overload;inline;
begin
Result := IM * range shr 32;
end;
Like all pseudorandom number generators, a LCG needs to store state and alter it each time it generates a new number. Multiple threads may access this state simultaneously causing a race condition. Implementations should use different state each with unique initialization for different threads to avoid equal sequences of random numbers on simultaneously executing threads.

LCG derivatives

There are several generators which are linear congruential generators in a different form, and thus the techniques used to analyze LCGs can be applied to them.
One method of producing a longer period is to sum the outputs of several LCGs of different periods having a large least common multiple; the Wichmann–Hill generator is an example of this form. This can be shown to be equivalent to a single LCG with a modulus equal to the product of the component LCG moduli.
Marsaglia's add-with-carry and subtract-with-borrow PRNGs with a word size of b=2w and lags r and s are equivalent to LCGs with a modulus of br ± bs ± 1.
Multiply-with-carry PRNGs with a multiplier of a are equivalent to LCGs with a large prime modulus of abr−1 and a power-of-2 multiplier b.
A permuted congruential generator begins with a power-of-2-modulus LCG and applies an output transformation to eliminate the short period problem in the low-order bits.

Comparison with other PRNGs

The other widely used primitive for obtaining long-period pseudorandom sequences is the linear feedback shift register construction, which is based on arithmetic in GF, the polynomial ring over GF. Rather than integer addition and multiplication, the basic operations are exclusive-or and carry-less multiplication, which is usually implemented as a sequence of logical shifts. These have the advantage that all of their bits are full-period; they do not suffer from the weakness in the low-order bits that plagues arithmetic modulo 2k.
Examples of this family include xorshift generators and the Mersenne twister. The latter provides a very long period and variate uniformity, but it fails some statistical tests. Lagged Fibonacci generators also fall into this category; although they use arithmetic addition, their period is ensured by an LFSR among the least-significant bits.
It is easy to detect the structure of a linear feedback shift register with appropriate tests such as the linear complexity test implemented in the TestU01 suite; a boolean circulant matrix initialized from consecutive bits of an LFSR will never have rank greater than the degree of the polynomial. Adding a non-linear output mixing function can greatly improve the performance on statistical tests.
Another structure for a PRNG is a very simple recurrence function combined with a powerful output mixing function. This includes counter mode block ciphers and non-cryptographic generators such as .
A structure similar to LCGs, but not equivalent, is the multiple-recursive generator: Xn = mod m for k ≥ 2. With a prime modulus, this can generate periods up to mk−1, so is a useful extension of the LCG structure to larger periods.
A powerful technique for generating high-quality pseudorandom numbers is to combine two or more PRNGs of different structure; the sum of an LFSR and an LCG can do very well at some cost in speed.