3.2.2 OTHER METHODS 25 7. [A4,20] (Hosting web) When a
3.2.2 OTHER METHODS 25 7. [A4,20] When a satisfies the conditions of Theorem 3.2.1.2A, it is relatively prime to m; hence there is a number a such that aa = 1 (modulo m). Show that a can be expressed simply in terms of b. b 8. [A4261 A random number generator defined by X,+1 = (217 $3)X, mod 235 and X0 = 1 was subjected to the following test: Let, Y, = [1OX,/235]; then Y, should be a random digit between 0 and 9, and the triples (Ysn, Ys~+~, Ysn+2) should take on each of the 1000 possible values from (0, 0, 0) to (9, 9, 9) with equal probability. But with 30000 values of n tested, some triples hardly ever occurred, and others occurred much more often than they should have. Can you account for this failure? 3.2.2. Other Methods Of course, linear congruential sequences are not the only sources of random num- bers that have been proposed for computer use. In this section we shall review the most significant alternatives; some of these methods are quite important, while others are interesting chiefly because they are not as good as a person might expect. One of the common fallacies encountered in connection with random number generation is the idea that we can take a good generator and modify it a little, in order to get an even-more-random sequence. This is often false. For example, we know that X n+l = (ax, + c) mod m (1) leads to reasonably good random numbers; wouldn t the sequence produced by X n+l = ((ax,) mod (m + 1) + c) mod m (2) be even more random? The answer is, the new sequence is probably a great deal less random. For the whole theory breaks down, and in the absence of any theory about the behavior of the sequence (a), we come into the area of generators of the type Xn+l = f(Xn) with the function f chosen at random; exercises 3.1-11 through 3.1-15 show that these sequences probably behave much more poorly than the sequences obtained from the more disciplined function (1). Let us consider another approach, in an attempt to get more random numbers. The linear congruential method can be generalized to, say, a quadratic congruential method: X n+l = (dXt + ax, + c) mod m. (3) Exercise 8 generalizes Theorem 3.2.1.2A to obtain necessary and sufficient con- ditions on a, c, and d such that the sequence defined by (3) has a period of the maximum length m; the restrictions are not much more severe than in the linear method.