Linear congruential generator

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Visualisation of generation of pseudo-random numbers in [0, 8] using a linear congruential generator. The top two rows show a generator with m = 9, a = 2 and c = 0 outputting numbers from left to right until the output equals the seed, when the sequence repeats. A seed of 1 gives a cycle length of 6 but a seed of 3 gives a cycle length of only 2. Using a = 4 and c = 1 (bottom row) gives a full cycle length of 9 with any seed.

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.[1] The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modulo arithmetic by storage-bit truncation.

The generator is defined by the recurrence relation:

where is the sequence of pseudorandom values, and

– the "modulus"
– the "multiplier"
– the "increment"
– 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.[2]

Period length[edit]

The period of a general mixed congruential generator is at most m, and for some choices of factor a much less than that. The mixed congruential generator will have a full period for all seed values if and only if:[2][3]

  1. and the offset 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.[4][5] While LCGs are capable of producing pseudorandom numbers which can pass formal tests for randomness, this is extremely sensitive to the choice of the parameters c, m, and a.[clarification needed]

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 led to many results which are currently being questioned because of the use of this poor LCG.[6]

Parameters in common use[edit]

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 (in fact, this can be achieved by simply not computing the most significant bits at all). The following table lists the parameters of LCGs in common use, including built-in rand() functions in runtime libraries of various compilers.

Source m (multiplier) a    (increment) c output bits of seed in rand() or Random(L)
Numerical Recipes 232 1664525 1013904223
Borland C/C++ 232 22695477 1 bits 30..16 in rand(), 30..0 in lrand()
glibc (used by GCC)[7] 231 - 1 1103515245 12345 bits 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ [8]
C99, C11: Suggestion in the ISO/IEC 9899 [9]
231 1103515245 12345 bits 30..16
Borland Delphi, Virtual Pascal 232 134775813 1 bits 63..32 of (seed * L)
Turbo Pascal 232 134775813 (0x808840516) 1
Microsoft Visual/Quick C/C++ 232 214013 (343FD16) 2531011 (269EC316) bits 30..16
Microsoft Visual Basic (6 and earlier)[10] 224 1140671485 (43FD43FD16) 12820163 (C39EC316)
RtlUniform from Native API[11] 231 − 1 2147483629 (7FFFFFED16) 2147483587 (7FFFFFC316)
Apple CarbonLib, C++11's minstd_rand0[12] 231 − 1 16807 0 see MINSTD
C++11's minstd_rand[12] 231 − 1 48271 0 see MINSTD
MMIX by Donald Knuth 264 6364136223846793005 1442695040888963407
Newlib, Musl 264 6364136223846793005 1 bits 63...32
VMS's MTH$RANDOM,[13] old versions of glibc 232 69069 (10DCD16) 1
Java's java.util.Random, POSIX [ln]rand48, glibc [ln]rand48[_r] 248 25214903917 (5DEECE66D16) 11 bits 47...16


If Xn is even then Xn+1 will be odd, and vice versa—the lowest bit oscillates at each step.

134456 = 2375 8121 28411
POSIX[19] [jm]rand48, glibc [mj]rand48[_r] 248 25214903917 (5DEECE66D16) 11 bits 47...15
POSIX [de]rand48, glibc [de]rand48[_r] 248 25214903917 (5DEECE66D16) 11 bits 47...0
cc65[20] 223 65793 (1010116) 4282663 (41592716) bits 22...8
cc65 232 16843009 (101010116) 826366247 (3141592716) bits 31...16
Formerly common: RANDU [6] 231   65539 0

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 (see below). LCGs that use this truncation technique produce statistically better values than those that do not.

Advantages and disadvantages[edit]

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

Hyperplanes of a linear congruential generator in three dimensions

LCGs should not be used for applications where high-quality randomness is critical. For example, it is not suitable for a Monte Carlo simulation because of the serial correlation (among other things). They also must not be used for cryptographic applications; see cryptographically secure pseudo-random number generator for more suitable generators. If a linear congruential generator is seeded with a character and then iterated once, the result is a simple classical cipher called an affine cipher; this cipher is easily broken by standard frequency analysis.

LCGs tend to exhibit some severe defects. For instance, if an LCG is used to choose points in an n-dimensional space, the points will lie on, at most, (n!m)1/n hyperplanes (Marsaglia's Theorem, developed by George Marsaglia). This is due to serial correlation between successive values of the sequence Xn. The spectral test, which is a simple test of an LCG's quality, is based on this fact.

A further problem of LCGs is that the lower-order bits of the generated sequence have a far shorter period than the sequence as a whole if m is set to a power of 2. In general, the nth least significant digit in the base b representation of the output sequence, where bk = m for some integer k, repeats with at most period bn.

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 of LCGs when m is a power of 2 should never be relied on for any degree of randomness whatsoever. Indeed, simply substituting 2n for the modulus term reveals that 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.

Sample Python code[edit]

The following is an implementation of an LCG in Python:

def lcg(modulus, a, c, seed):
    while True:
        seed = (a * seed + c) % modulus
        yield seed

Sample Microsoft Small Basic Ver 1.2[edit]

' Microsoft Small Basic Ver 1.2
' by Jan Zumwalt    2017.09.10
' Linear Congruential Generator
seed = Clock.ElapsedMilliseconds
a = 1103515245 
c = 12345
m = Math.Power(2,32)

For x = 1 to 100
  rnd = return

sub rand   ' returns a random number between 0 and 1
  seed = math.Remainder(a * seed + c, m) / 1000000
  return = seed - Math.floor(seed)

Sample Free Pascal code[edit]

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}

