The Mersenne twister is a pseudorandom number generator linked to CR developed in 1997 by Makoto Matsumoto (松本 眞, Makoto Matsumoto^?) and Takuji Nishimura (西村 拓士, Takuji Nishimura^?)^[1] that is based on a matrix linear recurrence over a finite binary field F₂. It provides for fast generation of very high quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms. A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. ...

Its name derives from the fact that period length is chosen to be a Mersenne prime. There are at least two common variants of the algorithm, differing only in the size of the Mersenne primes used. The newer and more commonly used one is the Mersenne Twister MT19937, with 32-bit word length. There is also a variant with 64-bit word length, MT19937-64, which generates a different sequence. In mathematics, a Mersenne number is a number that is one less than a power of two. ...

Application

Unlike Blum Blum Shub, the algorithm in its native form is not suitable for cryptography. Observing a sufficient number of iterates (624 in the case of MT19937) allows one to predict all future iterates. Combining the Mersenne twister's outputs with a hash function solves this problem, but slows down generation. Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ... A hash function is a reproducible method of turning some kind of data into a (relatively) small number that may serve as a digital fingerprint of the data. ...

Another issue is that it can take a long time to turn a non-random initial state into output that passes randomness tests, due to its size. A small Lagged Fibonacci generator or Linear congruential generator gets started much quicker and is usually used to seed the Mersenne Twister. If only a few numbers are required and standards aren't high it is simpler to use the seed generator. But the Mersenne Twister will still work. There are many practical measures of randomness for a binary sequence. ... A Lagged Fibonacci generator (LFG) is an example of a pseudorandom number generator. ... Linear congruential generators (LCGs) represent one of the oldest and best-known pseudorandom number generator algorithms. ...

For many other applications, however, the Mersenne twister is fast becoming the pseudorandom number generator of choice. Since the library is portable, freely available and quickly generates good quality pseudorandom numbers it is rarely a bad choice.

It is designed with Monte carlo simulations and other statistical simulations in mind. Researchers primarily want good quality numbers but also benefit from its speed and portability. Monte Carlo methods are algorithms for solving various kinds of computational problems by using random numbers (or more often pseudo-random numbers), as opposed to deterministic algorithms. ...

Advantages

The commonly used variant of Mersenne Twister, MT19937 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). In practice, there is little reason to use larger ones, as most applications do not require 2¹⁹⁹³⁷ unique combinations (in decimal, 2¹⁹⁹³⁷ is approximately 4.315425 × 10⁶⁰⁰¹).
2. It has a very high order of dimensional equidistribution (see linear congruential generator). Note that this means, by default, that there is negligible[elaborate] serial correlation between successive values in the output sequence.
3. It is faster than all but the most statistically unsound generators^{[dubious – discuss]}.
4. It passes numerous tests for statistical randomness, including the stringent Diehard tests.

Equidistributed is a property of a bounded sequence of numbers. ... Linear congruential generators (LCGs) represent one of the oldest and best-known pseudorandom number generator algorithms. ... The Diehard tests are a battery of statistical tests for measuring the quality of a set of random numbers. ...

Algorithmic detail

The Mersenne Twister algorithm is a twisted generalised feedback shift register^[2] (twisted GFSR, or TGFSR) of rational normal form (TGFSR(R)), with state bit reflection and tempering. It is characterized by the following quantities:

• w: word size (in number of bits)
• n: degree of recurrence
• m: middle word, or the number of parallel sequences, 1 ≤ m ≤ n
• r: separation point of one word, or the number of bits of the lower bitmask, 0 ≤ r ≤ w - 1
• a: coefficients of the rational normal form twist matrix
• b, c: TGFSR(R) tempering bitmasks
• s, t: TGFSR(R) tempering bit shifts
• u, l: additional Mersenne Twister tempering bit shifts

with the restriction that 2^nw − r − 1 is a Mersenne prime. This choice simplifies the primitivity test and k-distribution test that are needed in the parameter search.

For a word x with w bit width, it is expressed as the recurrence relation

with | as the bitwise or and ⊕ as the bitwise exclusive or (XOR), x^u, x^l being x with upper and lower bitmasks applied. The twist transformation A is defined in rational normal form OR logic gate. ... Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ...

with I_n − 1 as the (n − 1) × (n − 1) identity matrix (and in contrast to normal matrix multiplication, bitwise XOR replaces addition). The rational normal form has the benefit that it can be efficiently expressed as

where

In order to achieve the 2^nw − r − 1 theoretical upper limit of the period in a TGFSR, φ_B(t) must be a primitive polynomial, φ_B(t) being the characteristic polynomial of A primitive polynomial may refer to one of two concepts, which are : A polynomial over a unique factorization domain (such as the integers) whose greatest common divisor of its coefficients is one. ... In linear algebra, one associates a polynomial to every square matrix, its characteristic polynomial. ...

The twist transformation improves the classical GFSR with the following key properties:

• Period reaches the theoretical upper limit 2^nw − r − 1 (except if initialized with 0)
• Equidistribution in n dimensions (e.g. linear congruential generators can at best manage reasonable distribution in 5 dimensions)

As like TGFSR(R), the Mersenne Twister is cascaded with a tempering transform to compensate for the reduced dimensionality of equidistribution (because of the choice of A being in the rational normal form), which is equivalent to the transformation A = R → A = T⁻¹RT, T invertible. The tempering is defined in the case of Mersenne Twister as Linear congruential generators (LCGs) represent one of the oldest and best-known pseudorandom number generator algorithms. ...

y := x ⊕ (x >> u)

y := :y ⊕ ((y << s) & b)

y := :y ⊕ ((y << t) & c)

z := y ⊕ (y >> l)

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. AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ...

The coefficients for MT19937 are:

• (w, n, m, r) = (32, 624, 397, 31)
• a = 9908B0DF₁₆
• u = 11
• (s, b) = (7, 9D2C5680₁₆)
• (t, c) = (15, EFC60000₁₆)
• l = 18

Pseudocode

The following generates uniformly 32 bit integers in the range [0, 2³² − 1] with the MT19937 algorithm:

 // Create a length 624 array to store the state of the generator var int[0..623] MT var int y // Initialise the generator from a seed function initialiseGenerator ( 32-bit int seed ) { MT[0] := seed for i from 1 to 623 { // loop over each other element MT[i] := last_32bits_of(1812433253 * (MT[i-1] bitwise_xor right_shift_by_30_bits(MT[i-1])) + i) } } // Generate an array of 624 untempered numbers function generateNumbers() { for i from 0 to 623 { y := 32nd_bit_of(MT[i]) + last_31bits_of(MT[(i+1)%624]) if y even { MT[i] := MT[(i + 397) % 624] bitwise xor (right_shift_by_1_bit(y)) } else if y odd { MT[i] := MT[(i + 397) % 624] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615) // 0x9908b0df } } } // Extract a tempered pseudorandom number based on the i-th value // generateNumbers() will have to be called again once the array of 624 numbers is exhausted function extractNumber(int i) { y := MT[i] y := y bitwise_xor (right_shift_by_11_bits(y)) y := y bitwise_xor (left_shift_by_7_bits(y) bitwise_and (2636928640)) // 0x9d2c5680 y := y bitwise_xor (left_shift_by_15_bits(y) bitwise_and (4022730752)) // 0xefc60000 y := y bitwise_xor (right_shift_by_18_bits(y)) return y } 

In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ...

SFMT

Please help improve this article by expanding this section. See talk page for details. Please remove this message once the section has been expanded.

SIMD-oriented Fast Mersenne Twister (SFMT). SFMT is a variant of Mersenne Twister, introduced in 2006^[3], designed to be fast when it runs on 128-bit SIMD. Image File history File links This is a lossless scalable vector image. ...

• It is roughly twice as fast as Mersenne Twister.^[4]
• It has a better equidistribution property of v-bit accuracy than MT but worse than WELL.
• It has quicker recovery from zero-excess initial state than MT, but slower than WELL.
• It supports various periods from 2⁶⁰⁷-1 to 2²¹⁶⁰⁹¹-1.

Intel SSE2 and PowerPC AltiVec are supported by SFMT. In mathematics, a bounded sequence (sn)n = 1, 2, 3, ... of real numbers is said to be equidistributed on an interval [a, b] if for any subinterval [c, d] of [a, b] we have i. ... SSE2, Streaming Single Instruction, Multiple Data Extensions 2, is one of the IA-32 SIMD instruction sets, first introduced by Intel with the initial version of the Pentium 4 in 2001. ... PowerPC is a RISC microprocessor architecture created by the 1991 Apple–IBM–Motorola alliance, known as AIM. Originally intended for personal computers, PowerPC CPUs have since become popular embedded and high-performance processors as well. ...

References

External links

• The academic paper for MT, and related articles by Makoto Matsumoto
• Mersenne Twister home page, with codes in C, Fortran, Java, Lisp and some other languages
• The GNU Scientific Library (GSL), containing an implementation of the Mersenne Twister
• Fast implementations of the Mersenne Twister in C and C++
• An implementation of the Mersenne Twister algorithm in C++
• Two good implementations of Mersenne Twister in Java, including the fastest known Java implementation
• Java implementations of both the 32 and 64 bit versions
• Implementation of Mersenne Twister for Java
• Implementation of Mersenne Twister for REALbasic (requires REALbasic 2006r1 or greater)
• Implementation of Mersenne Twister for Lisp
• Implementation of Mersenne Twister in Euphoria
• Implementation of Mersenne Twister for C#
• Implementation of Mersenne Twister for Ada
• Implementation of Mersenne Twister for Fortran 95
• Implementation of Mersenne Twister for Mathematica
• Implementation of Mersenne Twister for MATLAB
• Implementation of Mersenne Twister for Clean
• High-speed Implementation of Mersenne Twister in Linoleum (a cross-platform Assembler), by Herbert Glarner
• Implementation of Mersenne Twister as an add-in for Microsoft Excel
• CPAN module implementing the Mersenne Twister for use with Perl
• Implementation of Mersenne Twister for Haskell
• Implementation of Mersenne Twister for Standard ML
• It also is implemented in gLib and the standard libraries of at least PHP, Python and Ruby.
• SIMD-oriented Fast Mersenne Twister (SFMT)
• C++ class implementing Mersenne Twister and SFMT
• Flash Actionscript implementation of Mersenne Twister as a Class file