Editing Pseudorandom number generator (section)

==Generators based on linear recurrences==
In the second half of the 20th century, the standard class of algorithms used for PRNGs comprised [[linear congruential generator]]s. The quality of LCGs was known to be inadequate, but better methods were unavailable.  Press et&nbsp;al. (2007) described the result thus: "If all scientific papers whose results are in doubt because of [LCGs and related] were to disappear from library shelves, there would be a gap on each shelf about as big as your fist."<ref>Press et&nbsp;al. (2007) §7.1</ref>

A major advance in the construction of pseudorandom generators was the introduction of techniques based on linear recurrences on the two-element field; such generators are related to [[linear-feedback shift register]]s.

The 1997 invention of the [[Mersenne Twister]],<ref>{{cite journal|last=Matsumoto|first=Makoto|author2=Nishimura, Takuji |title=Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator|journal=ACM Transactions on Modeling and Computer Simulation|year=1998|volume=8|issue=1|pages=3–30|doi=10.1145/272991.272995|publisher=[[Association for Computing Machinery|ACM]]|s2cid=3332028 |url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf}}</ref> in particular, avoided many of the problems with earlier generators. The Mersenne Twister has a period of 2<sup>19&nbsp;937</sup>&nbsp;−&nbsp;1 iterations (≈&nbsp;4.3{{e|6001}}), is proven to be [[equidistributed]] in (up to) 623 dimensions (for 32-bit values), and at the time of its introduction was running faster than other statistically reasonable generators.

In 2003, [[George Marsaglia]] introduced the family of [[xorshift]] generators,<ref>{{cite journal
| first=George
| last=Marsaglia
| title=Xorshift RNGs
| journal=[[Journal of Statistical Software]]
| volume=8
| issue=14
|date=July 2003
| doi=10.18637/jss.v008.i14
 | doi-access=free| s2cid=250501391
| url=http://www.jstatsoft.org/v08/i14/paper
}}</ref> again based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, they pass strong statistical tests.<ref>{{cite web|author=S.Vigna|title=xorshift*/xorshift+ generators and the PRNG shootout|url=http://prng.di.unimi.it}}</ref><ref>Vigna S. (2016), "An experimental exploration of Marsaglia’s xorshift generators", <em>[[ACM Transactions on Mathematical Software]]</em>, 42; {{doi|10.1145/2845077}}.</ref><ref>Vigna S. (2017), "Further scramblings of Marsaglia’s xorshift generators", <em>Journal of Computational and Applied Mathematics</em>, 315; {{doi|10.1016/j.cam.2016.11.006}}.</ref>

In 2006, the [[well equidistributed long-period linear|WELL]] family of generators was developed.<ref>{{cite journal|last1=Panneton|first1=François| author2=L'Ecuyer, Pierre| author3=Matsumoto, Makoto |title= Improved long-period generators based on linear recurrences modulo 2| journal=[[ACM Transactions on Mathematical Software]] |year=2006|volume=32|issue=1|pages=1–16| doi=10.1145/1132973.1132974|s2cid=7368302 |url=http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf}}</ref> The WELL generators in some ways improves on the quality of the Mersenne Twister, which has a too-large state space and a very slow recovery from state spaces with a large number of zeros.