526 ANSWERS TO EXERCISES 3.2.2 (b) The underlined (Web design tools)
526 ANSWERS TO EXERCISES 3.2.2 (b) The underlined numbers are V[j] after step B2. 0utput:initial 236570053…46(30…47)… V[O]: 0 000000544…1111…11… V[l]: 3 36~111111…0004…00… V[2]: 2 177733331…6222…72… V[3]: 5 555002222…3355…33… x: 4 761032547…3254…32… In this case the output is considerably better than the input; it enters a repeating cycle of length 40 after 46 steps: 236570 05314 72632 40110 37564 76025 12541 73625 03746 (30175 24061 52317 46203 74531 60425 16753 02647). The cycle can be found easily by applying the method of exercise 3.1-7 to the above array until a column is repeated. 4. The low-order byte of many random sequences (e.g., linear congruential sequences with m = word size) is much less random than the high-order byte. See Section 3.2.1.1. 5. The randomizing effect would be quite minimized, because V[j] would always contain a number in a certain range, essentially j/k 5 V[j]/m < (j + 1)/k. However, some similar approaches could be used: we could take Y, = XnPl, or we could choose j from X, by extracting some digits from about the middle instead of at the extreme left. None of these suggestions would produce a lengthening of the period analogous to the behavior of Algorithm B. 6. For example, if X,/m < $, then X,+1 = 2X,. 7. [W. Mantel, Nieuw Arehief voor Wiskunde (2) 1 (1897), 172-184.1 00.. .Ol 00.. .Ol 00.. .lO The subsequence of 00.. .lO X values: becomes: 10.. .oo 10.. .oo 00.. .oo CONTENTS (A) CONTENTS (A) 8. We may assume that Xs = 0 and m = p , as in the proof of Theorem 3.2.1.2A. First suppose that the sequence has period length pe; it follows that the period of the sequence mod pf has length p f, for 1 < f 5 e, otherwise some residues mod pf would never occur. Clearly, c is not a multiple of p, for otherwise each X, would be a multiple of p. If p 5 3, it is easy to establish the necessity of conditions (iii) and (iv) by trial and error, so we may assume that p 2 5. If d $ 0 (modulo p) then dz2 + aa: + c = d(z + a,) + cl (modulo p ) for some integers al and cl and for all integers x; this quadratic takes the same value at the points x and --z -2~1, so it cannot assume all values modulo pe. Hence d G 0 (modulo p); and if a $ 1, we would have dx2 $ ax + c E x (modulo p) for some z, contradicting the fact that the sequence mod p has period length p. To show the sufficiency of the conditions, we may assume by Theorem 3.2.1.2A and consideration of some trivial cases that m = pe where e > 2. If p = 2, we have Xntp = X, +pc (modulo p2), by trial; and if p = 3, we have either Xn+r G X, fpc (modulo p ), for all n, or Xn+r = X, -pc (modulo p ), for all n. For p 2 5, we can prove that Xn+r = X, + pc (modulo p ): Let d = pr, a = 1 f ps. Then if