Mersenne Twister


The Mersenne Twister is a pseudorandom number generator. It is by far the most widely used general-purpose PRNG. Its name derives from the fact that its period length is chosen to be a Mersenne prime.
The Mersenne Twister was developed in 1997 by and Takuji Nishimura. It 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 219937−1. The standard implementation of that, MT19937, uses a 32-bit word length. There is another implementation that uses a 64-bit word length, MT19937-64; it generates a different sequence.

Adoption in software systems

The Mersenne Twister is the default PRNG for the following software systems: Dyalog APL, Microsoft Excel, GAUSS, GLib, GNU Multiple Precision Arithmetic Library, GNU Octave, GNU Scientific Library, gretl, IDL, Julia, CMU Common Lisp, Embeddable Common Lisp, Steel Bank Common Lisp, Maple, MATLAB, Free Pascal, PHP, Python, R, Ruby, SageMath, Scilab, Stata.
It is also available in Apache Commons, in standard C++ , 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

An alternative generator, WELL, offers quicker recovery, and equal randomness, and nearly equal speed.
Marsaglia's xorshift generators and variants are the fastest in this class.
64-bit MELGs are completely optimized in terms of the k-distribution properties.
The ACORN family is another k-distributed PRNG, which shows similar computational speed to MT, and better statistical properties as it satisfies all the current TestU01 criteria; when used with appropriate choices of parameters, ACORN can have arbitrarily long period and precision.

''k''-distribution

A pseudorandom sequence xi of w-bit integers of period P is said to be k-distributed to v-bit accuracy if the following holds.

Algorithmic detail

For a w-bit word length, the Mersenne Twister generates integers in the range .
The Mersenne Twister algorithm is based on a matrix linear recurrence over a finite binary field F2. The algorithm is a twisted generalised feedback shift register of rational normal form, with state bit reflection and tempering. The basic idea is to define a series through a simple recurrence relation, and then output numbers of the form, where is an invertible F2 matrix called a tempering matrix.
The general algorithm is characterized by the following quantities :
with the restriction that 2nw − r − 1 is a Mersenne prime. This choice simplifies the primitivity test and k-distribution test that are needed in the parameter search.
The series x is defined as a series of w-bit quantities with the recurrence relation:
where denotes concatenation of bit vectors, the bitwise exclusive or, means the upper bits of, and means the lower bits of. The twist transformation A is defined in rational normal form as:
with In − 1 as the × identity matrix. The rational normal form has the benefit that multiplication by A can be efficiently expressed as:
where x0 is the lowest order bit of x.
As like TGFSR, the Mersenne Twister is cascaded with a tempering transform to compensate for the reduced dimensionality of equidistribution. Note that this is equivalent to using the matrix where for an invertible matrix, and therefore the analysis of characteristic polynomial mentioned [|below] still holds.
As with A, we choose a tempering transform to be easily computable, and so do not actually construct T itself. The tempering is defined in the case of Mersenne Twister as
where x is the next value from the series, y a temporary intermediate value, z the value returned from the algorithm, with <<, >> as the bitwise left and right shifts, and & as the bitwise and. The first and last transforms are added in order to improve lower-bit equidistribution. From the property of TGFSR, is required to reach the upper bound of equidistribution for the upper bits.
The coefficients for MT19937 are:
Note that 32-bit implementations of the Mersenne Twister generally have d = FFFFFFFF16. As a result, the d is occasionally omitted from the algorithm description, since the bitwise and with d in that case has no effect.
The coefficients for MT19937-64 are:
The state needed for a Mersenne Twister implementation is an array of n values of w bits each. To initialize the array, a w-bit seed value is used to supply x0 through xn − 1 by setting x0 to the seed value and thereafter setting
for i from 1 to n−1. The first value the algorithm then generates is based on xn, not on x0. The constant f forms another parameter to the generator, though not part of the algorithm proper. The value for f for MT19937 is 1812433253 and for MT19937-64 is 6364136223846793005.

Comparison with classical GFSR

In order to achieve the 2nw − r − 1 theoretical upper limit of the period in a TGFSR, φB must be a primitive polynomial, φB being the characteristic polynomial of
The twist transformation improves the classical GFSR with the following key properties:
The following pseudocode implements the general Mersenne Twister algorithm. The constants w, n, m, r, a, u, d, s, b, t, c, l, and f are as in the algorithm description above. It is assumed that int represents a type sufficient to hold values with w bits:
// Create a length n array to store the state of the generator
int MT
int index := n+1
const int lower_mask = - 1 // That is, the binary number of r 1's
const int upper_mask = lowest w bits of

// Initialize the generator from a seed
function seed_mt

// Extract a tempered value based on MT
// calling twist every n numbers
function extract_number

// Generate the next n values from the series x_i
function twist

Variants

CryptMT

is a stream cipher and cryptographically secure pseudorandom number generator which uses Mersenne Twister internally. It was developed by Matsumoto and Nishimura alongside Mariko Hagita and Mutsuo Saito. It has been submitted to the eSTREAM project of the eCRYPT network. Unlike Mersenne Twister or its other derivatives, CryptMT is patented.

MTGP

MTGP is a variant of Mersenne Twister optimised for graphics processing units published by Mutsuo Saito and Makoto Matsumoto. The basic linear recurrence operations are extended from MT and parameters are chosen to allow many threads to compute the recursion in parallel, while sharing their state space to reduce memory load. The paper claims improved equidistribution over MT and performance on a very old GPU of 4.7 ms for 5×107 random 32-bit integers.

SFMT

The SFMT is a variant of Mersenne Twister, introduced in 2006, designed to be fast when it runs on 128-bit SIMD.
Intel SSE2 and PowerPC AltiVec are supported by SFMT. It is also used for games with the Cell BE in the PlayStation 3.

TinyMT

TinyMT is a variant of Mersenne Twister, proposed by Saito and Matsumoto in 2011. TinyMT uses just 127 bits of state space, a significant decrease compared to the original's 2.5 KiB of state. However, it has a period of 2127−1, far shorter than the original, so it is only recommended by the authors in cases where memory is at a premium.