View source for Linear congruential generator

{{Short description|Algorithm for generating pseudo-randomized numbers}}
[[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''&nbsp;=&nbsp;9, ''a''&nbsp;=&nbsp;2, ''c''&nbsp;=&nbsp;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''&nbsp;=&nbsp;4 and ''c''&nbsp;=&nbsp;1 (bottom row) gives a cycle length of 9 with any seed in [0,&nbsp;8].]]

A '''linear congruential generator''' ('''LCG''') is an [[algorithm]] that yields a sequence of pseudo-randomized numbers calculated with a discontinuous [[piecewise linear function|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]]:

:<math>X_{n+1} = \left( a X_n + c \right)\bmod m</math>

where <math>X</math> is the [[sequence]] of pseudo-random values, and

: <math> m,\, 0<m </math> — the "[[modulo operation|modulus]]"
: <math> a,\,0 < a < m</math> — the "multiplier"
: <math> c,\,0 \le c < m</math> — the "increment"
: <math> X_0,\,0 \le X_0 < m</math> — the "seed" or "start value"

are [[integer]] constants that specify the generator. If ''c''&nbsp;=&nbsp;0, the generator is often called a '''multiplicative congruential generator''' (MCG), or [[Lehmer RNG]]. If ''c''&nbsp;≠&nbsp;0, the method is called a '''mixed congruential generator'''.{{r|KnuthV2|p=4-}}

When ''c''&nbsp;≠&nbsp;0, a mathematician would call the recurrence an [[affine transformation]], not a [[Linear transformation|linear]] one, but the misnomer is well-established in computer science.<ref name=Steele20>{{cite journal
 |title=Computationally easy, spectrally good multipliers for congruential pseudorandom number generators
 |first1=Guy L. Jr. |last1=Steele |author-link1=Guy L. Steele Jr.
 |first2=Sebastiano |last2=Vigna |author-link2=Sebastiano Vigna
 |journal=Software: Practice and Experience
 |volume=52 |issue=2 |date=February 2022 |pages=443–458
 |doi=10.1002/spe.3030 |doi-access=free
 |arxiv=2001.05304 |hdl=2434/891395 |orig-date=15 January 2020
 |url=https://www.researchgate.net/publication/354960552
 |quote=these denominations, by now used for half a century, are completely wrong from a mathematical viewpoint.... At this point it is unlikely that the now-traditional names will be corrected.
}} Associated software and data at https://github.com/vigna/CPRNG.</ref>{{Rp|1}}

==History==
The Lehmer generator was published in 1951<ref>{{Cite journal|last=Lehmer|first=Derrick H.|date=1951|title=Mathematical methods in large-scale computing units|journal=Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery|pages=141–146}}</ref> and the Linear congruential generator was published in 1958 by W. E. Thomson and A. Rotenberg.<ref>{{Cite journal|last=Thomson|first=W. E.|date=1958|title=A Modified Congruence Method of Generating Pseudo-random Numbers|journal=The Computer Journal|volume=1|issue=2|pages=83|doi=10.1093/comjnl/1.2.83|doi-access=free}}</ref><ref>{{Cite journal|last=Rotenberg|first=A.|date=1960|title=A New Pseudo-Random Number Generator|journal=Journal of the ACM|volume=7|issue=1|pages=75–77|doi=10.1145/321008.321019|s2cid=16770825|doi-access=free}}</ref>

== 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.<ref name=History>{{cite conference
 |title=History of Uniform Random Number Generation
 |first=Pierre |last=L'Ecuyer
 |date=13 July 2017<!--Conference is in December 2017-->
 |conference=Proceedings of the 2017 Winter Simulation Conference (to appear)
 |editor1-first=W. K. V. |editor1-last=Chan   |editor2-first=A. |editor2-last=D'Ambrogio
 |editor3-first=G. |editor3-last=Zacharewicz  |editor4-first=N. |editor4-last=Mustafee
 |editor5-first=G. |editor5-last=Wainer       |editor6-first=E. |editor6-last=Page
 |url=https://www.iro.umontreal.ca/~lecuyer/myftp/papers/wsc17rng-history.pdf
 |location=Las Vegas, United States
 |id=[https://hal.inria.fr/hal-01561551 hal-01561551]
}}</ref>

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''.{{r|KnuthV2|Steele20|Marsaglia68|Park88|Hörmann92|LEcuyer99}}  For example, ''a''&nbsp;=&nbsp;1 and ''c''&nbsp;=&nbsp;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.<ref name="Press">{{cite book |last=Press |first=William H. |year=1992 |title=Numerical Recipes in Fortran 77: The Art of Scientific Computing |edition=2nd |isbn=978-0-521-43064-7 |display-authors=etal |title-link=Numerical Recipes |page=268}}</ref>{{r|Park88|p=1198–9}}

There are three common families of parameter choice:

=== ''m'' prime, ''c'' = 0 ===
{{main|Lehmer random number generator}}
This is the original Lehmer RNG construction. The period is ''m''−1 if the multiplier ''a'' is chosen to be a [[Primitive element (finite field)|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 prime]]s 2<sup>31</sup>−1 and 2<sup>61</sup>−1 are popular), so that the reduction modulo ''m''&nbsp;=&nbsp;2<sup>''e''</sup>&nbsp;−&nbsp;''d'' can be computed as (''ax''&nbsp;mod&nbsp;2<sup>''e''</sup>)&nbsp;+&nbsp;''d''&nbsp;{{floor|''ax''/2<sup>''e''</sup>}}. 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'''<ref>{{cite journal
 |title=A more portable Fortran random number generator
 |first=Linus |last=Schrage
 |journal=ACM Transactions on Mathematical Software
 |volume=5 |issue=2 |pages=132–138 |date=June 1979
 |doi=10.1145/355826.355828
 |url=http://degiorgi.math.hr/aaa_sem/Rand_Gen/p132-schrage.pdf
}}</ref><ref>{{cite web
 |title=Computer Systems Performance Analysis Chapter 26: Random-Number Generation
 |first=Raj |last=Jain |date=9 July 2010
 |pages=19–20
 |url=http://www.cse.wustl.edu/~jain/iucee/ftp/k_26rng.pdf#page=19
 |access-date=2017-10-31
}}</ref> may be used. To do this, factor ''m''&nbsp;=&nbsp;''qa''+''r'', i.e. {{nobr|1=''q'' = {{floor|''m''/''a''}}}} and {{nobr|1=''r'' = ''m'' mod ''a''}}. Then compute ''ax''&nbsp;mod&nbsp;''m'' = {{nobr|''a''(''x'' mod ''q'') − ''r''{{floor|''x''/''q''}}}}. Since ''x''&nbsp;mod&nbsp;''q'' < ''q'' ≤ ''m''/''a'', the first term is strictly less than ''am''/''a''&nbsp;=&nbsp;''m''. If ''a'' is chosen so that ''r''&nbsp;≤&nbsp;''q'' (and thus ''r''/''q''&nbsp;≤&nbsp;1), then the second term is also less than ''m'': ''r''{{floor|''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'',&nbsp;''m''−1], so can be reduced to [0,&nbsp;''m''−1] with a single conditional add.<ref>{{cite web
 |title=Schrage's Method
 |url=http://home.earthlink.net/~pfenerty/pi/schrages_method.html
 |first=Paul |last=Fenerty |date=11 September 2006
 |access-date=2017-10-31
 |archive-url=https://web.archive.org/web/20181230061306/http://home.earthlink.net/~pfenerty/pi/schrages_method.html
 |archive-date=2018-12-30 |url-status=dead
}}</ref>

The most expensive operation in Schrage's method is the division (with remainder) of ''x'' by ''q''; fast [[Division algorithm#Division by a constant|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&nbsp;≤&nbsp;''x''&nbsp;<&nbsp;''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'' = 2<sup>32</sup> or ''m'' = 2<sup>64</sup>, 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''&nbsp;≡&nbsp;±3 (mod 8) and the initial state ''X''<sub>0</sub> 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''&nbsp;≡&nbsp;+3, ''X'' alternates ±1↔±3, while if ''a''&nbsp;≡&nbsp;−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.{{r|KnuthV2}}

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<sup>''b''</sup> LCG by themselves, repeating with a period of 2<sup>''b''−2</sup>. 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]]:{{r|KnuthV2|p=17–19}}
# <math>m</math> and <math>c</math> are coprime,
# <math>a - 1</math> is divisible by all [[prime factor]]s of <math>m</math>,
# <math>a - 1</math> is divisible by 4 if <math>m</math> is divisible by 4.

These three requirements are referred to as the Hull–Dobell Theorem.<ref>{{Cite journal
 |last1=Hull |first1=T. E. |last2=Dobell |first2=A. R.
 |date=July 1962
 |title=Random Number Generators
 |url=http://chagall.med.cornell.edu/BioinfoCourse/PDFs/Lecture4/random_number_generator.pdf
 |journal=SIAM Review |volume=4 |issue=3 |pages=230–254 
 |access-date=2016-06-26 |doi=10.1137/1004061
|bibcode=1962SIAMR...4..230H |hdl=1828/3142 |hdl-access=free }}</ref><ref name="HullDobell">{{cite book
 |title=System Modeling and Simulation
 |publisher=John Wiley & Sons, Ltd.
 |last=Severance |first=Frank |year=2001 |page=86
 |isbn=978-0-471-49694-6
}}</ref>

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''&nbsp;≡&nbsp;1 (mod&nbsp;''m''), 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.{{r|Park88|p=1199}}  For example, it is desirable for ''a''&nbsp;−&nbsp;1 to not be any more divisible by prime factors of ''m'' than necessary.  If ''m'' is a power of 2, then ''a''&nbsp;−&nbsp;1 should be divisible by 4 but not divisible by 8, i.e.&nbsp;''a''&nbsp;≡&nbsp;5&nbsp;(mod&nbsp;8).{{r|KnuthV2|at=§3.2.1.3}}

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{{r|KnuthV2|at=§3.3.3}} is quite challenging.{{r|Park88}}  The [[spectral test]] is one of the most important tests.<ref name=Austin2008>{{cite web |first=David |last=Austin |title=Random Numbers: Nothing Left to Chance |date=March 2008 |publisher=American Mathematical Society |work=Feature Column |url=https://www.ams.org/publicoutreach/feature-column/fcarc-random}}</ref>

Note that a power-of-2 modulus shares the problem as described above for ''c''&nbsp;=&nbsp;0: the low ''k'' bits form a generator with modulus 2<sup>''k''</sup> and thus repeat with a period of 2<sup>''k''</sup>; only the most significant bit achieves the full period.  If a pseudorandom number less than ''r'' is desired, {{floor|''rX''/''m''}} is a much higher-quality result than ''X'' mod ''r''.  Unfortunately, most programming languages make the latter much easier to write (<code>X % r</code>), 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.{{r|KnuthV2|p=11}}  Specifically, if ''Y'' is the prototypical sequence defined by ''Y''<sub>0</sub> =&nbsp;0 and ''Y''<sub>''n''+1</sub> =&nbsp;''aY<sub>n</sub>''&nbsp;+&nbsp;1 mod&nbsp;m, then a general sequence ''X''<sub>''n''+1</sub> =&nbsp;''aX<sub>n</sub>''&nbsp;+&nbsp;''c'' mod&nbsp;''m'' can be written as an affine function of ''Y'':
:<math>X_n = (X_0(a-1)+c)Y_n + X_0 = (X_1 - X_0)Y_n + X_0 \pmod m.</math>
More generally, any two sequences ''X'' and ''Z'' with the same multiplier and modulus are related by
:<math>{ 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.</math>

In the common case where ''m'' is a power of 2 and ''a''&nbsp;≡&nbsp;5&nbsp;(mod&nbsp;8) (a desirable property for other reasons), it is always possible to find an initial value ''X''<sub>0</sub> so that the denominator ''X''<sub>1</sub>&nbsp;−&nbsp;''X''<sub>0</sub> ≡&nbsp;±1&nbsp;(mod&nbsp;''m''), producing an even simpler relationship.  With this choice of ''X''<sub>0</sub>, ''X<sub>n</sub>'' =&nbsp;''X''<sub>0</sub>&nbsp;±&nbsp;''Y<sub>n</sub>'' will remain true for all ''n''.{{r|Steele20|p=10-11}} The sign is determined by ''c''&nbsp;≡&nbsp;±1&nbsp;(mod&nbsp;4), and the constant ''X''<sub>0</sub> is determined by 1&nbsp;∓&nbsp;''c''&nbsp;≡&nbsp;(1&nbsp;−&nbsp;''a'')''X''<sub>0</sub>&nbsp;(mod&nbsp;''m'').<!--1∓c is a multiple of 4, and 1−a ≡ 4 (mod 8), so this has solutions mod m/4-->

As a simple example, consider the generators ''X''<sub>''n''+1</sub> =&nbsp;157''X<sub>n</sub>''&nbsp;+&nbsp;3 mod&nbsp;256 and ''Y''<sub>''n''+1</sub> =&nbsp;157''Y<sub>n</sub>''&nbsp;+&nbsp;1 mod&nbsp;256; i.e. ''m''&nbsp;=&nbsp;256, ''a''&nbsp;=&nbsp;157, and ''c''&nbsp;=&nbsp;3.  Because 3&nbsp;≡&nbsp;−1&nbsp;(mod&nbsp;4), we are searching for a solution to 1&nbsp;+&nbsp;3&nbsp;≡&nbsp;(1&nbsp;−&nbsp;157)''X''<sub>0</sub>&nbsp;(mod&nbsp;256).  This is satisfied by ''X''<sub>0</sub>&nbsp;≡&nbsp;41&nbsp;(mod&nbsp;64), so if we start with that, then ''X<sub>n</sub>'' ≡&nbsp;''X''<sub>0</sub>&nbsp;−&nbsp;''Y<sub>n</sub>''&nbsp;(mod&nbsp;256) for all ''n''.

For example, using ''X''<sub>0</sub> = 233 = 3&times;64 + 41:
* ''X'' = 233, 232, 75, 2, 61, 108, ...<!--63, 166, 209, 48, 115, 138, 165, 52, 231-->
* ''Y'' = 0, 1, 158, 231, 172, 125, ...<!--170, 67, 24, 185, 118, 95, 68, 181, 2-->
* ''X''&nbsp;+&nbsp;''Y'' mod 256 = 233, 233, 233, 233, 233, 233, ...

== Parameters in common use ==
The following table lists the parameters of LCGs in common use, including built-in ''rand()'' functions in [[Runtime library|runtime libraries]] of various [[compiler]]s.  This table is to show popularity, not examples to emulate; ''many of these parameters are poor.''  Tables of good parameters are available.{{r|LEcuyer99|Steele20}}

{|class="wikitable"
! Source || modulus<br/>''m'' || multiplier<br/>''a'' || increment<br/>''c'' || output bits of seed in ''rand()'' or ''Random(L)''
|-
| ''[[ZX81]]'' || 2<sup>16</sup> + 1 || 75 || 74 || 
|-
| ''[[Numerical Recipes]]'' <code>ranqd1</code>, Chapter 7.1, §An Even Quicker Generator, Eq. 7.1.6<br /> parameters from Knuth and H. W. Lewis || 2<sup>32</sup> || 1664525 || 1013904223 || 
|-
| [[Borland]] C/C++ || 2<sup>31</sup> || 22695477 || 1 || bits 30..16 in ''rand()'', 30..0 in ''lrand()''
|-
| [[glibc]] (used by [[GNU Compiler Collection|GCC]])<ref>[https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.26#l362 Implementation in glibc-2.26 release.] See the code after the test for "TYPE_0"; 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 ([https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.26#l187 initialized using ''minstd_rand0'']) and the period increases. See the [http://www.mscs.dal.ca/~selinger/random/ simplified code] that reproduces the random sequence from this library.</ref>
| 2<sup>31</sup> || 1103515245 || 12345 || bits 30..0
|-
| [[ANSI C]]: [[Watcom C compiler|Watcom]], [[Digital Mars]], [[CodeWarrior]], [[IBM VisualAge]] C/C++<ref>{{cite book|title=A collection of selected pseudorandom number generators with linear structures |author=K. Entacher |date=21 August 1997 |url=http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.53.3686&rep=rep1&type=pdf |access-date=16 June 2012 |citeseerx=10.1.1.53.3686}}</ref><br/>[[C90 (C version)|C90]], [[C99]], [[C11 (C standard revision)|C11]]: Suggestion in the ISO/IEC 9899,<ref>{{cite web|title=Last public Committee Draft from April 12, 2011|page=346f|url=http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf|access-date=21 Dec 2014}}</ref> [[C17 (C standard revision)|C17]] || 2<sup>31</sup> || 1103515245 || 12345 || bits 30..16
|-
| [[Borland Delphi]], [[Virtual Pascal]] || 2<sup>32</sup> || 134775813 || 1 || bits 63..32 of ''(seed × L)''
|-
| [[Turbo Pascal]] 4.0 ''[[et seq.]]''<ref>{{cite journal |first1=Birgit |last1=Dohmann |first2=Michael |last2=Falk |first3=Karin |last3=Lessenich |title=The random number generators of the Turbo Pascal family |journal=Computational Statistics & Data Analysis |volume=12 |issue=1 |date=August 1991 |pages=129–132 |doi=10.1016/0167-9473(91)90108-E}}</ref>  || 2<sup>32</sup> || 134775813 (8088405<sub>16</sub>) || 1 ||
|-
| [[Visual C++|Microsoft Visual/Quick C/C++]] || 2<sup>31</sup> || 214013 (343FD<sub>16</sub>) || 2531011 (269EC3<sub>16</sub>) || bits 30..16
|-
| [[Visual Basic|Microsoft Visual Basic]] (6 and earlier)<ref>{{cite web |title=How Visual Basic Generates Pseudo-Random Numbers for the RND Function |url=http://support.microsoft.com/kb/231847 |publisher=Microsoft |access-date=17 June 2011 |archive-url=https://web.archive.org/web/20110417000838/http://support.microsoft.com/kb/231847 |archive-date=17 April 2011 |url-status=dead |date=24 June 2004 }}</ref> || 2<sup>24</sup> || 1140671485 ({{^|43}}43FD43FD<sub>16</sub>) || 12820163 (C39EC3<sub>16</sub>) ||
|-
| RtlUniform from [[Native API]]<ref>In spite of documentation on [http://msdn.microsoft.com/en-us/library/bb432429(VS.85).aspx 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</ref><ref>{{cite web |url=https://source.winehq.org/ident?_i=RtlUniform | title=WINE source identifier search: RtlUniform | access-date=2024-01-13}}</ref> || 2<sup>31</sup> − 1
|| &minus;18 (7FFFFFED<sub>16</sub>) || &minus;60 (7FFFFFC3<sub>16</sub>) ||
|-
| [[CarbonLib|Apple CarbonLib]], [[C++11]]'s <code>minstd_rand0</code>,<ref name="cpp11">{{ cite web | title = ISO/IEC 14882:2011 | publisher = ISO | date = 2 September 2011 | url = http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=50372 | access-date =3 September 2011 }}</ref> MATLAB's v4 legacy generator mcg16807<ref>{{ cite web | title = Creating and Controlling a Random Number Stream | publisher = MathWorks | url = https://www.mathworks.com/help/matlab/math/creating-and-controlling-a-random-number-stream.html | access-date = 7 June 2021 }}</ref> || 2<sup>31</sup> − 1 || 16807 || 0 || see [[MINSTD]]
|-
| [[C++11]]'s <code>minstd_rand</code><ref name="cpp11" /> || 2<sup>31</sup> − 1 || 48271 || 0 || see [[MINSTD]]
|-
| [[MMIX]] by [[Donald Knuth]] || 2<sup>64</sup> || 6364136223846793005 || 1442695040888963407 ||
|-
| [[Newlib]]<ref>{{cite web | url=https://sourceware.org/git/?p=newlib-cygwin.git;a=blob;f=newlib/libc/stdlib/rand.c | title=<code>rand</code>, <code>srand</code>&mdash;pseudo-random numbers | website=Newlib git repository | access-date=2024-01-13}}</ref> || 2<sup>63</sup> || 6364136223846793005 || 1 || bits 62..32 (46..32 for 16-bit int)
|-
| [[Musl]] || 2<sup>64</sup> || 6364136223846793005 || 1 || bits 63..33
|-
| [[OpenVMS|VMS]]'s '''MTH$RANDOM''',<ref>{{cite web| url = https://www.gnu.org/software/gsl/doc/html/rng.html#c.gsl_rng_vax | title = GNU Scientific Library: gsl_rng_vax}}</ref> old versions of [[glibc]] || 2<sup>32</sup> || 69069 (10DCD<sub>16</sub>) || 1 ||
|-
| [[Java (programming language)|Java]]'s java.util{{Not a typo|.}}Random, [[POSIX]] [ln]rand48, [[glibc]] [ln]rand48[_r]|| 2<sup>48</sup> || 25214903917 (5DEECE66D<sub>16</sub>) || 11 || bits 47..16
|-
|
<code>random0</code><ref>
Stephen J. Chapman.
"Example 6.4 – Random Number Generator".
[https://books.google.com/books?id=e80HBgAAQBAJ "MATLAB Programming for Engineers"].
2015.
pp. 253–256.
</ref><ref>
Stephen J. Chapman.
"Example 6.4 – Random Number Generator".
[https://books.google.com/books?id=of8KAAAAQBAJ "MATLAB Programming with Applications for Engineers"].
2012.
pp. 292–295.
</ref><ref>
S. J. Chapman.
[http://www.udel.edu/CIS/106/pconrad/MPE3/code/chap5/random0.m random0].
2004.
</ref><ref>
Stephen J. Chapman.
[https://books.google.com/books?id=QoVGAAAAYAAJ "Introduction to Fortran 90/95"].
1998.
pp. 322–324.
</ref><ref>Wu-ting Tsai.
[http://homepage.ntu.edu.tw/~wttsai/fortran/ppt/11.Module.pdf "'Module': A Major Feature of the Modern Fortran"] {{Webarchive|url=https://web.archive.org/web/20210224125803/http://homepage.ntu.edu.tw/~wttsai/fortran/ppt/11.Module.pdf |date=2021-02-24 }}.
pp. 6–7.</ref>
|| 134456 = 2<sup>3</sup>7<sup>5</sup> || 8121 || 28411 || <math>\frac{ X_n }{ 134456 }</math>
|-
| [[POSIX]]<ref>[http://pubs.opengroup.org/onlinepubs/9699919799/ The Open Group Base Specifications Issue 7]
IEEE Std 1003.1, 2013 Edition</ref> [dejm]rand48, [[glibc]] [dejm]rand48[_r] || 2<sup>48</sup> || 25214903917 (5DEECE66D<sub>16</sub>) || 11 || bits 47..0 or bits 47..15, as required
|-
| [[cc65]]<ref>{{cite web|first=Sidney|last=Cadot|url=https://github.com/cc65/cc65/blob/06bb95d19788e3326738ee968b49dd11d18ca790/libsrc/common/rand.s|title=rand.s|work=cc65|access-date=8 July 2016}}</ref> || 2<sup>23</sup> || 65793 (10101<sub>16</sub>) || 4282663 (415927<sub>16</sub>) || bits 22..8
|-
| [[cc65]] || 2<sup>32</sup> || 16843009 (1010101<sub>16</sub>) || 826366247 (31415927<sub>16</sub>) || bits 31..16
|-
| [[cc65]] || 2<sup>32</sup> || 16843009 (1010101<sub>16</sub>) || 3014898611 (B3B3B3B3<sub>16</sub>) || previously bits 31..16, current bits 31..16 xor bits 14..0
|- style="border-top:2px solid;"
| ''Formerly common:'' {{resize|[[RANDU]]}}<ref name=Press/> || 2<sup>31</sup> || 65539 || 0 ||
|}

As shown above, LCGs do not always use all of the bits in the values they produce.  In general, they return the most significant bits.  For example, the [[Java (programming language)|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. 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.

Contrarily, some libraries use an implicit power-of-two modulus but never output or otherwise use the most significant bit, in order to limit the output to positive [[two's complement]] integers.  The output is [[As-if rule|as if]] the modulus were one bit less than the internal word size, and such generators are described as such in the table above.

== Advantages and disadvantages ==
{{More sources needed section|date=July 2021}}
LCGs are fast and require minimal memory (one modulo-''m'' number, often 32 or 64 bits) 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.

[[Image:Lcg 3d.gif|thumb|200px|[[Hyperplane]]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 the strength of the technique. A LCG with large enough state can pass even stringent statistical tests; a modulo-2<sup>64</sup> LCG which returns the high 32 bits passes [[TestU01]]'s SmallCrush suite,{{citation needed|date=November 2017|reason=O'Neill stated this result somewhere, but I'm having a hard time finding it.}} and a 96-bit LCG passes the most stringent BigCrush suite.<ref>{{cite tech report
 |title=PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
 |first=Melissa E. |last=O'Neill
 |publisher=[[Harvey Mudd College]]
 |id=HMC-CS-2014-0905
 |date=5 September 2014
 |pages=6–7
 |url=http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf#page=9
}}</ref>

For a specific example, an ideal random number generator with 32 bits of output is expected (by the [[Birthday theorem]]) to begin duplicating earlier outputs after {{math|{{sqrt|''m''}} ≈ 2<sup>16</sup>}} results. ''Any'' PRNG whose output is its full, untruncated state will not produce duplicates until its full period elapses, an easily detectable statistical flaw.<ref name=HeathSanchez86>{{cite journal
 |title=On the adequacy of pseudo-random number generators (or: How big a period do we need?)
 |last1=Heath |first1=David |last2=Sanchez |first2=Paul
 |journal=[[Operations Research Letters]] |date=June 1986 |volume=5 |issue=1 |pages=3–6
 |doi=10.1016/0167-6377(86)90092-1
 |url=https://doi.org/10.1016/0167-6377(86)90092-1
}}</ref>
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 2<sup>64</sup> 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, {{math|{{radic|''n''!⋅''m''|''n''}} }}[[hyperplanes]] ([[Marsaglia's theorem]], developed by [[George Marsaglia]]).<ref name=Marsaglia68>{{cite journal
 |title=Random Numbers Fall Mainly in the Planes
 |first=George |last=Marsaglia |author-link=George Marsaglia
 |journal=[[PNAS]] |date=September 1968 |volume=61 |issue=1 |pages=25–28
 |doi=10.1073/pnas.61.1.25 |doi-access=free |bibcode=1968PNAS...61...25M |pmc=285899
 |url=https://www.pnas.org/content/61/1/25.full.pdf |pmid=16591687
 }}</ref> This is due to serial correlation between successive values of the sequence ''X<sub>n</sub>''. 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 2<sup>64</sup>.

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 of LCGs when m is a power of 2 should never be relied on for any degree of randomness whatsoever.)  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 (good) 32-bit LCG can be used to obtain about a thousand random numbers; a 64-bit LCG is good for about 2<sup>21</sup> random samples (a little over two million), etc. For this reason, in practice LCGs are not suitable for large-scale Monte Carlo simulations.

== Sample code ==

===Python code===
The following is an implementation of an LCG in [[Python (programming language)|Python]], in the form of a [[Generator (computer programming)|generator]]:

<syntaxhighlight lang="python">
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
</syntaxhighlight>

===Haskell code===
The following is an implementation of an LCG in [[Haskell]] utilizing a [[Lazy evaluation#Working_with_infinite_data_structures|lazy evaluation]] strategy to generate an infinite stream of output values in a list:

<syntaxhighlight lang="haskell">
-- 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) % modulus) lcgacmx0

-- Specific parameters can be easily specified (eg. Knuth's MMIX parameters):
mmixLCG :: Integer -> [Integer]
mmixLCG = linearCongruentialGenerator 6364136223846793005 1442695040888963407 (2^(64 ::Integer))
</syntaxhighlight>

===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.

<syntaxhighlight lang="pascal">
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;</syntaxhighlight>

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.

[[George Marsaglia|Marsaglia]]'s add-with-carry and [[Subtract with carry|subtract-with-borrow]] PRNGs with a word size of ''b''=2<sup>''w''</sup> and lags ''r'' and ''s'' (''r''&nbsp;>&nbsp;''s'') are equivalent to LCGs with a modulus of ''b<sup>r</sup>''&nbsp;±&nbsp;''b<sup>s</sup>''&nbsp;±&nbsp;1.<ref>{{cite conference
 |title=On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators
 |first1=Shu |last1=Tezuka |first2=Pierre |last2=L'Ecuyer
 |url=https://core.ac.uk/download/pdf/39215926.pdf
 |date=October 1993
 |publisher=Kyoto University
 |conference=Workshop on Stochastic Numerics
}}</ref><ref>{{cite conference 
 |url=http://www.informs-sim.org/wsc92papers/1992_0059.pdf
 |first1=Shi |last1=Tezuka |first2=Pierre |last2=L'Ecuyer
 |title=Analysis of Add-with-Carry and Subtract-with-Borrow Generators
 |conference=Proceedings of the 1992 Winter Simulation Conference
 |date=December 1992 |pages=443–447
}}</ref>

[[Multiply-with-carry]] PRNGs with a multiplier of ''a'' are equivalent to LCGs with a large prime modulus of ''ab<sup>r</sup>''−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 shift]]s.  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<sup>''k''</sup>.<ref>{{cite book |first=Neil |last=Gershenfeld |author-link=Neil Gershenfeld |title=The Nature of Mathematical Modeling |url=https://archive.org/details/naturemathematic00gers_334 |url-access=limited |edition=First |publisher=Cambridge University Press |year=1999 |isbn=978-0-521-57095-4 |chapter=Section 5.3.2: Linear Feedback |page=[https://archive.org/details/naturemathematic00gers_334/page/n64 59]}}</ref>

Examples of this family include [[xorshift]] generators and the [[Mersenne twister]].  The latter provides a very long period (2<sup>19937</sup>−1) and variate uniformity, but it fails some statistical tests.<ref>{{cite journal |last1=Matsumoto |first1=Makoto |first2=Takuji |last2=Nishimura |date=January 1998 |journal=ACM Transactions on Modeling and Computer Simulation |volume=8 |issue=1 |pages=3–30 |title=Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator |doi=10.1145/272991.272995 |url=https://pdfs.semanticscholar.org/098d/5792ffa43e9885f9fc644ffdd7b6a59b0922.pdf |archive-url=https://web.archive.org/web/20171107004909/https://pdfs.semanticscholar.org/098d/5792ffa43e9885f9fc644ffdd7b6a59b0922.pdf |url-status=dead |archive-date=2017-11-07 |citeseerx=10.1.1.215.1141 |s2cid=3332028 }}</ref> [[Lagged Fibonacci generator]]s 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<ref name="rfc4086">{{cite IETF |rfc=4086 |bcp=106 |title=Randomness Requirements for Security |section=6.1.3 |sectionname=Traditional Pseudo-random Sequences |first1=((Donald E. 3rd)) |last1=Eastlake |first2=Jeffrey I. |last2=Schiller |first3=Steve |last3=Crocker |date=June 2005 |publisher=[[Internet Engineering Task Force|IETF]]}}</ref> 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 (linear algebra)|rank]] greater than the degree of the polynomial.  Adding a non-linear output mixing function (as in the [[Xorshift#xoshiro256**|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 [http://prng.di.unimi.it/splitmix64.c SplitMix64].

A structure similar to LCGs, but ''not'' equivalent, is the multiple-recursive generator: ''X<sub>n</sub>''&nbsp;= (''a''<sub>1</sub>''X''<sub>''n''−1</sub>&nbsp;+ ''a''<sub>2</sub>''X''<sub>''n''−2</sub>&nbsp;+ ···&nbsp;+ ''a<sub>k</sub>X''<sub>''n''−''k''</sub>) mod&nbsp;''m'' for ''k''&nbsp;≥&nbsp;2.  With a prime modulus, this can generate periods up to ''m<sup>k</sup>''−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 (algorithm)|KISS]] or [[Xorshift#xorwow|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 qualitites
* [[ACORN (PRNG)|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]]

==Notes==
{{Reflist|30em|refs=
<ref name=KnuthV2>{{TAOCP|volume=2|edition=3|pages=10–26}}</ref>
<ref name=Park88>{{cite journal
 |first1=Stephen K. |last1=Park |first2=Keith W. |last2=Miller
 |title=Random Number Generators: Good Ones Are Hard To Find
 |journal=[[Communications of the ACM]] |date=October 1988 |volume=31 |issue=10 |pages=1192–1201
 |doi=10.1145/63039.63042 |s2cid=207575300 |url=http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
 |quote=In a sense it is unfortunate that this test for full period is so trivial as it falsely encourages non-specialists to build their own generators.
}}</ref>
<ref name=Hörmann92>{{cite journal
 |title=A Portable Uniform Random Number Generator Well Suited for the Rejection Method
 |first1=Wolfgang |last1=Hörmann |first2=Gerhard |last2=Derflinger
 |journal=ACM Transactions on Mathematical Software |volume=19 |issue=4 |pages=489–495 |date=1993
 |doi=10.1145/168173.168414 |citeseerx=10.1.1.52.3811
 |s2cid=15238956 |url=https://epub.wu.ac.at/1288/1/document.pdf
 |quote=a multiplier about as small as {{sqrt|''m''}}, produces random numbers with a bad one-dimensional distribution.
}}</ref>
<ref name=LEcuyer99>{{cite journal
 |first=Pierre |last=L'Ecuyer
 |title=Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure
 |journal=[[Mathematics of Computation]] |volume=68 |issue=225 |pages=249–260 |date=January 1999
 |url=https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf
 |doi=10.1090/S0025-5718-99-00996-5
 |bibcode=1999MaCom..68..249L
 |citeseerx=10.1.1.34.1024}}
 Be sure to read the [https://www.iro.umontreal.ca/~lecuyer/myftp/papers/latrules99Errata.pdf Errata] as well.
</ref>
}}

==References==
* {{Citation | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | location=New York | isbn=978-0-521-88068-8 | chapter=Section 7.1.1. Some History | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=343 | access-date=2011-08-10 | archive-date=2011-08-11 | archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=343 | url-status=dead }}
*Gentle, James E., (2003). ''Random Number Generation and Monte Carlo Methods'', 2nd edition, Springer, {{ISBN|0-387-00178-6}}.
* {{cite journal |author=Joan Boyar|author-link=Joan Boyar |title=Inferring sequences produced by pseudo-random number generators |journal=[[Journal of the ACM]] |year=1989 |volume=36 |issue=1 |pages=129–141 |doi=10.1145/58562.59305 |s2cid=3565772 |url=http://asterix.cs.gsu.edu/crypto/p129-boyar.pdf}} (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).

==External links==
* The simulation [http://www.vias.org/simulations/simusoft_lincong.html Linear Congruential Generator] visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
* [https://web.archive.org/web/20081211083300/http://www.cs.virginia.edu/~rjg7v/annotated.html Security of Random Number Generation: An Annotated Bibliography]
* [https://web.archive.org/web/20090108194540/http://www.math.niu.edu/~rusin/known-math/99/LCG Linear Congruential Generators post to sci.math]
* [http://www.goldsteintech.com/art.php 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, [http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf "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.
* [https://web.archive.org/web/20150616223328/http://yurichev.com/blog/modulo/ Article about another way of cracking LCG]

{{DEFAULTSORT:Linear Congruential Generator}}
[[Category:Pseudorandom number generators]]
[[Category:Modular arithmetic]]
[[Category:Articles with example Python (programming language) code]]