View source for Well equidistributed long-period linear

{{short description|Family of pseudorandom number generators}}
The '''Well Equidistributed Long-period Linear (WELL)''' is a family of [[Pseudorandom number generator|pseudorandom number generator]]s developed in 2006 by François Panneton, Pierre L'Ecuyer, and {{nihongo|{{Interlanguage link multi|Makoto Matsumoto (mathematician)|lt=Makoto Matsumoto|ja|3=松本眞}}|松本 眞}}.<ref>{{Cite journal| doi = 10.1145/1132973.1132974| title = Improved long-period generators based on linear recurrences modulo 2| journal = ACM Transactions on Mathematical Software| volume = 32| number = 1| pages = 1&ndash;16| date = March 2006| last1 = Panneton | first1 = François O. | last2 = l'Ecuyer | first2 = Pierre | last3 = Matsumoto | first3 = Makoto | url = http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf| citeseerx = 10.1.1.73.5499| s2cid = 7368302}}</ref> It is a form of [[Linear-feedback shift register|linear-feedback shift register]] optimized for software implementation on a 32-bit machine.

== Operational design ==
The structure is similar to the [[Mersenne Twister]], a large state made up of previous output words (32 bits each), from which a new output word is generated using linear [[Recurrence relation|recurrences]] modulo 2 over a finite [[GF(2)|binary field]] <math>F_2</math>.  However, a more complex recurrence produces a denser generator polynomial, producing better statistical properties.

Each step of the generator reads five words of state: the oldest 32 bits (which may straddle a word boundary if the state size is not a multiple of 32), the newest 32 bits, and three other words in between. 

Then a series of eight single-word transformations (mostly of the form <math display=inline> x:= x\oplus(x\gg k)</math> and six exclusive-or operations combine those into two words, which become the newest two words of state, one of which will be the output.

== Variants ==

Specific parameters are provided for the following generators:
* WELL512a
* WELL521a, WELL521b
* WELL607a, WELL607b
* WELL800a, WELL800b
* WELL1024a, WELL1024b
* WELL19937a, WELL19937b, WELL19937c
* WELL21701a
* WELL23209a, WELL23209b
* WELL44497a, WELL44497b.  

Numbers give the state size in bits; letter suffixes denote variants of the same size.

== Implementations ==

* [http://www.iro.umontreal.ca/~panneton/WELLRNG.html Implementations of WELL512a, WELL1024a, WELL19937a, WELL19937c, WELL44497a, WELL44497b in C] (Free for non-commercial use)
* [https://github.com/non/spire/tree/v0.11.0/core/shared/src/main/scala/spire/random/rng/ Implementations of same algorithms in Scala]
* [https://github.com/sergiud/random/blob/master/well.hpp Implementations in C++]
* [http://www.iro.umontreal.ca/~simardr/ssj/doc/html/umontreal/iro/lecuyer/rng/RandomStreamBase.html Implementations of WELL512, WELL1024, WELL607 in Java]
* [http://bbcbasic.co.uk/wiki/doku.php?id=high_20quality_20random_20number_20generation Implementations of WELL512, WELL1024 in BBC BASIC]
* [http://www.ritsumei.ac.jp/~harase/megenerators.html Modified "maximally equidistributed" implementations of WELL19937, WELL44497 in C] (Free for non-commercial use)
* [http://lomont.org/papers/2008/Lomont_PRNG_2008.pdf  Implementation of WELL512 in C] (Public Domain)

==References==
{{Reflist}}

== External links ==
* [http://www.iro.umontreal.ca/~panneton/  The academic paper, and related articles by François Panneton]
* [http://www.iro.umontreal.ca/~lecuyer/papers.html Pierre L'Ecuyer's publications]

[[Category:Pseudorandom number generators]]



{{Sourceattribution|Well equidistributed long-period linear}}