Interactive Educational Modules in
Scientific Computing

Linear Congruential Generators

This module illustrates the serial correlation that results from a poor choice of parameters in a linear congruential random number generator. A linear congruential generator computes a sequence of numbers using the recursive formula xk = (a xk−1 + b)   (mod M), where a, b, M, and the seed x0 = s are nonnegative integer parameters that define a specific linear congruential generator. The sequence of integers xk produced by such a generator can be converted to a sequence of floating point numbers  fk in the interval [0, 1) by taking  fk = xkM. This module plots consecutive pairs of these floating point numbers, i.e., (f1, f2), (f3, f4),… as points in the unit square.

The user either types in the desired parameters a, b, M, and s or clicks one of the example buttons to choose a set of parameters. The parameter M is limited (usually to 46340) to allow all computations to be performed with integer operations, and if the user types in a value for M exceeding that limit, it may be rounded it down to the limit. Other parameters, if they exceed M, are reduced modulo M. When the parameters have been chosen, the user clicks to plot the next 1, 10, or 100 pairs as points in the unit square. The user may plot about 6000 points on the graph before it must be cleared. Clicking Reset or choosing a different set of parameters clears the graph and resets the generator to begin again from the seed value.

Trying a few different parameter combinations with this module should make it clear that a good linear congruential generator requires a very careful choice of parameters. For many choices of parameters, such as those given in Example 1, the sequence of numbers produced by a linear congruential generator has high serial correlation, and the unit square is not sampled well by the plotted pairs of points. The parameters from Example 2 are significantly better, but even for those parameters some serial correlation is visually evident when 3000 points have been plotted.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 13.3.1, Exercise 13.1 on page 517, and Computer Problem 13.2 on page 518.

Developers: Evan VanderZee and Michael Heath