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 used 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 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.
2. 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.
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, with C code
• Another paper on the Mersenne Twister algorithm
• The GNU Scientific Library (GSL), containing an implementation of the Mersenne Twister
• A claimed implementation of the Mersenne Twister algorithm
• Implementation of Mersenne Twister for Lisp
• Implementation of Mersenne Twister for Ada
• Implementation of Mersenne Twister as an add-in for Microsoft Excel

• It also is, apparently, implemented in gLib and the standard libraries of at least Python and Ruby.