function LCGRandom: extended; overload;inline;
function LCGRandom(const range:longint):longint;overload;inline;

function IM:cardinal;inline;
  RandSeed := RandSeed * 134775813  + 1;
  Result := RandSeed;

function LCGRandom: extended; overload;inline;
  Result := IM * 2.32830643653870e-10;

function LCGRandom(const range:longint):longint;overload;inline;
  Result := IM * range shr 32;

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.

Comparison with other PRNGs[edit]

Generators based on linear recurrences (such as xorshift*) or on good avalanching functions (such as SplitMix64 [1]) outperform linear congruential generators even at small state sizes. Moreover, linear generators can generate very long sequences, and when suitably perturbed at the output, they pass strong statistical tests. Several examples can be found in the Xorshift family. The Mersenne twister algorithm provides a very long period (219937 − 1) and variate uniformity, but it fails some statistical tests.[21] A common Mersenne twister implementation, interestingly enough, uses an LCG to generate seed data.[citation needed]

Linear congruential generators have the problem that all of the bits in each number are usually not equally random. A linear feedback shift register PRNG produces a stream of pseudo-random bits, each of which are truly pseudo-random,[22] and can be implemented with essentially the same amount of memory as a linear congruential generator, albeit with a bit more computation.

The linear feedback shift register has a strong relationship to linear congruential generators.[23] Given a few values in the sequence, some techniques can predict the following values in the sequence for not only linear congruent generators but any other polynomial congruent generator.[23]

See also[edit]


  1. ^ "Linear Congruential Generators" by Joe Bolte, Wolfram Demonstrations Project.
  2. ^ a b Donald E. Knuth (6 May 2014). Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley Professional. pp. 4–. ISBN 978-0-321-63576-1. 
  3. ^ Knuth, Donald E. Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley Professional. pp. 17–19. ISBN 978-0-321-63576-1. 
  4. ^ Hull, T. E.; Dobell, A. R. (1962-01-01). "Random Number Generators" (PDF). SIAM Review. 4 (3): 230–254. doi:10.1137/1004061. Retrieved 2016-06-26. 
  5. ^ Severance, Frank (2001). System Modeling and Simulation. John Wiley & Sons, Ltd. p. 86. ISBN 0-471-49694-4. 
  6. ^ a b Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed.). ISBN 0-521-43064-X. 
  7. ^ The GNU C library's rand() in stdlib.h uses a simple (single state) linear congruential generator only in case that the state is declared as 8 bytes. If the state is larger (an array), the generator becomes an additive feedback generator and the period increases. See the simplified code that reproduces the random sequence from this library.
  8. ^ "A collection of selected pseudorandom number generators with linear structures, K. Entacher, 1997". Retrieved 16 June 2012. 
  9. ^ "Last public Committee Draft from April 12, 2011, page 346f" (PDF). Retrieved 21 Dec 2014. 
  10. ^ "How Visual Basic Generates Pseudo-Random Numbers for the RND Function". Microsoft Support. Microsoft. Retrieved 17 June 2011. 
  11. ^ In spite of documentation on MSDN, RtlUniform uses LCG, and not Lehmer's algorithm, implementations before Windows Vista are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied
  12. ^ a b "ISO/IEC 14882:2011". ISO. 2 September 2011. Retrieved 3 September 2011. 
  13. ^ GNU Scientific Library: Other random number generators
  14. ^ Stephen J. Chapman. "Example 6.4 - Random Number Generator". "MATLAB Programming for Engineers". 2015. p. 253-256.
  15. ^ Stephen J. Chapman. "Example 6.4 - Random Number Generator". "MATLAB Programming with Applications for Engineers". 2012. p. 292-295.
  16. ^ S. J. Chapman. random0. 2004.
  17. ^ Stephen J. Chapman. "Introduction to Fortran 90/95". 1998. p. 322-324.
  18. ^ Wu-ting Tsai. "'Module': A Major Feature of the Modern Fortran". p. 6-7.
  19. ^ The Open Group Base Specifications Issue 7 IEEE Std 1003.1, 2013 Edition
  20. ^ Cadot, Sidney. "rand.s". cc65. Retrieved 8 July 2016. 
  21. ^ Matsumoto, Makoto, and Takuji Nishimura (1998) ACM Transactions on Modeling and Computer Simulation 8
  22. ^ * Neil Gershenfeld. The Nature of Mathematical Modeling, First Edition. Cambridge University Press, 1999. ISBN 0-521-57095-6. Section 5.3.2: Linear Feedback, p. 59.
  23. ^ a b RFC 4086 section 6.1.3 "Traditional Pseudo-random Sequences"


External links[edit]