TT800 and Mersenne Twister

Mersenne Twister (MT) is a relatively new RNG which is claimed to have an astronomically long period of $2^{19937}-1$ and other strong theoretical support by its authors Matsumoto and Nishimura in [15]. TT800, an RNG announced earlier by the same authors, is a small cousin of MT with a shorter period of $2^{800}$.

Both MT and TT800 are variants of generalized FSRs (see Section 3.3) based on the following linear recurrence

$$x_n = x_{n-(N-M)} \oplus (x^U_{n-N} \vert x^L_{n-N+1}) A$$

$x_i$ is a $w$-bit word for all $i$. $\oplus$ is bitwise XOR operation. $x^U_{n-N}$ means the upper $(w-R)$ bits of $x_{n-N}$ and $x^L_{n-N+1}$ means the lower $R$ bits of $x_{n-N+1}$. $\vert$ is the concatenation operation. $A$ is a $w$-by-$w$ bit array in the following form:

$$\left( \begin{array}{cc} 0 & I_{w-1} \\ a_{w-1} & a \\ \end{array}\right)$$

where $I_{w-1}$ is the $(w-1)$-by-$(w-1)$ identity matrix and $a = (a_{w-2}, a_{w-3}, \ldots, a_0)$. $a_{w-1}$ and $a$ together are denoted by $\alpha$. To summarize, this kind of generator is parameterized by $N,M,R,w,$ and $\alpha$. The parameters for MT are $N=624, M=397, R=31, w=32,$ and $\alpha =$ 9908B0DF in hexadecimal. The parameters for TT800 are $N=32, M=25, R=0,w=32,$ and $\alpha =$ 8EBFD028 in hexadecimal.

MT actually operates on 19937-bit words, and when it is implemented on 32-bit hardware, it requires a work area of 624 32-bit integers to store the whole word. Every time a random variate is requested, a consecutive 32-bit portion is extracted sequentially from the 19937-bit word and undergoes three XOR operations before output. The algorithm will generate another 19937-bit word when all of its 32-bit portions have been requested. Initial seed of MT is a 19937-bit word, which can be given by the first 624 outputs of ordinary 32-bit integer LCGs.

Most congruential-based generators uses prime numbers as the modulus to achieve long periods. The authors of MT chose a special class of primes called Mersenne prime, which is of form $2^n-1$ and $n=19937$ in MT's case , to create an RNG that can produce a theoretically 623-distributed sequence (see Section 2.1). Longer periods are possible by using larger Mersenne primes.