The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士). Its name derives from the choice of a Mersenne prime as its period length. The Mersenne Twister was created specifically to address most of the flaws found in earlier PRNGs. The most commonly used version of the Mersenne Twister algorithm is based on the Mersenne prime 2 19937 − 1 {\displaystyle 2^{19937}-1} . 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 which generates a different sequence.
k-distribution A pseudorandom sequence x i {\displaystyle x_{i}} of w {\displaystyle w} -bit integers of period P {\displaystyle P} is said to be k {\displaystyle k} -distributed to v {\displaystyle v} -bit accuracy if the following holds:
Let trunc v ( x ) {\displaystyle \operatorname {trunc} _{v}(x)} denote the number formed by the leading v {\displaystyle v} bits of x {\displaystyle x} , and consider P {\displaystyle P} of the k v {\displaystyle kv} -bit vectors
( trunc v ( x i ) , trunc v ( x i + 1 ) , … , trunc v ( x i + k − 1 ) ) {\displaystyle (\operatorname {trunc} _{v}(x_{i}),\operatorname {trunc} _{v}(x_{i+1}),\dots ,\operatorname {trunc} _{v}(x_{i+k-1}))}
for 0 ≤ i < P {\displaystyle 0\leq i<P} . Then each of the 2 k v {\displaystyle 2^{kv}} possible combinations of bits occurs the same number of times in a period, except for the all-zero combination that occurs once less often.
Algorithmic detail
For a w-bit word length, the Mersenne Twister generates integers in the range [ 0 , 2 w − 1 ] {\displaystyle [0,2^{w}-1]} . The Mersenne Twister algorithm is based on a matrix linear recurrence over the finite field F 2 {\displaystyle \mathbb {F} _{2}} . The algorithm is a twisted generalised feedback shift register (twisted GFSR, or TGFSR) of rational normal form (TGFSR(R)), with state bit reflection and tempering. The basic idea is to define a series x i {\displaystyle x_{i}} through a simple recurrence relation, and then output numbers of the form x i T {\displaystyle x_{i}^{T}} , where T {\displaystyle T} is an invertible F 2 {\displaystyle \mathbb {F} _{2}} -matrix called a tempering matrix. The general algorithm is characterized by the following quantities:
w {\displaystyle w} : word size (in number of bits)
n {\displaystyle n} : degree of recurrence
m {\displaystyle m} : middle word, an offset used in the recurrence relation defining the series x {\displaystyle x} , 1 ≤ m < n {\displaystyle 1\leq m<n}
r {\displaystyle r} : separation point of one word, or the number of bits of the lower bitmask, 0 ≤ r ≤ w − 1 {\displaystyle 0\leq r\leq w-1}
a {\displaystyle a} : coefficients of the rational normal form twist matrix
b , c {\displaystyle b,c} : TGFSR(R) tempering bitmasks
s , t {\displaystyle s,t} : TGFSR(R) tempering bit shifts
u , d , l {\displaystyle u,d,l} : additional Mersenne Twister tempering bit shifts/masks with the restriction that 2 n w − r − 1 {\displaystyle 2^{nw-r}-1} is a Mersenne prime. This choice simplifies the primitivity test and k-distribution test needed in the parameter search. The series x {\displaystyle x} is defined as a series of w {\displaystyle w} -bit quantities with the recurrence relation:
… excerpt ends here. Continue reading the full article.
