Linear congruential generator

A linear congruential generator (LCG) 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 the recurrence relation:

X n + 1 = ( a X n + c ) mod m {\displaystyle X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}}

where X {\displaystyle X} is the sequence of pseudo-random values, and

m , 0 < m {\displaystyle m,\,0<m} — the "modulus"

a , 0 < a < m {\displaystyle a,\,0<a<m} — the "multiplier"

c , 0 ≤ c < m {\displaystyle c,\,0\leq c<m} — the "increment"

X 0 , 0 ≤ X 0 < m {\displaystyle X_{0},\,0\leq X_{0}<m} — the "seed" or "start value" are integer constants that specify the generator. If c = 0, the generator is often called a multiplicative congruential generator (MCG), 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.

History The Lehmer generator was published in 1951 and the Linear congruential generator was published in 1958 by W. E. Thomson and A. Rotenberg.

Period length A benefit of LCGs is that an appropriate choice of parameters results in a period which is both 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. Other values of c coprime to m produce a Weyl sequence, which is better distributed but still 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 (the Mersenne primes 231−1 and 261−1 are popular), so that the reduction modulo m = 2e − d can be computed as (ax mod 2e) + d ⌊ax/2e⌋. 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. q = ⌊m/a⌋ and r = m mod a. Then compute ax mod m = a(x mod q) − r⌊x/q⌋. 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 (and thus r/q ≤ 1), then the second term is also less than m: r⌊x/q⌋ ≤ rx/q = x(r/q) ≤ x < m. Thus, both products can be computed with a single-width product, and the difference between them lies in the range [1−m, m−1], so can be reduced to [0, m−1] with a single conditional add. The most expensive operation in Schrage's method is the division (with remainder) of x by q; fast algorithms for division by a constant are not available since they also rely on double-width products. A second disadvantage of a prime modulus 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 two, 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 (mod 8) and the initial state X0 is odd. Even in this best case, the low three bits of X alternate between two values and thus only contribute one bit to the state. X is always odd (the lowest-order bit never changes), and only one of the next two bits ever changes. If a ≡ +3, X alternates ±1↔±3, while if a ≡ −3, X alternates ±1↔∓3 (all modulo 8). It can be shown that this form is equivalent to a generator with modulus m/4 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. Its simplicity of implementation comes from the fact that bits are never affected by higher-order bits, so the low b bits of such a generator form a modulo-2b LCG by themselves, repeating with a period of 2b−2. Only the most significant bit of X achieves the full period.

m a power of 2, 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:

… excerpt ends here. Continue reading the full article.