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 (松本 眞).[1] 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 [math]\displaystyle{ 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]\displaystyle{ 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
- 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
- ↑ Panneton, François O.; l'Ecuyer, Pierre; Matsumoto, Makoto (March 2006). "Improved long-period generators based on linear recurrences modulo 2". ACM Transactions on Mathematical Software 32 (1): 1–16. doi:10.1145/1132973.1132974. http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf.
External links
 |  |
