Producing a number by some algorithm takes away some of the randomness that it should possess.  A truly "random" number or occurrence can be produced only by some physical phenomenon, such as white noise.  For this reason, numbers produced by algorithms are correctly referred to as pseudorandom numbers.  Understanding this, pseudorandom numbers shall from this point be referred to as random numbers.

Properties of Uniformly Distributed Numbers
   A random number generator should have the following properties:

1. †The numbers generated should have as nearly as possible a uniform distribution.
2. The generator should be fast.
3. The generator program should not require large amounts of core.
4. The generator should have a long period (i.e., it should produce a large sequence of numbers before the sequence begins to cycle).
5. The generator should be able to produce a different set of random numbers to reproduce a series of numbers depending on where it starts the sequence.
6. The method should not degenerate to repeatedly produce a constant value.
7. †The generator should not produce a zero.

   Several methods will now be examined that have been developed to generate sequences of pseudorandom numbers.  The first three methods (Midsquare, Midproduct, and Fibonacci) are of historical significance and have detrimental, limiting characteristics.  The last technique is the most popular in use today and is referred to as the congruential methods. (** Some of these methods are shown in this site.)

Midsquare Techique
   We select a four-digit integer seed to initialize the generator.  Our first random number is obtained from the seed in the following manner.  The seed is squared and all digits except the middle four are ignored.  The result is then normalized† to give the first random number; this number is subsequently used as the new seed.  Pseudorandom numbers can be generated in this manner, each time using the previous random number as the new seed.
   The Midsquare technique is never used today.  The method has a tendency to degenerate rapidly.  If the number zero is ever generated, all subsequent numbers generated will also have a zero value unless steps are provided to handle this case.  Furthermore, the method is slow, since many multiplications and divisions are required to access the middle digits in a fixed-word binary computer.

Midproduct Techique
   The method is similar to the Midsquare technique except that a successive number is obtained by multiplying the current number by a constant, K, and taking the middle digits.  The formula is S_n+1 = K.S_n.  The Midproduct technique has the following properties:

1. A longer period than the Midsquare technique.
2. More uniformly distributed than the Midsquare technique.
3. The method tends to degenerate.

Fibonacci Method
   This generator is based on the Fibonacci sequence and is represented by

The method usually produces a period of length greater than M; however, the pseudorandom numbers obtained by using the Fibonacci method fail to pass the tests for randomness.  Consequently the method does not give satisfactory results.

The logic in generating uniform random variates via a congruential method
   Congruential methods of random number generation can be explained in the following manner.  Consider this relation:

   This formula can be expressed in words as follows.  Choose a positive (** integer) number A and a positive number C.  Let r_i be an initial random number chosen ahead of time.  It is called the random number seed.  Multiply r_i by A, add C to this total, and divide the result by M.  Keep the remainder and call this r_i+1.  Repeat the procedure.  If C = 0, then the procedure is called a multiplicative congruential generator.  If C ≠ 0, then this is called a mixed generator.  Surprisingly, mixed generators have not performed well in practice.  Hence, we shall only consider the multiplicative congruential generator.
r_i+1 = (A r_i) Modulo M
   Let us consider a simple example with r₁ = 5, A = 5, and M = 17.  The following sequence of pseudorandom numbers is produced: 5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7, 1, 5, … The sequence begins to repeat after 16 random numbers.  Note that every number between 1 and 16 is in the sequence, but neither zero nor 17 ever appear, since the number zero would repeat forever.  This particular choice of A, r, and X_i yields a period of 16.  The numbers "appear" to occur at random, but they obviously repeat this sequence forever.  The period of a random number generator and the "randomness" are obviously a function of the parameters A, M, and r₁.  A logical choice for M would be the largest number that can exist, since division by that number would always yield a value between zero and one.  For a binary computer, the range of positive integers are 2^B, where B is this number of maximum digits per word.
   For example, for a 32-bit machine the choice for M would be 2³².  Positive integers therefore range from 1 to 2³² − 1.  (** Maybe in the past century.) The parameter A should be selected so that it is at least 5 digits, odd, and relative prime to M.  Furthermore, it should not contain long sequences of zeros or ones.  For a 32-bit machine, a good choice for A is 3¹⁹ (** = 1162261467); and this is also a good choice for r₁.  Following this procedure for a 32-bit machine, numbers between 1 and 2³² − 1 will be produced.  However, note that an anomaly occurs.  Since all numbers are odd and relative prime, even remainders can never occur!  Nevertheless, mathematical tests have accepted this generator as a statistically sound choice —the numbers appear random.  The numbers A = 3¹⁹ and M = 2³¹ − 1 are IBM choice for use on an IBM 360 (** obsolete).  Their choice of a seed is 65539, which produces a period of 2²⁹ (** 500 millions).  The reader is encouraged to explore this logic through direct experimentation on either a mainframe or microcomputer using the appropriate value for B in (** unclear) 2^B − 1.

Created: 12-Oct-2003 — Last update: 15-Oct-2003