Well Equidistributed Long-period Linear
The Well Equidistributed Long -period Linear ( short: WELL ) is a pseudo-random number generator, which was developed in 2006 by François Panneton and Pierre L' Ecuyer. It was designed to rapidly generate uniformly distributed pseudo-random numbers with extremely long period and is based on linear recurrences.
Properties
Have WELL random number generators with period lengths of ( with k ∈ { 512, 607, 800, 1024, 19937, 21701, 23209, 44497 }) with little effort very long period lengths ( in power notation between about 10154 and about 1,013,395 ). To generate highly uniformly distributed sequences. In this regard, the generated random numbers have an even higher quality than that of Mersenne Twister, which also WELL as fast as the Mersenne Twister delivers random numbers.
Its characteristics make WELL particularly for use in statistical simulations (eg Monte Carlo simulation ). In contrast, the WELL is just like the Mersenne Twister (and all other LRGs ) for cryptographic applications not directly suitable. In a relatively short observation of its expenditures may be internal state are determined and so all future numbers are predicted. This problem can be circumvented by collecting multiple output words in a block and on this then apply a secure hash function (eg SHA- 256).
Algorithm
Edition: or.
Initialization
To initialize the state array is set to any (random) values . These initial values are primarily represents only one position in the long bit sequence, in which the generator starts.
Initializing with only zeros leads to the constant output value of 0 ( which is the second potential cycle of the random number generator with period length 1). By contrast, if only many (but not all) bits of the status word is "0", the WELL as well as the Mersenne Twister delivers (and all (!) Other LRGs ) not initially uniformly distributed random numbers more. This case can occur if poorly initialized.
Right here prove the WELL generators with respect to the Mersenne Twister and its little brother, the TT800, as superior: they provide after a few hundred steps ( eg 700 for the WELL - 19937 ) again a uniformly distributed bit sequence. The Mersenne Twister needed here up to 700,000 steps and the TT800 is still more than 60,000.
Period length
The WELL generators are designed so that they have a maximum for linear feedback generators period length, ie the entire state space through (except 0). The period is 2k -1, in power notation about 100.3 * k Here, k is the order of the characteristic polynomial P (z) of the transition matrix A
Implementation in C
Here, the implementation in C is shown as an example for the WELL1024a. The generator delivers uniformly distributed random numbers on the interval [0, 232-1 ].
# include