Web hosting reseller - 3.6 ANSWERSTOEXERCISES 561 36. Let b and k
3.6 ANSWERSTOEXERCISES 561 36. Let b and k be arbitrary but fixed integers greater than 1. Let Y, = LbU,]. An arbitrary infinite subsequence (&) = (Ysn)R determined by algorithms S and R (as in the proof of Theorem M) corresponds in a straightforward but notationally hopeless manner to algorithms S and R that inspect Xt, Xt+l, . . . , Xt+, and/or select Xt, X t+1, . . . , Xt+mln(k–l,s) of (Xn) if and only if S and R inspect and/or select Y,, where us = (0.X,X,+.1 . . . X,+t,)z. Algorithms S and R determine an infinite l-distributed subsequence of (Xn) and in fact (as in exercise 32) this subsequence is co-distributed so it is (k, 1)-distributed. Hence we find that &(Z, = u) and Pr(2, = a) differ from l/b by less than 1/2k. [The result of this exercise is true if R6 is replaced consistently by R4 or R5 ; but it is false if Rl is used, since X(-) might be identically zero.] 2 37. For 7~ 2 2 replace U,2 by ~(U,Z + &), where 6, = 0 or 1 according as the set {Ucn–lj~+l,. , Un~~l} contains an even or odd number of elements less than 4. [Advances in Math. 14 (1974), 333-334.1 39. See Acta Arithmetica 21 (1972), 45-50. The best possible value of c is unknown. 40. If every one-digit change to a random table yields a random table, all tables are random (or none are). If we don t allow degrees of randomness, the answer must therefore be, Not always. SECTION 3.6 l.RANDI STJ 9F Store exit location. STA 8F Store value of Ic. LDA XFtAND rA+-X. MUL 7F rAX + ax. INCX 1009 rX + (ax + c) mod m. JOV *+I Ensure that overflow is off. SLAX 5 rA t (ax + c) mod m. STA XRAND Store X. MUL 8F rA + [kX/mJ. INCA 1 Add 1, so that 1 5 Y 5 Ic. 9H JMP + Return. XFUND CON 1 Value of X; X0 = 1. 8H CON 0 Temp storage of k. 7H CON 3141592621 The multiplier a. 1 2. Putting a random number generator into a program makes the results essentially unpredictable to the programmer. If the behavior of the machine on each problem were known in advance, few programs would ever be written. As Turing has said, the actions of a computer quite often do surprise its programmer, especially when a program is being debugged. So the world had better watch out. 7. In fact, you only need the a-bit values [Xn/216j mod 4; see D. E. Knuth, De- ciphering a linear congruential encryption, to appear. See also J. Reeds, Cryptologia 1 (1977), 20-26, 3 (1979), 83-95, for solutions to related problems.