Well equidistributed long-period linear explained

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 .^[1] It is a form of linear-feedback shift register optimized for software implementation on a 32-bit machine.

Operational design

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\backslash oplus(x\backslash 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

• 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)

External links

• The academic paper, and related articles by François Panneton
• Pierre L'Ecuyer's publications

Notes and References

1. 10.1145/1132973.1132974. Improved long-period generators based on linear recurrences modulo 2. ACM Transactions on Mathematical Software. 32. 1. 1 - 16. March 2006. Panneton . François O. . l'Ecuyer . Pierre . Matsumoto . Makoto . 10.1.1.73.5499. 7368302.