Mersenne twister

TLDR

The Mersenne Twister is a new variant of TGFSR generators designed to achieve a Mersenne‑prime period. The paper proposes the Mersenne Twister algorithm to generate uniform pseudorandom numbers. The algorithm uses a high‑degree characteristic polynomial with many terms, includes a primitivity‑checking routine of O(p²) complexity, and is implemented in portable C. The Mersenne Twister achieves a period of 2^19937−1, 623‑dimensional equidistribution to 32‑bit accuracy, passes stringent statistical tests such as Diehard, runs at speeds comparable to modern generators, and benefits from efficient polynomial‑based algorithms.

Abstract

A new algorithm called Mersenne Twister (MT) is proposed for generating uniform pseudorandom numbers. For a particular choice of parameters, the algorithm provides a super astronomical period of 2 19937 −1 and 623-dimensional equidistribution up to 32-bit accuracy, while using a working area of only 624 words. This is a new variant of the previously proposed generators, TGFSR, modified so as to admit a Mersenne-prime period. The characteristic polynomial has many terms. The distribution up to v bits accuracy for 1 ≤ v ≤ 32 is also shown to be good. An algorithm is also given that checks the primitivity of the characteristic polynomial of MT with computational complexity O(p 2 ) where p is the degree of the polynomial. We implemented this generator in portable C-code. It passed several stringent statistical tests, including diehard. Its speed is comparable to other modern generators. Its merits are due to the efficient algorithms that are unique to polynomial calculations over the two-element field.