Skip over navigation

The Lost continent of

You've found a bug on my site!

Technology is a queer thing. It brings you great gifts with one hand, and it stabs you in the back with the other.

C.P. Snow

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, Pn, Pn+1 is equal to (aPn + 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 Pn, and Pn+1 should not be related to each other. That is, if we are generating numbers between 1 and 100, and Pn is 14, then the probability that Pn+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.