Computer generated "Random Numbers" are used in many applications. Indeed, there is a whole set of numerical "Monte Carlo" techniques based on them. This page describes how (most) random number generators work and most importantly it lets you design and test your own random number generator. To do so just click on the applet nearby.
Most random number generators generate a sequence of integers by the following recurrence:
x _{0} = given, x _{n+1} = P _{1} x _{n} + P _{2 } (mod N) n = 0,1,2,... (*)
The notation mod N means that the expression on the right of the equation is divided by N, and then replaced with the remainder.
To understand the mechanics consider the following simple Example. (Choose Example on the applet to study this example further.)
x _{0} =79, N = 100, P _{1} = 263, and P _{2} = 71
Thenx _{1} = 79*263 + 71 (mod 100) = 20848 (mod 100) = 48,
x _{1} = 48*263 + 71 (mod 100) = 12695 (mod 100) = 95,
x _{1} = 95*263 + 71 (mod 100) = 25056 (mod 100) = 56,
x _{1} = 56*263 + 71 (mod 100) = 14799 (mod 100) = 99,
Subsequent numbers are: 8, 75, 96, 68, 36, 39, 28, 35, 76, 59, 88, 15, 16, 79, 48. The sequence then repeats . (This indicates a weakness of our example generator: If the random numbers are between 0 and 99 then one would like every number between 0 and 99 to be a possible member of the sequence.
The parameters P _{1}, P _{2}, and N determine the characteristics of the random number generator, and the choice of x _{0} (the seed ) determines the particular sequence of random numbers that is generated. If the generator is run with the same values of the parameters, and the same seed, it will generate a sequence that's identical to the previous one. In that sense the numbers generated certainly are not random. They are therefore sometimes referred to as pseudo random numbers.
Of course one may want random numbers not as integers in a given range, but for example as uniformly distributed real numbers in a certain interval, or perhaps as real numbers of (almost) arbitrary size, but clustered around the origin. Distributions of that sort can be obtained by suitably transforming the original random numbers. For example, to transform a sequence defined as above into an evenly distributed set of real numbers in the interval from 0 to 1 simply divide each of the original numbers by N. In the remainder of this page, though, we just consider the sequence defined by (*) itself.
That's a good question! Several answers are possible, for example:
The second figure nearby shows a distribution of 1,000 points obtained with a widely used and well tested and analyzed random number generator using
P _{1} = 16807, P _{2} = 0, and N= 2 ^{31} -1 = 2147483647.
This generator is described in the reference by Park and Miller given below.
One reason for the seemingly peculiar choice of N is that
that particular number is the largest integer than can be
represented on a Unix machine or in Java.
To illustrate the abilities of this applet consider the following Figure which shows three sequences of 100,000 points each, using the same generator, for k=1 (red), k2 (green), and k=3 (blue). Reassuringly, no systematic patterns are readily apparent.
Clicking on the box at the beginning of this page will cause a control window to pop up that looks much as illustrated in the image nearby. A drawing window that will contain the plots also appears.
There are mostly text input windows and buttons marked ">", "<<" etc.. To change an entry of a text window highlight the text and write a new number. You can also change parts of the number. It is important to terminate every change by pressing the Return or Enter key. The green buttons increment or decrement the text windows they surround. "< " and ">" decrement or increment by 1, the other buttons by larger amounts, e.g., by going to the closest prime number or the closest power of 2. Points of the form
Following is a description of some less obvious features:
You can download the Java Binary and use it standalone (e.g., by typing java Random on your Unix system). You'll need three class files that you can obtain by clicking on the links below. They point to binary files and the pages will look strange in your browser, but you should be able to download them nonetheless. Let me know if you have any trouble.
A standard paper is S.K. Park and K.W. Miller, " Random Number Generators: Good Ones Are Hard To Find", Communications of the ACM, October 1988, pp. 1192-1201.
A recent article on random number generators is by Pei-Chi Wu: Multiplicative, Congruential Random-Number Generators with Multiplier +/-2 ^{k1} +/-2 ^{k2} and Modulus 2 ^{ p} -1, ACM Transactions on Mathematical Software, June 1997, v. 23, No. 2, pp. 255-265.
The Grogono generator is described in P. Grogono, Programming in Pascal, 2nd Ed., Addison-Wesley, 1984, pp. 135-137.
I gratefully acknowledge a very helpful discussion I had with Nelson Beebe.
[15-Aug-2011]