5.4.1 Linear Congruential Generators
Today, the most widely used pseudorandom number generators are linear congruential generators (LCGs). Introduced by Lehmer (1951), these are specified with nonnegative integers η, a, and c.13 An integer seed value z[0] is selected, 0 ≤ z[0] < η, and a sequence of integers z[k] is obtained recursively with the formula
[5.10]
The modular notation “mod” indicates that z[k] is the remainder after dividing the quantity a z[k–1] + c by η. A sequence of pseudorandom numbers u[k] is obtained by dividing the z[k] by η:
[5.11]
Consider the simplistic generator
[5.12]
Starting with a seed z[0] = 4, we calculate a sequence of pseudorandom numbers in Exhibit 5.9.
These illustrate three important properties of LCGs:
- They are periodic. Because the integers z[k] are nonnegative and bounded by η, the sequence of pseudorandom number must repeat in a continual loop of period ≤ η.
- Their pseudorandom numbers always fall on a lattice. In our example, the lattice has a spacing between numbers that is a multiple of 1/7. More generally, Marsaglia (1968) demonstrates that n-tuples of consecutive numbers from LCGs always fall on sets of parallel planes in n-dimensional space.
- They may generate 0 as a pseudorandom number. Our definition of pseudorandom numbers requires that the numbers be in the open interval (0,1).
Periodicity is a property of all pseudorandom number generators. It is addressed by using a generator whose period exceeds the number of pseudorandom numbers required for an application. An LCGs period can be as high as η, but many have lower periods. We call a pseudorandom number generator whose period is the maximum possible for its form a full-period generator.
A lattice structure may or may not be a problem, depending upon how closely the planes are spaced and the nature of the intended Monte Carlo application. Exhibit 5.10 illustrates two-dimensional lattice structures for two LCGs. Because they have low periods, neither of these generators would be used in practice, but they illustrate how lattice structures can vary from very good to very bad.
An LCG has a different lattice structure for each dimension. It may have excellent lattice structures in certain dimensions, but poor lattice structures in others. A classic example is the so-called RANDU14 generator:
[5.13]
This was widely adopted during the 1960s because computer implementations of the generator ran quickly. Division by 231 was easy on binary computers just as division by 100 is easy with decimal numbers. A simple trick made it easy to multiply by 65,539. Unfortunately, RANDU was a mistake. We know today that its two-dimensional lattice is good, but not its three-dimensional lattice. All 3-tuples generated by RANDU fall on just 15 parallel planes. This discovery cast doubt on Monte Carlo results obtained during the 1960s and 1970s with this generator.
Another issue with LCGs is the fact that correlations between pseudorandom numbers separated by large lags may be strong.
A number of LCGs have been adopted as default generators in various operating systems and software packages. An example is the LCG
[5.14]
This was first proposed by Lewis, Goodman, and Miller (1969) for the IBM System/360. Based upon its performance on empirical tests as well as its ease of implementation, Park and Miller (1988) proposed it as a minimal standard against which other generators might be compared. This LCG was incorporated into operating systems for personal computers and Macintosh computers, as well as the IMSL subroutine library, MATLAB, and a number of simulation packages. Exhibit 5.11 illustrates a sample of 2-tuples from the generator as well as its two-dimensional lattice structure.
