The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by and . Its name derives from the fact that its period length is chosen to be a Mersenne prime.
The Mersenne Twister was designed specifically to rectify most of the flaws found in older PRNGs.
The most commonly used version of the Mersenne Twister algorithm is based on the Mersenne prime . The standard implementation of that, MT19937, uses a 32-bit word length. There is another implementation (with five variants) that uses a 64-bit word length, MT19937-64; it generates a different sequence.
Application
Software
The Mersenne Twister is used as default PRNG by the following software:
Programming languages: Dyalog APL, IDL, R, Ruby, Free Pascal, PHP, Python (also available in NumPy, however the default was changed to PCG64 instead as of version 1.17), CMU Common Lisp, Embeddable Common Lisp, Steel Bank Common Lisp, Julia (up to Julia 1.6 LTS, still available in later, but a better/faster RNG used by default as of 1.7) Linux libraries and software: GLib, GNU Multiple Precision Arithmetic Library, GNU Octave, GNU Scientific Library Other: Microsoft Excel, GAUSS, gretl, Stata, SageMath, Scilab, Maple, MATLAB
It is also available in Apache Commons, in the standard C++ library (since C++11), and in Mathematica. Add-on implementations are provided in many program libraries, including the Boost C++ Libraries, the CUDA Library, and the NAG Numerical Library.
The Mersenne Twister is one of two PRNGs in SPSS: the other generator is kept only for compatibility with older programs, and the Mersenne Twister is stated to be "more reliable". The Mersenne Twister is similarly one of the PRNGs in SAS: the other generators are older and deprecated. The Mersenne Twister is the default PRNG in Stata, the other one is KISS, for compatibility with older versions of Stata.
Advantages
Permissively-licensed and patent-free for all variants except CryptMT. Passes numerous tests for statistical randomness, including the Diehard tests and most, but not all of the TestU01 tests. A very long period of . Note that while a long period is not a guarantee of quality in a random number generator, short periods, such as the common in many older software packages, can be problematic. k-distributed to 32-bit accuracy for every (for a definition of k-distributed, see below) Implementations generally create random numbers faster than hardware-implemented methods. A study found that the Mersenne Twister creates 64-bit floating point random numbers approximately twenty times faster than the hardware-implemented, processor-based RDRAND instruction set.
Disadvantages
Relatively large state buffer, of almost 2.5 kB, unless the TinyMT variant (discussed below) is used. Mediocre throughput by modern standards, unless the SFMT variant (discussed below) is used. Exhibits two clear failures (linear complexity) in both Crush and BigCrush in the TestU01 suite. The test, like Mersenne Twister, is based on an -algebra. Multiple instances that differ only in seed value (but not other parameters) are not generally appropriate for Monte-Carlo simulations that require independent random number generators, though there exists a method for choosing multiple sets of parameter values. Poor diffusion: can take a long time to start generating output that passes randomness tests, if the initial state is highly non-random—particularly if the initial state has many zeros. A consequence of this is that two instances of the generator, started with initial states that are almost the same, will usually output nearly the same sequence for many iterations, before eventually diverging. The 2002 update to the MT algorithm has improved initialization, so that beginning with such a state is very unlikely. The GPU version (MTGP) is said to be even better. Contains subsequences with more 0's than 1's. This adds to the poor diffusion property to make recovery from many-zero states difficult. Is not cryptographically secure, unless the CryptMT variant (discussed below) is used. The reason is that observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations.
Alternatives
An alternative generator, WELL ("Well Equidistributed Long-period Linear"), offers quicker recovery, and equal randomness, and nearly equal speed.
Marsaglia's xorshift generators and variants are the fastest in the class of LFSRs.