3.2.2 OTHER METHODS 31 1011 0101 1010 0111 (Web hosting bandwidth)
3.2.2 OTHER METHODS 31 1011 0101 1010 0111 1110 1111 1101 1001 0001 0010 0100 1000 Fig. 1. Successive contents of the computer word X in the binary 0011 0110 method, assuming that k = 4 and CONTENTS(A) = (0011)~. 1100 1011 of the form xn = f(-%-1, . . . > X+-k), 0 I xn < m, (11) is easily seen to be mk. M. H. Martin [Bull. Amer. Math. Sot. 40 (1934), 859-8641 was the first person to show that functions achieving this maximum period are possible for all m and k; his method is easy to state, but it is unfortunately not suitable for programming (see exercise 17). From a computational standpoint, the simplest known functions f that yield the maximum period mk appear in exercise 21; the corresponding programs are, in general, not as efficient for random number generation as other methods we have described, but they do give demonstrable randomness when the period as a whole is considered. Another important class of techniques deals with the combination of random number generators, to get more random sequences. There will always be people who feel that the linear congruential methods, additive methods, etc., are all too simple to give sufficiently random sequences; and it may never be possible to prove that their skepticism is unjustified (although we believe it is), so it is pretty useless to argue the point. There are reasonably efficient methods for combining two sequences into a third one that should be haphazard enough to satisfy all but the most hardened skeptic. Suppose we have two sequences X0, X1, . . . and Y,, Y,, . . . of random numbers between 0 and m -1, preferably generated by two unrelated methods. One suggestion has been to add them together, mod m, obtaining the sequence 2, = (X, + Yn) mod m; in this case, the period will be quite long if the period lengths of (-G) and (L) are relatively prime to each other (see exercise 13). Another approach, based on circular shifting and exclusive or-ing , has been suggested by W. J. Westlake, JACM 14 (1967), 337-340. A considerably different method has been suggested by M. D. MacLaren and G. Marsaglia [JACM 12 (1965), 83-89; CACM 11 (1968), 7591, who use one random sequence to permute the elements of another: