Editing Linear congruential generator (section)

{{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}}