26 RANDOM NUMBERS 3.2.2 An interesting quadratic method (Web design)
26 RANDOM NUMBERS 3.2.2 An interesting quadratic method has been proposed by R. R. Coveyou when m is a power of two; let X0 mod 4 = 2, X,+1 = X,(X, + 1) mod 2e, n 2 0. (4) This sequence can be computed with about the same efficiency as (l), without any worries of overflow. It has an interesting connection with von Neumann s original middle-square method: If we let Y, be Z X,, so that Y, is a double-precision number obtained by placing e zeros to the right of the binary representation of -L then Y,+l consists of precisely the middle 2e digits of Yg + 2eY,! In other words, Coveyou s method is almost identical to a somewhat degenerate double- precision middle-square method, yet it is guaranteed to have a long period; further evidence of its randomness is proved in exercise 3.3.4-25. Other generalizations of Eq. (1) also suggest themselves; for example, we might try to extend the period length of the sequence. The period of a linear congruential sequence is extremely long; when m is approximately the word size of the computer, we usually get periods on the order of 10 or more, so that typical calculations will use only a very small portion of the sequence. On the other hand, when we discuss the idea of accuracy in Section 3.3.4 we will see that the period length influences the degree of randomness achievable in a sequence. Therefore it is occasionally desirable to seek a longer period, and several methods are available for this purpose. One technique is to make X,+i depend on both X, and Xn-1, instead of just on X,; then the period length can be as high as m2, since the sequence will not begin to repeat until we have wn+x 7-&+x+1) = (-%I, x7x+1>. The simplest sequence in which X,+i depends on more than one of the preceding values is the Fibonacci sequence, X n+~ = (& + G-1) mod m. (5) This generator was considered in the early 1950s and it usually gives a period length greater than m; but tests have shown that the numbers produced by the Fibonacci recurrence (5) are definitely not satisfactorily random, and so at the present time the main interest in (5) as a source of random numbers is that it makes a nice bad example. We may also consider generators of the form X n+~ = (-G + L–k) mod m, (6) when k is a comparatively large value. These were introduced by Green, Smith, and Klem [JACK 6 (1959), 527-5371, who reported that, when Ic 5 15, the sequence fails to pass the gap test described in Section 3.3.2, although when k = 16 the test was satisfactory. A much better type of additive generator was devised in 1958 by G. J. Mitchell and D. P. Moore [unpublished], who suggested the somewhat unusual sequence defined by -G = (K-24 + X-55) mod m, n > 55,