Mersenne Twister:
A Study on Random Number Generators

The Mersenne Twister[1] (MT) is a new algorithm for generating pseudo random numbers. It has the following advantages in comparison to the other generators:  

• It has a very large period, 2¹⁹⁹³⁷-1, which is greater than the other generators
• It provides a far higher order of equidistribution (623-dimensions)
• It is very fast; it avoids multiplication and division, benefits from the caches pipelines.
• It is efficient in memory use (only 624 words needed for the working area)

The algorithm itself is an improved variant of Twisted Generalized Feedback Register (TGSFR[2]). The 'twist' is a transformation, which assures equidistribution of the generated numbers in 623 dimensions (linear congruential generators can at best manage reasonable distribution in 5 dimensions).

Here we present a study on Mersenne Twister and it's predecessors Twisted GFSR, GFSR and Tausworthe generators also some popular generators like the Linear Congruential Generators, their theory and background and implementations. The study also focuses on testing, measuring and comparing random number generators and gives an didactic introduction to k-distribution property and spectral test.

The project contains a random number generator library which includes popular instances of above mentioned generators and 3 applications to demonstrate the certain aspects discussed in the study.

There's a paper discussing the theory and a report which gives information about the design and the implementation.

Spectral Test

Following are the 2 dimensional distributivity of some random number generators as plotted by the application. The density of the dots gives a measure of randomness for the numbers generated by these generators.

The left most plot belongs to LCG-276 instance. The pairs of random numbers only appear with certain combinations. As the k-distributivity increases pairs have almost all of the combinations in the given interval. In MT the plotted plots fill in every possible cross section on the graph after a while meaning the generated numbers have equal possibility to appear.

Comparison of Random Number Generators

Following are the comparisons between different RNG instances using the Cesaro's Method for calculating the Pi with 15000 Monte-Carlo experiments. As the randomness of the generated sequences increase the accuracy of the estimation increases. 

Mersenne Twister has the most accurate Pi value, leaving the instance with ANSI-C rand and PLT Scheme's internal generator. It is interesting to see that for this test instance the trivial LCG-277 (cycle length is only 31) scores better than some of the sophisticated generators with longer cycle lengths including IBM's famous RANDU. However this test is quite subjective as certain sequence of numbers may just have good combinations for calculating the Pi (maybe sequence 1,2,3,... gives an accurate estimation as well) . Therefore this test alone is not enough to give a conclusion about the randomness of the  generator.

Files

Mersenne Twister and Random Number Generators Theory and Background

Mersenne Twister and Random Number Generators Design and Implementation

Random Number Generator Library and Demo Applications Sources