Well equidistributed long-period linear

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 Makoto Matsumoto [ja] (松本眞).^[1] It is a form of linear-feedback shift register optimized for software implementation on a 32-bit machine.

Operational design edit

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 ${\textstyle 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 edit

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 edit

Implementations of WELL512a, WELL1024a, WELL19937a, WELL19937c, WELL44497a, WELL44497b in C (Free for non-commercial use)
Implementations of same algorithms in Scala
Implementations in C++
Implementations of WELL512, WELL1024, WELL607 in Java
Implementations of WELL512, WELL1024 in BBC BASIC
Modified "maximally equidistributed" implementations of WELL19937, WELL44497 in C (Free for non-commercial use)
Implementation of WELL512 in C (Public Domain)

References edit

^ Panneton, François O.; l'Ecuyer, Pierre; Matsumoto, Makoto (March 2006). "Improved long-period generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. CiteSeerX 10.1.1.73.5499. doi:10.1145/1132973.1132974. S2CID 7368302.

External links edit

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

[1] Panneton, François O.; l'Ecuyer, Pierre; Matsumoto, Makoto (March 2006). "Improved long-period generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. CiteSeerX 10.1.1.73.5499. doi:10.1145/1132973.1132974. S2CID 7368302.

[1]