Mersenne twister
|
|
The Mersenne twister is a pseudorandom number generator that was developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士).
Mersenne twisters provide 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 at least two common variants of the algorithm only different in size with respect to the size of the Mersenne Primes used. The newer and more commonly used one being the Mersenne Twister MT 19937.
MT 19937 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 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.
How the algorithm functions
The algorithm itself is a twisted generalised shift feedback register or TGSFR for short (a twisted generalized linear feedback shift register). 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 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 (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html)
- The GNU Scientific Library (GSL), containing an implementation of the Mersenne Twister (http://www.gnu.org/software/gsl/)
- A claimed implementation of the Mersenne Twister algorithm (http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.html)
- Implementation of Mersenne Twister for Lisp (http://lisp-p.org/jmt/)
- Implementation of Mersenne Twister for Ada (http://adrianhoe.com/adrianhoe/adamt19937/)
- Implementation of Mersenne Twister as an add-in for Microsoft Excel (http://www.numtech.com/NtRand/)
- It also is, apparently, implemented in gLib and the standard libraries of at least Python and Ruby.