Login
Login

Well equidistributed long-period linear

{{short description|Family of pseudorandom number generators}}

{{multiple issues|

{{One source|date=November 2017}}

{{EL|date=November 2017}}

}}

The Well Equidistributed Long-period Linear (WELL) is a family of pseudorandom number generators developed in 2006 by François Panneton, Pierre L'Ecuyer, and {{nihongo|{{Interlanguage link multi|Makoto Matsumoto (mathematician)|lt=Makoto Matsumoto|ja|3=松本眞}}|松本 眞}}.{{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–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}} It is a form of 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 recurrences modulo 2 over a finite binary field F_2. 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 x:= x\oplus(x\gg k) 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

  • [https://web.archive.org/web/20240726180537/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