Well Equidistributed Long-Period Linear

The Well Equidistributed Long-period Linear (short: WELL ) is a pseudo-random number generator that was developed in 2006 by François Panneton and Pierre L'Ecuyer. It was designed to quickly generate evenly distributed pseudo-random numbers with extremely long periods and is based on linear recursion equations .

properties

WELL random number generators with period lengths of (with k ∈ {512, 607, 800, 1024, 19937, 21701, 23209, 44497}) have very long period lengths with little effort (in power notation between about 10 ¹⁵⁴ and about 10 ^{13 395} ). They generate highly evenly distributed sequences. In this regard, the generated random numbers are even of a higher quality than those of the Mersenne Twister , with WELL delivering random numbers just as quickly as the Mersenne Twister. ${\displaystyle 2^{k}-1}$

Its properties make WELL particularly suitable for use in statistical simulations (e.g. Monte Carlo simulation ). In contrast, the WELL, like the Mersenne Twister (and all other LRGs), is not directly suitable for cryptographic applications. With a comparatively short observation of its expenses, its internal state can be determined and thus all future numbers can be predicted. This problem can be circumvented by collecting several output words in a block and then applying a secure hash function (e.g. SHA-256 ) to these .

algorithm

${\displaystyle z_{0}\leftarrow rot_{p}(v_{i,r-2}^{T},v_{i,r-1}^{T})^{T};}$

${\displaystyle z_{1}\leftarrow T_{0}v_{i,0}\oplus T_{1}v_{i,m_{1}};}$

${\displaystyle z_{2}\leftarrow T_{2}v_{i,m_{2}}\oplus T_{3}v_{i,m_{3}}}$

${\displaystyle z_{3}\leftarrow z_{1}\oplus z_{2}}$

${\displaystyle v_{i+1,r-1}\leftarrow v_{i,r-2}\wedge m_{p}}$

${\displaystyle {\begin{aligned}{\text{for}}~&j:=r-2,\dots ,2\quad {\text{do}}\\\quad &v_{i+1,j}\leftarrow v_{i,j-1}\end{aligned}}}$

${\displaystyle v_{i+1,1}\leftarrow z_{3}}$

${\displaystyle v_{i+1,0}\leftarrow z_{4}}$

Output: or . ${\displaystyle y_{i}=v_{i,1}}$ ${\displaystyle y_{i}=v_{i,0}}$

initialization

For initialization, the status array is set to any (random) values. These initial values ​​primarily represent only one position in the long bit sequence at which the generator starts. ${\displaystyle 2^{k}-1}$

The initialization with only zeros leads to the constant output of the value 0 (this is the second possible cycle of the random number generator with the period length 1). If, on the other hand, there are only many (but not all) bits of the status word "0", the WELL and the Mersenne Twister (and all (!) Other LRGs) initially no longer deliver evenly distributed random numbers. This case can occur if the initialization was poor.

It is precisely here that the WELL generators prove to be superior to the Mersenne Twister and its little brother, the TT800 : after a few hundred steps (e.g. 700 for the WELL-19937) they again deliver a uniformly distributed bit sequence. The Mersenne Twister takes up to 700,000 steps and the TT800 still more than 60,000.

Period length

The WELL generators are designed in such a way that they have a maximum period length for linear feedback generators, ie they run through the entire state space (except for 0). The period is 2 ^k -1, in power notation about 10 ^{0.3 · k} . k here is the order of the characteristic polynomial P (z) of the transition matrix A .

Implementation in C

The implementation in C for the WELL1024a is shown here as an example. The generator delivers uniformly distributed random numbers on the interval [0, 2 ³² -1].

#include <stdint.h>

#define R   32      /* Anzahl der Worte im Zustandsregister */

#define M1   3
#define M2  24
#define M3  10

#define MAT0POS(t,v)  (v ^ (v >>  (t)))
#define MAT0NEG(t,v)  (v ^ (v << -(t)))
#define Identity(v)   (v)

#define V0            State[ i        ]
#define VM1           State[(i+M1) % R]
#define VM2           State[(i+M2) % R]
#define VM3           State[(i+M3) % R]
#define VRm1          State[(i+31) % R]

#define newV0         State[(i+31) % R]
#define newV1         State[ i        ]

/* Der Zustandsvektor muss mit (pseudo-)zufälligen Werten initialisiert werden. */
static uint32_t State[R];

uint32_t WELL1024()
{
  static uint32_t i = 0;
  uint32_t        z0;
  uint32_t        z1;
  uint32_t        z2;

  z0    = VRm1;
  z1    = Identity( V0)      ^ MAT0POS ( +8, VM1);
  z2    = MAT0NEG (-19, VM2) ^ MAT0NEG (-14, VM3);
  newV1 = z1                 ^ z2;
  newV0 = MAT0NEG (-11,  z0) ^ MAT0NEG ( -7,  z1) ^ MAT0NEG (-13,  z2);
  i     = (i + R - 1) % R;

  return State[i];
}

See also

• List of random number generators

Web links

• Implementation of the authors (k = 512, 1024, 19937, 44497)
• Implementations of other WELL

Individual evidence

1. ↑ ^{a b c} F. Panneton, P. L'Ecuyer: Improved Long-Period Generators Base on Linear Recurrences Modulo 2 (PDF; 301 kB) .
2. ^ M. Matsumoto: Mersenne Twister Homepage
3. ↑ M. Matsumoto: Mersenne Twister FAQ
4. ^ F. Panneton, P. L'Ecuyer: Homepage of the WELL RNG