Mersenne Twister - Algorithmic Detail

Algorithmic Detail

The Mersenne Twister algorithm is a twisted generalised feedback shift register (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 2nw − 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), xu, xl being x with upper and lower bitmasks applied. The twist transformation A is defined in rational normal form

$A = R = \begin{pmatrix} 0 & I_{w - 1} \\ a_{w-1} & (a_{w - 2}, \ldots, a_0) \end{pmatrix}$

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

$\boldsymbol{x}A = \begin{cases}\boldsymbol{x} \gg 1 & x_0 = 0\\(\boldsymbol{x} \gg 1) \oplus \boldsymbol{a} & x_0 = 1\end{cases}$

where

In order to achieve the 2nw − 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

$B = \begin{pmatrix} 0 & I_{w} & \cdots & 0 & 0 \\ \vdots & & & & \\ I_{w} & \vdots & \ddots & \vdots & \vdots \\ \vdots & & & & \\ 0 & 0 & \cdots & I_{w} & 0 \\ 0 & 0 & \cdots & 0 & I_{w - r} \\ S & 0 & \cdots & 0 & 0 \end{pmatrix} \begin{matrix} \\ \\ \leftarrow m\hbox{-th row} \\ \\ \\ \\ \end{matrix}$

$S = \begin{pmatrix} 0 & I_{r} \\ I_{w - r} & 0 \end{pmatrix} A$

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

Period reaches the theoretical upper limit 2nw − 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−1RT, T invertible. The tempering is defined in the case of Mersenne Twister as

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.

The coefficients for MT19937 are: