Linear congruential generator
[[File:Linear_congruential_generator_visualisation.svg|thumb|480px|Two modulo-9 LCGs show how different parameters lead to different cycle lengths.
≈ 13 min read
Linear congruential generator. encyclopegia.org, snapshot enwiki-001374761067. /a/linear-congruential-generator
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
[[File:Linear_congruential_generator_visualisation.svg|thumb|480px|Two modulo-9 LCGs show how different parameters lead to different cycle lengths. Each row shows the state evolving until it repeats. The top row shows a generator with m = 9, a = 2, c = 0, and a seed of 1, which produces a cycle of length 6.
The second row is the same generator with a seed of 3, which produces a cycle of length 2. Using a = 4 and c = 1 (bottom row) gives a cycle length of 9 with any seed in [0, 8]. 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} = \left( a X_n + c \right)\bmod m where X is the sequence of pseudo-random values, and m,\, 0 — the "modulus" a,\,0 — the "multiplier" c,\,0 \le c — the "increment" X_0,\,0 \le X_0 — 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 19511 and the Linear congruential generator was published in 1958 by W. E. Thomson and A. Rotenberg. 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 2 31 −1 and 2 61 −1 are popular), so that the reduction modulo m = 2 e − d can be computed as (ax mod 2 e ) + 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 32 or m = 2 64 , 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 X 0 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-2 b LCG by themselves, repeating with a period of 2 b−2 .
Only the most significant bit of X achieves the full period. 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 2 k and thus repeat with a period of 2 k ; 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 ( X % r ), so it is very commonly used. The generator is not sensitive to the choice of c, as long as it is relatively prime to the modulus (e.g. if m is a power of 2, then c must be odd), so the value c=1 is commonly chosen.
The sequence produced by other choices of c can be written as a simple function of the sequence when c=1. Specifically, if Y is the prototypical sequence defined by Y 0 = 0 and Y n+1 = aY n + 1 mod m, then a general sequence X n+1 = aX n + c mod m can be written as an affine function of Y: X_n = (X_0(a-1)+c)Y_n + X_0 = (X_1 - X_0)Y_n + X_0 \pmod m. More generally, any two sequences X and Z with the same multiplier and modulus are related by { X_n - X_0 \over X_1 - X_0 } = Y_n = {a^n - 1 \over a - 1} = { Z_n - Z_0 \over Z_1 - Z_0 } \pmod m. In the common case where m is a power of 2 and a ≡ 5 (mod 8) (a desirable property for other reasons), it is always possible to find an initial value X 0 so that the denominator X 1 − X 0 ≡ ±1 (mod m), producing an even simpler relationship.
With this choice of X 0 , X n = X 0 ± Y n will remain true for all n. The sign is determined by c ≡ ±1 (mod 4), and the constant X 0 is determined by 1 ∓ c ≡ (1 − a)X 0 (mod m). As a simple example, consider the generators X n+1 = 157X n + 3 mod 256 and Y n+1 = 157Y n + 1 mod 256; i.e. m = 256, a = 157, and c = 3. Because 3 ≡ −1 (mod 4), we are searching for a solution to 1 + 3 ≡ (1 − 157)X 0 (mod 256).
This is satisfied by X 0 ≡ 41 (mod 64), so if we start with that, then X n ≡ X 0 − Y n (mod 256) for all n. For example, using X 0 = 233 = 3×64 + 41: X = 233, 232, 75, 2, 61, 108, ... Y = 0, 1, 158, 231, 172, 125, ... X + Y mod 256 = 233, 233, 233, 233, 233, 233, ...
Python code
The following is an implementation of an LCG in Python, in the form of a generator: from collections.abc import Generator def lcg(modulus: int, a: int, c: int, seed: int) -> Generator[int, None, None]: """Linear congruential generator.""" while True: seed = (a * seed + c) % modulus yield seed
Haskell code
The following is an implementation of an LCG in Haskell utilizing a lazy evaluation strategy to generate an infinite stream of output values in a list: -- Allowing a generic choice for a, c, m and x_0 linearCongruentialGenerator :: Integer -> Integer -> Integer -> Integer -> [Integer] linearCongruentialGenerator a c modulus seed = lcgacmx0 where lcgacmx0 = seed : map (\x -> (a*x + c) `mod` modulus) lcgacmx0 -- Specific parameters can be easily specified (eg. Knuth's MMIX parameters): mmixLCG :: Integer -> [Integer] mmixLCG = linearCongruentialGenerator 6364136223846793005 1442695040888963407 (2^(64 ::Integer))
Free Pascal
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; {$ifdef fpc}{$mode delphi}{$endif} interface function LCGRandom: extended; overload; inline; function LCGRandom(const range:longint): 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(const range: longint): 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.
(We would prefer them to be completely coprime, but a prime modulus implies an even period, so there must be a common factor of 2, at least.) 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=2 w and lags r and s (r > s) are equivalent to LCGs with a modulus of b r ± b s ± 1. Multiply-with-carry PRNGs with a multiplier of a are equivalent to LCGs with a large prime modulus of ab r −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(2)[x], the polynomial ring over GF(2). 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 2 k . Examples of this family include xorshift generators and the Mersenne twister. The latter provides a very long period (2 19937 −1) 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 (as in the xoshiro256** and permuted congruential generator constructions) 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 SplitMix64.
A structure similar to LCGs, but not equivalent, is the multiple-recursive generator: X n = (a 1 X n−1 + a 2 X n−2 + ··· + a k X n−k ) mod m for k ≥ 2. With a prime modulus, this can generate periods up to m k −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 (as in the KISS or xorwow constructions) can do very well at some cost in speed.
See also
List of random number generators – other PRNGs including some with better statistical qualities ACORN generator – not to be confused with ACG which term appears to have been used for variants of LCG and LFSR generators Permuted congruential generator Full cycle Inversive congruential generator Multiply-with-carry Lehmer RNG (sometimes called the Park–Miller RNG) Combined linear congruential generator
References
Gentle, James E., (2003). Random Number Generation and Monte Carlo Methods, 2nd edition, Springer, . (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).
External links
The simulation Linear Congruential Generator visualizes the correlations between the pseudo-random numbers when manipulating the parameters. Security of Random Number Generation: An Annotated Bibliography Linear Congruential Generators post to sci.math The "Death of Art" computer art project at Goldstein Technologies LLC, uses an LCG to generate 33,554,432 images P. L'Ecuyer and R. Simard, "TestU01: A C Library for Empirical Testing of Random Number Generators", May 2006, revised November 2006, ACM Transactions on Mathematical Software, 33, 4, Article 22, August 2007.
Article about another way of cracking LCG
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374761067 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Linear congruential generator” publication date (×1) · confidence 0.95 revision URL