Programming Praxis

We have written random number generators in several previous exercises. Today we look at the Mersenne Twister of Makoto Matsumoto and Takuji Nishimura. Here is their description of their algorithm:

We propose a new random number generator Mersenne Twister. An implemented C-code MT19937 has the period 2¹⁹⁹³⁷−1 and 523-dimensional equidistribution property, which seems to be the best among all generators ever implemented. There are two new ideas added to the previous twisted GFSR to attain these records. One is an incomplete array to realize a Mersenne-prime period. The other is a fast algorithm to test the primitivity of the characteristic polynomial of a linear recurrence, named inversive-decimation method. This algorithm does not require even the explicit form of the characteristic polynomial. It needs only (1) the defining recurrence, and (2) some fast algorithm that obtains the present state vector from its 1-bit output stream. The computational complexity of the inversive-decimation method is the order of the algorithm in (2) multiplied by the degree of the characteristic polynomial. To attain higher order equidistribution properties, we used the resolution-wise lattice method, with Lenstra’s algorithm for successive minima.

If that’s not quite clear, their reference implementation is given on the next page. Note that this implementation is the original Mersenne Twister MT19937; there are several variants.

Though George Marsaglia has strongly criticized it as needlessly complex, the Mersenne Twister is quite a popular random number generator. It takes a 32-bit integer other than 0 as a seed, returns a 32-bit integer each time it is called, and has a period of 2¹⁹⁹³⁷−1 ≅ 4·10⁶⁰⁰¹. The Mersenne twister is suitable for simulation but not for cryptography.

Your task is to implement the Mersenne twister in your favorite language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2 3