Web hosting billing - 3.1 INTRODUCTION 7 h) Assume that 10 horses
3.1 INTRODUCTION 7 h) Assume that 10 horses are entered in a race and that you know nothing whatever about their qualifications. Assign to these horses the digits 0 to 9, in arbitrary fashion, and after the race use the winner s digit. 2. [M%!?] In a random sequence of a million decimal digits, what is the probability that there are exactly 100,000 of each possible digit? 3. [IO] What number follows 1010101010 in the middle-square method? 4. [IO] Why can t the value of X be zero when step Kll of Algorithm K is performed? What would be wrong with the algorithm if X could be zero? 5. [15] Explain why, in any case, Algorithm K should not be expected to provide infinitely many random numbers, in the sense that (even if the coincidence given in Table 1 had not occurred) one knows in advance that any sequence generated by Algorithm K will eventually be periodic. b 6. [MZJ] Suppose that we want to generate a sequence of integers X0, Xi, Xz, . . . , in the range 0 < X, < m. Let f(z) b e any function such that 0 2 z < m implies 0 5 f(x) < m. Consider a sequence formed by the rule Xn+l = f(Xn). (Examples are the middle-square method and Algorithm K.) a) Show that the sequence is ultimately periodic, in the sense that there exist numbers X and p for which the values X0, Xi, , X,, . . . , Xp+x-i are distinct, but X %+x = X, when n 2 CL. Find the maximum and minimum possible values of p and X. b) (R. W. Floyd.) Show that there exists an n > 0 such that X, = Xzn; and the smallest such value of 72 lies in the range p < n 5 p + X. Furthermore the value of X, is unique in the sense that if X, = X2, and X, = Xzr, then X, = X,. c) Use the idea of part (b) to design an algorithm that calculates p and X for any given function f and any given X0, using only O(k + X) steps and only a bounded number of memory locations. b 7. [MZ] (R. P. Brent, 1977.) Let e(n) be the least power of 2 that is less than or equal to n; thus, for example, e(15) = 8 and .!(e(n)) = e(n). a) Show that, in terms of the notation in exercise 6, there exists an n > 0 such that X, = Xe(n)-i. Find a formula that expresses the least such 72 in terms of p and x. b) Apply this result to design an algorithm that can be used in conjunction with any random number generator of the type X=+1 = f(Xn), to prevent it from cycling indefinitely. Your algorithm should calculate the period length X, and it should use only a small amount of memory space-you must not simply store all of the computed sequence values! 8. [.28] Make a complete examination of the middle-square method in the case of two- digit decimal numbers. (a) We might start the process out with any of the 100 possible values 00, 01, . . . , 99. How many of these values lead ultimately to the repeating cycle 00, 00, . 1 [Example: Starting with 43, we obtain the sequence 43, 84, 05, 02, 00, 00, 00, . . . .] (b) How many possible final cycles are there? How long is the longest cycle? (c) What starting value or values will give the largest number of distinct elements before the sequence repeats? 9. [M14] Prove that the middle-square method using 2n-digit numbers to the base b has the following disadvantage: If the sequence includes any number whose most significant n digits are zero, the succeeding numbers will get smaller and smaller until zero occurs repeatedly.