Mersenne Twister

A Random Number Class, or, a practical use for Mersenne primes at last...

@todo finish off, or move somewhere else...

mt_rand is an easy to use C++ class that encapsulates a Mersenne Twister Random Number generator and a series of useful functions. The Merrsenne Twister algorithm was invented by Makoto Matsumoto and Takuji Nishimura only a few years age, and is certainly the best random number generator around (far better than the std::rand() you may be using now...)

More than 99% of the run time of all of my computers is used to search for ever larger Mersenne Primes (see my primes page), and the question I get asked most is if there is any practical use for these crazily large primes - now there is, and you are looking at it.

Why not just use std::rand()?

Almost all vendors implementations of rand() in the C library (and indeed, most all languages...) use whats known as a linear congruential generator:

Given a non-negative integer, P_n, P_n+1 is equal to (aP_n + c) mod m

(Where the values of a, c, and m are carefully chosen. Press et. al. ('Numerical recipies in C') recomend m=714,025 a=1,366 and c=150,889)

This algorithm is easy to implement, reasonbly fast, and extremely well known - but it has a number of serious limitations that affect some common applications: Where lots of random numbers are needed (simulations, genetic algorithms, simulated annealing), or high quality random numbers are needed (Monte Carlo simulation).

The Random number generated can never be larger than m. This limits us to m possible values. If m is large, ~31 bits or so, this is not a problem, but until fairly recently it was quite common for m to be a 15 bit value, producing only 32,768 different random values! You should check your library.
Given the best possible values for a, c, & m the number produced by the linear congruential generator will start to repeat after m iterations - much less than m if a & c are chosen poorly. The common values of a, c & m given above will start to repeat their output in less than a second on a modern machine, and even a high quality 31 bit value of m will start to repeat in less than a minute during a simulation, or similar application. Continuing the simulation after this time is clearly a waste of time. This was a major problem for me while experimenting with Genetic algorithms.
The two random numbers P_n, and P_n+1 should not be related to each other. That is, if we are generating numbers between 1 and 100, and P_n is 14, then the probability that P_n+1 is also 14 should be 1/100. Also this in not the case with the linear congruential generator - close neighbours in the series exibit serial correlation.

So what's so great about the Mersenne Twister?

What does mt_rand provide?

mt_rand provides an efficient implementation of a 32-bit Mersenne-Twister peusdo-random number generator, as well as a number of utility functions, all wrapped in a modern C++ class.