Freelance web design - 110 RANDOM NUMBERS 3.3.4 in this case is
110 RANDOM NUMBERS 3.3.4 in this case is extremely small in spite of the fact that there are parallelogram- shaped regions of area x l/fi containing no points (U,, Un+l). The fact that discrepancy can change so drastically when the points are rotated warns us that the serial test may not be as meaningful a measure of randomness as the rotation-invariant spectral test. G. Historical remarks. In 1959, while deriving upper bounds for the error in the evaluation of t-dimensional integrals by the Monte Carlo method, N. M. Korobov devised a way to rate the multiplier of a linear congruential sequence. His formula (which is rather complicated) is related to the spectral test since it is strongly influenced by small solutions to (15); but it is not quite the same. Korobov s test has been the subject of an extensive literature, surveyed by Kuipers and Niederreiter in Uniform Distribution of Sequences (New York: Wiley, 1974), 52.5. The spectral test was originally formulated by R. R. Coveyou and R. D. MacPherson [JACM 14 (196i ), lOO-1191, who introduced it in an interesting indirect way. Instead of working with the grid structure of successive points, they considered random number generators as sources of t-dimensional waves. The numbers ~xY +. . . + X; such that 21 + . . . + at- zt E 0 (modulo m) in their original treatment were the wave frequencies, or points in the spectrum defined by the random number generator, with low-frequency waves being the most damaging to randomness; hence the name spectral test. Coveyou and MacPherson introduced a procedure analogous to Algorithm S for performing their test, based on the principle of Lemma A. However, the original procedure (which used matrices UUT and VVT instead of U and V) dealt with extremely large numbers; the idea of working directly with U and V was independently suggested by F. Janssens and by U. Dieter. Several other authors pointed out that the spectral test could be understood in far more concrete terms; by introducing the study of the grid and lattice struc- tures corresponding to linear congruential sequences, the fundamental limitations on randomness became graphically clear. See G. Marsaglia, Proc. Nat. Acad. Sci. 61 (1968), 25-28; W. W. Wood, J. Chem. Phys. 48 (1968), 427; R. R. Coveyou, Studies in Applied Math. 3 (1969), 70-112; W. A. Beyer, R. B. Roof, and D. Williamson, Math. Comp. 25 (1971), 345-360; G. Marsaglia and W. A. Beyer, Applications of Number Theory to Numerical Analysis, ed. by S. K. Zaremba (New York: Academic Press, 1972), 249-285, 361-370. Harald Niederreiter s papers concerning the use of exponential sums to study the distribution of linear congruential sequences have appeared in Math. Comp. 26 (1972), 793-795; 28 (1974), 1117-1132; 30 (1976), 571-597; Advances in Math. 26 (1977), 99-181 [this is the most important paper of the series]; and Bull. Amer. Math. Sot. 84 (1978), 273-274: 957-1041 [this one summarizes the others and contains an extensive bibliography]. EXERCISES 1. [M10] To what does the spectral test reduce in one dimension? (In other words,