Editing Linear congruential generator (section)

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