Mersenne-Twister
The Mersenne Twister is a pseudorandom number generator that was developed in 1997 by Makoto Matsumoto and Takuji Nishimura. It generates sequences of pseudo-random numbers and was tailored to overcome the problems of older algorithms (such as linear congruential generators ).
There are two variants of this algorithm; the newer and more common is the Mersenne Twister " MT 19937 ", which is described here.
Properties
On the other hand it has the disadvantage of working on a large amount of data of about 2.5 KB ( 624 words of 32 bits each ). This can result in a performance impact on computer architectures with a relatively small cache and slower memory.
The word "Twister " refers to a specific transformation of the algorithm is ensured by the high level of this uniform distribution (pure linear congruential generators can guarantee a reasonable cost only five-dimensional uniform distribution ).
An n-dimensional uniform distribution means divide the output sequence in each tuple of n numbers, the sequence of n- tuples is uniformly distributed in the n- dimensional space.
Unlike other algorithms, the Mersenne Twister is not suitable in its pure form for cryptographic applications. For many other applications, but it will already be used successfully.
Algorithm
The values to ( with ) can be specified as start values . The other values are calculated as follows:
The symbol denotes the bitwise XOR operation, and "hex " stands for hexadecimal. The symbol is the floor function and indicates the rounded value of, i.e. the largest integer which is not larger than the argument in the parenthesis.
To ensure that the 623- dimensional uniform distribution for all 32 bits are still modified:
It stands for the bitwise AND operation.
The thus calculated are used as random numbers.
Initialization
As initial values to be selected ideally truly random numbers, for example, can be generated by a physical random number generator. But it can also be pseudo-random numbers used by another generator.
It may not be all of the bits that make up the state of the Mersenne Twister, initialized to zero, otherwise it generates only zero as a " random" number. These are the most significant bit in as well as all the bits in the remaining variables to.
The less random the starting values are ( ie the more unequal the bits are distributed ), the longer is the " warm up " the needs of the Mersenne Twister, until he spends a good pseudo-random numbers. The worst possible initialization consists of a single 1- bit and otherwise zeros. After that requires the Mersenne Twister over 700,000 Views, until he delivers a uniformly distributed bit sequence. If in doubt, you should therefore be generated 800,000 random numbers before using the numbers. Alternatively, there are also modern generators that have much shorter recovery times, such as the WELL or Marsaglias Xorshift.
However, you can also save the initialization with another PRNG in this way (if you do not trust this example ): you bet ( in the code y) on a random seed value (such as time) and all the others on 0 ( in the C code they are usually due to the static attribute already ). Then just call it the generator to 800,000 times.
Code
These calculations can be implemented efficiently, for example in C code. The following function always calculates N = 624 words at a time, and then they are read from the vector y, in order:
# include
Matsumoto and Nishimura developed previously a "little brother" of the Mersenne Twister with the name TT800. It operates on the same principle, but on a smaller data set of only 25 words, and its algorithm is a little easier because not three but only two old 32 -bit status words will be charged for the calculation of the next state word. Its period length is 2800-1 ( ≈ 6.7 x 10240 ).
# include