Mersenne twister
The
Mersenne twister is a
pseudorandom number generator that was developed in 1997 by Makoto Matsumoto and Takuji Nishimura. It provides for fast generation of very high quality random numbers - having been designed specifically to rectify many of the flaws found in older algorithms.
There are two variants of the algorithm, the newer and more commonly utilised one being the Mersenne Twister MT 19937. It has the following desirable properties:
- It was designed to have a colossal period of 219937-1 (the creators of the algorithm proved this property). This period, incidentally, explains the origin of the name: it is a Mersenne prime, and some of the guarantees of the algorithm depend on internal use of Mersenne primes. In practice, there is little reason to use larger ones.
- It has a very high order of dimensional equidistribution (see linear congruential generator). Note that this means, by default, that there is negligible serial correlation between successive values in the output sequence.
- It is faster than all but the most statistically unsound generators.
- It is statistically random in all the bits of its output.
The algorithm itself is a Twisted generalised shift feedback register or TGSFR for short. The 'twist' is a transformation which assures equidistribution of the generated numbers in 623 dimensions (linear congruential generators can at best manage reasonable distribution in 5 dimensions).
Unlike, for example, Blum Blum Shub, the algorithm in its native form is not suitable for cryptography. For many other applications, however, it is fast becoming the random number generator of choice.
References:
- M. Matsumoto and T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations, 1998.
External links: