24 RANDOM (Anonymous web server) NUMBERS 3.2.1.3 in this case, so
24 RANDOM NUMBERS 3.2.1.3 in this case, so the differences between consecutively generated numbers change in a simple way from one value of n to the next. The point (X,,X,+i,X,+z) always lies on one of the four planes x-2y+z=d+m, x-2y+z=d-m, x-2y+z=d, x-2y+z=d-2m, in three-dimensional space, where d = cb mod m. If the potency is 3, the sequence begins to look somewhat more random, but there is a high degree of dependency between X,, Xn+i, and Xn+s; tests show that sequences with potency 3 are still not sufficiently good. Reasonable results have been reported when the potency is 4 or more, but these have been disputed by other people. A potency of at least 5 would seem to be required for sufficiently random values. Suppose, for example, that m = 235 and a = 2k + 1. Then b = 2k, so we find that when Ic 2 18, the value b2 = 22k is a multiple of m: the potency is 2. If Ic = 17,16,. . . , 12, the potency is 3, and a potency of 4 is achieved for Ic = 11, 10,9. The only acceptable multipliers, from the standpoint of potency, therefore have Ic 5 8. This means a 5 257, and we shall see later that small multipliers are also to be avoided. We have now eliminated all multipliers of the form 2k + 1 when m = 235. When m is equal to w f 1, where w is the word size, m is generally not divisible by high powers of primes, and a high potency is impossible (see exercise 6). So in this case, the maximum-period method should not be used; the pure-multiplication method with c = 0 should be applied instead. It must be emphasized that high potency is necessary but not sufficient for randomness; we use the concept of potency only to reject impotent generators, not to accept the potent ones. Linear congruential sequences should pass the spectral test discussed in Section 3.3.4 before they are considered to be accept- ably random. EXERCISES 1. [MO] Show that, no matter what the byte size B of MIX happens to be, the code (3) yields a random number generator of maximum period. 2. [IO] What is the potency of the generator represented by the MIX code (3)? 3. [II] When m = 235, what is the potency of the linear congruential sequence with a = 3141592621? What is the potency if the multiplier is a = 223 + 214 + 22 + l? 4. [15] Show that if m = 2e 2 8, maximum potency is achieved when a mod 8 = 5. 5. [M20] Given that m = pt . . . pf and a = 1 + kpp . . , pp, where a satisfies the conditions of Theorem 3.2.1.2A and k is relatively prime to m, show that the potency is max(Tel/fil,. . . , retlftl). b 6. [20] Which of the values of m = w f 1 in Table 3.2.1.1-1 can be used in a linear congruential sequence of maximum period whose potency is 4 or more? (Use the result of exercise 5.)