The Mersenne Twister is a twisted generalized feedback shift register generator. The algorithm is as follows: * Set some arbitrary initial values \(x_1, x_2, · · · , x_r\), each consisting of w bits. * Letting
where \(\mathbf I_{w−1}\) is the \((w-1)\times(w-1)\) identity matrix and each of the \(a_i, i = 1\ to\ w\) take a value of either 0 or 1 (i.e. they can be represented as bits).
Define
where \(\mathcal X_{i}^{(w:(l+1))} | \mathcal X_{i+1}^{(l:1)}\) indicates the concatenation of the most significant (upper) \(w − l\) bits of \(\mathcal X_i\) and the least significant (lower) \(\mathcal l\) bits of \(\mathcal X_{i+1}\).
Perform the following operations sequentially:
where \(t_1, t_2, t_3\) and \(t_4\) are integers and \(m_1\) and \(m_2\) are bit-masks and >>t and <<t represent a t bit shift right and left respectively, is bit-wise exclusively or (xor) operation and AND is a bit-wise and operation.
The \(u_{i+r} : i = 1, 2,…\) then form a pseudo-random sequence, with \(u_i \in (0, 1)\), for all i. This implementation of the Mersenne Twister uses the following values for the algorithmic constants:
where the notation \(0 \times DD \dotsc`\) indicates the bit pattern of the integer whose hexadecimal representation is \(DD \dotsc\).
This algorithm has a period length of approximately \(2^{19,937} − 1\) and has been shown to be uniformly distributed in 623 dimensions. [MT]