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:

1. It was designed to have a colossal period of 2¹⁹⁹³⁷-1 (the creators of the algorithm proved this property). This period, incidentally, explains the origin of the name: it is a Mersenne prime.
2. It has a very high order of dimensional equidistribution (see Linear Congruential Generators). Note that this means, by default, that there is negligible serial correlation between successive values in the output sequence.
3. It is faster than all but the most statistically unsound generators.
4. 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:

• Mersenne Twister home page (http://www.math.keio.ac.jp/~matumoto/emt)
• A claimed implementation of the Mersenne Twister algorithm (http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister)
• Another paper on the Mersenne Twister algorithm (http://citeseer.nj.nec.com/313273)