Steve Thompson
Originally written: 11 Jun 2003
Last updated: 16 Mar 2005
The random number generators supplied with computer programs have limitations.
A common generator is the “linear congruential
generator” (LCG). It's an efficient way to generate a list of integers
from 0 to m-1. For example,
say m=10; the generator might make the list
4 7 5 1 2 9 0 3 6 8. Each time the
generator is called, next number in the list is outputted. The obvious
problem here is that the list will eventually repeat itself,
therefore losing randomness.
The so-called minimal standard generator has a period of 2^31-1 and is
computed by with the recursion expression: I[j+1] =
16807*I[j] (mod 2,147,483,647). This generator was used in
early versions of MATLAB and is currently used in various
environments. Numerical Recipes has a couple different
implementations of this algorithm.
The first problem with the linear congruential generator is the relatively small period. The second is that the numbers are rigidly confined to planes. Consider rain falling on a 1 meter by 1 meter square on the sidewalk. The rain drops will certainly fall at any and all locations on the square. This is a true random process. However, the points generated on a two dimensional plane using the LCG do not have the freedom to “land” at any location. The points are confined to lines in the square. For a three dimensional space, the points are confined to planes. In general, for an N dimensional space, the points are confined to N-1 dimensional hyperplanes. Using the minimal standard LCG, the number of planes for N=3 is 1600; for N=4, 256; for N=16, 4. This is a problem for Monte Carlo simulations that require the generation of random points in a higher dimensional space -- the points generated with the LCD are hardly random.
Care should be taken when using the supplied
rand() function.
Researchers have developed much better generators over the last several years. See: Paul Bourke's website, Agner Fog's website, George Marsaglia's DIEHARD randomness test (Marsaglia has invented the generator currently used by MATLAB), and Makoto Matsumoto website (inventor of the Mersenne Twister generator used by GNU Octave).
I put some slides together about this topic.