Editing Linear congruential generator (section)

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