Section 3:
Random numbers and random number
generators.
What is a Random Number?
Numbers that are ``chosen at random'' .
Applications:
Random number generation:
Brief History:The history of generating random numbers is interesting. At first, people who needed random numbers in their scientific work would draw balls out of a ``wellstirred urn'' or would roll dice or deal out cards. A table of over 40,000 random digits, ``taken at random from census reports,'' was published in 1927 by L. H. C. Tippett. Since then, a number of devices have been built to generate random numbers mechanically; the first such machine was used in 1939 by M. G. Kendall and B. BabingtonSmith to produce a table of 100,000 random digits, and in 1955 the RAND Corporation published a widely used table of a million random digits obtained with the help of another special device. A famous randomnumber machine called ERNIE has been used to pick the winning numbers in the British Premium Bonds lottery.
Shortly after computers were introduced, people began to search for efficient ways to obtain random numbers within computer programs. A table can be used, but this method is of limited utility because of the memory space and input time requirement, because the table may be too short, and because it is a bit of nuisance to prepare and maintain the table. Machines such as ERNIE might be attached to the computer, but this would be unsatisfactory since it would be impractical to reproduce calculations exactly a second time when checking out a program; and such machines have tended to suffer from malfunctions that are difficult to detect.
The inadequacy of these methods led to an interest in the production of random numbers using the arithmetic operations of a computer. John von Neumann first suggested this approach in about 1946, using the ``middlesquare'' method. His idea was to take the square of the previous random number and to extract the middle digits; for example, if we are generating 10digit numbers and the previous value as 5772156649, we square it to get
33317792380594909201, and the next number is therefore 7923805949.
There is a fairly obvious objection to this technique: how can a sequence generated in such a way be random, since each number is completely determined by its predecessor? The answer is that this sequence isn't random, but it appears to be. In typical applications the actual relationship between one number and its successor has no physical significance; hence the nonrandom character is not really undesirable. Intuitively, the middle square seems to be fairly good scrambling of the previous number.
Sequences generated in a deterministic way such as this are usually called pseudorandom or quasirandom sequences in the highbrow technical literature, but here we shall simply call them random sequences, with the understanding that they only appear to be random. Being ``apparently random'' is perhaps all that can be said about any random sequence anyway. Random numbers generated deterministically on computers have worked quite well in nearly every application, provided that a suitable method has been carefully selected. Of course, deterministic sequences aren't always the answer; they certainly shouldn't replace ERNIE for the lotteries.
Von Neumann's original ``middlesquare method'' has actually proved to be a comparatively poor source of random numbers. The danger is that the sequence tends to get into a rut, a short cycle of repeating elements. For example, if zero ever appears as a number of the sequence, it will continually perpetuate itself.
Many random number generators in use today are not very good. There is a tendency for people to avoid learning anything about such subroutines; quite often we find that some old method that is comparatively unsatisfactory has blindly been passed down from one programmer to another, and today's users have no understanding of its limitations. We shall see that it is not difficult to learn the most important facts about random number generators and their proper use.
Linear congruential method
By far the most popular random number generators in use today are special cases of the following scheme.
We choose four ``magic numbers'':For example, the sequence obtained when m = 10 and X_{0} = a = c = 7 ism, the modulus; m > 0The desired sequence of random numbers X_{n} is then obtained by setting
a, the multiplier; 0 < a < m
c, the increment; 0 < c < m
X_{0}, the starting value; 0 < X_{0} < mX_{n+1} = (a X_{n} + c) mod m, n > 0, (1)where a, c, and m are properly chosen integer constants. This is called a linear congruential sequence. Taking the remainder mod m is somewhat like determining where a ball will land in a spinning roulette wheel.7, 6, 9, 0, 7, 6, 9, 0, ...As this example shows, the sequence is not always ``random'' for all choices of m, a, c, and X_{0}; the principles of choosing the magic numbers appropriately will be outlined.The above example illustrates the fact that the congruential sequences always ``get into a loop''; i.e., there is ultimately a cycle of numbers that is repeated endlessly. This property is common to all sequences having the general form X_{n+1} = f(X_{n}). The repeating cycle is called the period.
Choice of modulus.
The value of m need to be rather large, since the period cannot have more than m elements.
Choice of multiplier.m can be conveniently chosen as the word size of our computer:Let w be the computer's word size, namely, 2^{e} on an ebit binary computer (e=16 on Intel 8086 processor, e=32 on Silicon Graphics and 64 on Cray). The result of an addition operation is usually given modulo m; and multiplication mod w is also quite simple, since the desired result is the lower half of the product. Hence the C statement
x = a * x + c;
is the same as a x+ c modulo 2^{e}, assuming that a, x, and c are declared as unsigned int. Quick tricks for modulo w + 1 also exist if one writes in assembly languages.
The multiplier should give the period of maximum length. A long period is essential for any sequence that is to be used as a source of random numbers.
With only m different values are possible, the period
surely cannot be longer than m. Can we achieve the maximum length, m?



period

7^{5}

2^{31}1

0

2^{31}2

1664525

2^{32}

1013904223

2^{32}

69069

2^{32}

0

2^{30}

6364136223846793005

2^{64}

1

2^{64}

For the random number generators with period 2^{30}, it takes only a hour to finish the sequence (the full period) on our workstations.Generating random numbers in C:
Eq.(1) can be efficiently implemented if m=2^{e} on an ebit computer.
In such a case, the modulo operation is really unnecessary (and slow) since it is automatic. In multiplication, if the result is larger than the maximum possible value in a computer, the higher order bits are truncated.
As an example, in C we could write two lines of code
x = 1664525U * x + 1013904223U;each time a random number r in the range (0,1) is needed. The variable x must be unsigned and r could be double or float. It is more efficient to use the uniformly distributed random integer x between 0 and 2^{32}1 directly.
r = x * 2.328306437e10;
C compilers supply a standard random integer function, rand() (header file <stdlib.h>).
Many implementations give only a 16bit random number,
which is not acceptable for Monte Carlo calculation, and should be avoided.
A better choice is the drand48()
which returns a double and
is generated with 48bit integers. The 64bit random number generator above
can be implemented with long long int
type in SGI workstations.