next up previous

4 N-tuple Generation With LCGs     continued...

The cases looked at so far are for moduli chosen to be small enough that we can plot the full-period results and still see a pattern with space between points. In practice, it would be foolish to use a generator with such a short period. If we look at an LCG with much longer period, one that we might use in a practical application, we still see the lattice-like full-period behavior. Figure 6f shows the full-period 2-D result for , where we ``zoom in'' on only the portion of the unit square in the (0,0.0005) X (0,0.0005) corner, or 1/4,000,000 of the total area. Although the row spacing for this generator is obviously not optimal, this particular one is popular for its universal portability and its satisfactory performance in many applications.

We have shown only examples in which c = 0. Using a nonzero value for c when m is prime has the effect of shifting the entire lattice structure to a new location, so that it appears offset from that of the c = 0 case. The orientation and spacing of the lattice remain the same, except that one lattice point appears absent --- this reflects the fact that when m is prime and c=0, some nonzero value of X will succeed itself in the recursion formula of the generator. (Actually, there is a ``hole'' in the c=0 lattice as well, but it lies on one of the axes, and so doesn't disrupt the apparent regularity.) When m is a power of two and c is nonzero, recall that the period of the generator is four times the period of the c=0 case. Here again the resulting lattice appears to be aligned the same as the c=0 lattice, with the c = 0 lattice offset from a subset of the lattice. A further complication arises in the case where m is a power of two and mod 8: here a nonzero value for c will produce different offsets for each of the two distinct lattice structures, relative to the c = 0 case. The fact that the case is slightly more complicated than the c = 0 case should not obscure the basic theme of this section: that the quality of an LGC used in generating n-tuples is a function of the multiplier, a.

The remarks given here with respect to 2-D behavior of LCGs apply as well to higher dimensions. For example, in three dimensions, the coordinate triples formed as above will lie in distinct planes. For ease of illustration, we have considered only 2-D examples and only in a qualitative sense. The lattice spacing in any number of dimensions can be treated quantitatively using methods detailed in Knuth, Vol. 2. The interested reader is encouraged to pursue the topic further in this source. Remember that the effects described here are full-period properties of LCGs. If only a tiny fraction of the period is used, the most desirable way to use any pseudo-random generator, then these effects may not be noticed. If a user suspects that the lattice structure of n-tuple generation is affecting the outcome of a Monte Carlo simulation, then the best policy is to try another generator of different type and compare the results.

(See exercise 8.)