MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

4.3.3 ANSWERS TO EXERCISES 587 12. Obvious from (ll), if we replace m3 by m. [Another way to test for overflow, if m is odd, is to maintain extra bits 2~0 = u mod 2 and vo = v mod 2. Then overflow has occurred iff UO+VO $ wi +. . .+w, (modulo 2), where (~1, . , wr) are the mixed-radix digits corresponding to u + v.] 13. (a) x2 -x = (x -1)x = 0 (modulo 10n) is equivalent to (x -1)x = 0 (modulo p ) for p = 2 and 5. Either x or x -1 must be a multiple of p, and then the other is relatively prime to p ; so either x or x -1 must be a multiple of pn. If x mod 2 = x mod 5 = 0 or 1, we must have xmod 10 = 0 or 1; hence automorphs have xmod2 # xmod5 . (b) If x = qp + r, where r = 0 or 1, then r = r2 = r3, so 3×2 -2×3 G (6qpnr f 3r) -(6qpY + 27.) E T (modulo p ). (c) Let c be the magic constant (3(cx)2 -2(cx)3)/x2 = 3c2 -2c3x. Note: Since the last Ic digits of an n-digit automorph form a k-digit automorph, it makes sense to speak of the two oo-digit automorphs, x and 1 -x, which are IO-adic numbers (cf. exercise 4.1-31). The set of IO-adic numbers is equivalent under modular arithmetic to the set of ordered pairs (~1, UZ), where ~1 is a 2-adic number and 212 is a 5-adic number. SECTION 4.3.3 1. 27 x 47: 18 x 42: 09 x 05: 2718 x 4742: 08 04 00 1269 08 00 1269 -15 +Yi -45 -0045 49 16 45 0756 49 16 45 0756 1269 0756 0045 12888756 2.dm~ I dm < dQ+W+l= dC?+l, so lJ&+Rl I lJ&I + 1. 3. When /C 5 2, the result is true, so assume that k > 2. Let qk = 2Qk, rk = 2Rk, so that Rk = ]a] and Qk = &k–l + &-I. W e must show that 1 + (& + I)2Rk 5 ZQr-l; this inequality isn t close at all, one way is to observe that 1 $ (Rk + 1)2Rk 5 1+22R and 2Rk < &k-i when k > 2. (The fact that 2Rk < &k–l is readily proved by induction since Rk+i -Rk 5 1 and Qk -Qk-i 2 2.) 4. For j = 1, . . . , r, calculate U,(j ), jU0(j2), V,(j2), jVo(j2); and by recursively calling the multiplication algorithm, calculate W(j) = (Wj ) + ~&(~ ))(v,(~ ) + Po(j )), W(-j) = (&(j ) -j&(j2))(ve(j2) -jlqj )). Then we have lV,(j ) = f(W(j) + W(-j)), W& ) = i(W(j) -W(–j)). Also calculate W,(O) = U(O)V(O). Now construct difference tables for We and W,, which are polynomials whose respective degrees are r and r -1. This method reduces the size of the numbers being handled, and reduces the number of additions and multiplications. Its only disadvantage is a longer program (since the control is somewhat more complex, and some of the calculations must be done with signed numbers).

586 ANSWERS TO EXERCISES 4.3.2 6. (a) If e = f + kg, then 2 = 2f(2g)k = af . lk (modulo 2g -1). So if 2 = 2f (modulo 2g -l), we have 2e modg = af modg (modulo 2g -1); and since the latter quantities lie between zero and 2g -1 we must have e mod g = f mod g. (b) By part (a), (1 + zd + . . . + 2(c- )d). (ze -1) E (1 + sd + . . . + 2(c-1)d). (zd -1) = zCd-1 E 2 -1 = 2l -1 = 1 (modulo af -1). 7.(u, -(2)1 +ml(V2 fmz(w3 + +~~-2w~-l)…)))Cl~ . ..C(2-l)j = (Uj -W1)C13 . . .c(J-l)J -Tnlz)ZC13 . ..C(j-l)j -. . . -ml m,7-2w,-lclj.. . C(j-1)j E (IL7 -211) Clj . . . C(J-l)j -wzc23 c(J-l)j –w3-lC(j-l)j = ( . . . ((uj -vi) cij -~2) CQ -. . -~~-1) c(J-l)j (modulo mj). This method of rewriting the formulas uses the same number of arithmetic opera- tions and fewer constants; but the number of constants is fewer only if we order the moduli so that ml < m2 < . < m,, otherwise we would need a table of m, mod m3. This ordering of the moduli might seem to require more computation than if we made ml the largest, m2 the next largest, etc., since there are many more operations to be done modulo m, than modulo ml; but since VU~ can be as large as m3 -1, we are better off with ml < m2 < … < rnT in (23) 1 So this idea appears to be preferable to a so. the formulas in the text, although the formulas in the text are advantageous when the moduli have the form (14) as shown in Section 4.3.3. 8. m3–1.. .miw3 = m3-l.. . ml(…((u,-Wl ) Clj -V2)C2j - -w j-l)c(,-l)~ E m3-2.. ml ( . . . (uj -WI) cl2 -. . . -wJ-2)c(j-2j3 -w3–lm3-2.. ml = z uj -vi -wsml -. . - wl-im,-s . . ml (modulo m3). 9. ur + ((…(v,m,-1 +w7-l)mr–2 +…)rnl +wl)modm,, . . . . u2 +– (w,m, + wi)modm2, u1 t w1 modmi. (The computation should be done in this order, if we want to let uj and wj share the same memory locations, as they can in (23).) 10. If we redefine the mod operator so that it produces residues in the symmetrical range, the basic formulas (2), (3), (4) for arithmetic and (23), (24) for conversion remain the same, and the number u in (24) lies in the desired range (10). (Here (24) is a balanced mixed-radix notation, generalizing balanced ternary notation.) The comparison of two numbers may still be done from left to right, in the simple manner described in the text. Furthermore, it is possible to retain the value u3 in a single computer word, if we have signed magnitude representation within the computer, even if rnj is almost twice the word size. But the arithmetic operations analogous to (11) and (12) are more difficult, so it appears that on most computers this idea would result in slightly slower operation. 11. Multiply by m-t1 ml + 1 mr + 1 -= 2 ( 2 ” 2 1. Note that 2t.q = t (modulo m). In general if w is relatively prime to m, then we can find (by Euclid s algorithm) a number w = (vi,. . . , vi) such that VW = 1 (modulo m); and then if u is known to be a multiple of w we have u/w = uw , where the latter is computed with modular multiplication. When w is not relatively prime to m, division is much more difficult.

4.3.2 ANSWERS TO EXERCISES 585 3. u = uz (modulo m,) implies that u E LL% (modulo gcd(mi, mj)), so the condition uz G u3 (modulo gcd(m,, m3)) must surely hold if there is a solution. Furthermore if u F w (modulo m3) for all j, then u - u is a multiple of lcm(mi, . . , m,) = m; hence there is at most one solution. The proof can now be completed in a nonconstructive manner by counting the number of different r-tuples (~1,. . . , u?) satisfying the conditions 0 2 u3 < m3 and 2~~= uj (modulo gcd(m,, m3)). If this number is m, there must be a solution since (Umodml,…, ~modm,) takes on m distinct values as u goes from a to a f m. Assume that ~1,. , ~~-1 have been chosen satisfying the given conditions; we must now pick u7 = uj (modulo gcd(mj, m,)) for 1 5 j < r, and by the generalized Chinese remainder theorem for r -1 elements there are m/lcm(gcd(ml, m), . , gcd(m,-1, m,)) = m,/gcd(lcm(m1,. . , m-l), m,) = lcm(mi, , m,)/lcm(mr, . . . , m7-i) ways to do this. [This proof is based on identities (lo), (11) (12) and (14) of Section 4.5.2.1 A constructive proof [A. S. F raenkel, Proc. Amer. Math. Sot. 14 (1963), 790-7911 generalizing (24) can be given as follows. Let M3 = lcm(mi, . , mj); we wish to find u = v,M,-, + . . . + v2M1 + vi, where 0 5 oJ < M3/Mj–1. Assume that vi, . . , v3-i have already been determined; then we must solve the congruence w3M3–1 +v3–1MJ-2 +..+wi F 1~~ (modulo m3). Here ~~~-1 M3-~ + . . . + wi = 1~~ G U? (modulo gcd(mi, m3)) for i < j by hypothesis, so c = 1~~-( j-r Mj+-2 + . + ~1) is a multiple of lcm(gcd(mr, m,), , gcd(m,-1, m3)) = gcd(Mj-1, mj) = d,. We therefore must solve v.,M~-~ = c (modulo mj). By Euclid s algorithm there is a number c3 such that c3M3-l G d, (modulo m,); hence we may take wj = (cj c)/dJ mod (m3/d3). Note that, as in the nonconstructive proof, we have m,ld, = M3/Mj-1. 4. (After m4 = 91 = 7.13, we have used up all products of two or more odd primes that can be less than 100, so ms, must all be prime.) m7 = 79, ma = 73, mg = 71, ml0 = 67, ml1 = 61, ml2 = 59, ml3 = 53, ml4 = 47, mis = 43, ml6 = 41, ml7 = 37, ml8 = 31, ml9 = 29, mss = 23, m21 = 17, and then we are stuck (mzz = 1 does no good). 5. No. The obvious upper bound, 34527211 . . = J-J pt % lOOl, podd p prime is attained if we choose ml = 34, m2 = 52, etc. (It is more difficult, however, to maximize ml . . . m7 when r is fixed, or to maximize ml +. . +m, as we would attempt to do when using moduli 2mj -1.)

584 ANSWERS TO EXERCISES 4.3.1 The minimum value of v after one iteration of step N2 is 2 b(b + 1) -z11 w + 1 0 + 1) + 1 =I+;+;-; t >f if t = vi f 1. The minimum of this quantity occurs for t = b/2 + 1; a lower bound is 1 -3/2b. Hence vi 2 b -2, after one iteration of step N2. Finally, we have (l-3/2b)(l+ l/b)2 > 1, when b 2 5, so at most two more iterations are needed. The assertion is easily verified when b < 5. 29. True, since (uJ ulfn)b < 21. 30. In Algorithms A and S, such overlap is possible if the algorithms are rewritten slightly; e.g., in Algorithm A, we could rewrite step A2 thus: Set t + u3 + v3 + k, wj + t mod b, k + Lt/bj. In Algorithm M, vj may be in the same location as w3. In Algorithm D, it is most convenient (as in Program D, exercise 26) to let rl . . . r, be the same as urn+1 ZL,+,; and we can also have qo qm the same as 2~0 . . . urn, provided that no alteration of u3 is made in step D6. (Line 098 of Program D can safely be changed to JlP 2B , since ZL? isn t used in the subsequent calculation.) 31. Consider the situation of Fig. 6 with u = (u3uJ+i . ~,+~)s as in Algorithm D. If the leading nonzero digits of u and v have the same sign, set r + u -v, q + 1; otherwise set r t u+v, o t -1. Now if Irl > 2~ , or if Irl = IuI and the first 1 1 nonzero digit of ~j+~+r . . . um+n has the same sign as the first nonzero digit of r, set q + 0; otherwise set u3 u3+,, equal to the digits of r. 36. Values to 1000 decimal and 1100 octal places have been computed by R. P. Brent, Comp. Centre Tech. Rep. 47 (Canberra: Australian Nat. Univ., 1975). 37. Let d = 2e so that b > dvl > b/2. Instead of normalizing u and v in step Dl, simply compute the two leading digits viva of 2e(vlvavs)b by shifting left e bits. In step D3, use (vi, v)z) instead of (VI, vs) and (ui, ui+i, ~;+a) instead of (uj, uJ-tl, u~+~), where the digits u~~L~+~~L~+~ are obtained from (uju3+~u3+suJ+s)~ by shifting left e bits. Omit division by d in step D8. (In essence, ZL and v are being virtually shifted. This method saves computation when m is small compared to n.) SECTION 4.3.2 1. The solution is unique since 7 11 . 13 = 1001. The constructive proof of Theorem C tells us that the answer is ((11. 13)6 + 6. (7.13) + 5. (7. 11)12) mod 1001. But this answer is perhaps not explicit enough! By (23) we have u1 = 1, us = (6 -1). 8mod11=7,vs=((5-1).2-7).6 mod13=6,sou=6~7~11+7~7+1=512. 2. No. There is at most one such ZL; the additional condition 2~1 G . . . ZG u7 (modulo 1) is necessary and sufficient, and it follows that such a generalization is not very interesting.

4.3.1 ANSWERSTOEXERCISES 583 015 ENTI N A Multiply v by d. 016 ENTX 0 A 017 2H STX CARRY AN 018 LDA V,l AN 019 MULD AN (as in exercise 13) 026 JIP 2B AN 027 ENTi M+N A (Now rX = 0.) 028 2H STX CARRY A(M + N) Multiply u by d. 029 LDA U.1 ACM -t N) (as in exercise 13) 037 JlP 2B ACM + W 038 STX U A I 26. (See the algorithm of exercise 16.) 101 D8 LDA D 1 (Remainder will be left in 102 DECA 1 1 locations U+M+l through U+M+N) 103 JAZ DONE 1 Terminate if d = 1. 104 ENNl N A rI1 = j -n -1; j + 1. 105 ENTA 0 A r + 0. 106 IH LDX U+M+N+l,l AN rAX+ rb+u,+,. 107 DIV D AN 108 STA U+M+N+l,l AN 109 SLAX 5 AN r +-(rb + IL,+,) mod d. 110 INC2 1 AN jtj+1. 111 J2N IB AN -Repeat for 1 5 j 2 n. 1 At this point, the division routine is complete; and by the next exercise, register AX is zero. 27. It is du mod dv = d(u mod v). 28. For convenience, let us assume that v has a decimal point at the left, i.e., u = (wo.w~v~. . .)b. After step Nl we have 4 2 v < 1 + l/b: for bfl < v(b + 1) 41 + l/b) < 1 + 1 V--= I Vl + 1 J -n+l (llb)(vl + 1) b and > @l(b+ 1 -v,) vl+l -b w1+1 . The latter quantity takes its smallest value when vi = 1, since it is a convex function and the other extreme value is greater. The formula in step N2 may be written so we see as above that v will never become 2 1 + l/b.

582 ANSWERS TO EXERCISES 4.3.1 15. The error is nonnegative and less than (n -2)bpn- . [Similarly, if we ignore the products with i + j > n + 3, the error is bounded by (n -3)b- - , etc.; but, in some cases, we must compute all of the products if we want to get the true rounded result.] 16. Sl. Set r + 0, j + 1. S2. Set wj + L(rb + uj)/wJ, r + (rb + uj) mod v. S3. Increase j by 1, and return to S2 if j 5 n. 1 17. u/v > uob /(vl + l)b - = b(1 -l/(vi + 1)) > b(1 -l/(b/2)) = b - 2. 18. (uob + UI)/(VI + 1) < u/(z)1 + l)b-< u/v. 19. u -Qv 5 u -@lb+ -c&b+ = uzbn- + . . . + un + ?bn- -Qvzb -2 < b - (uz + 1 + Pb - @I~) < 0. Since u -Qv < 0, q < $. 20. If q 5 Q - 2, then u < (0 -1)v < o(vlbn- + (VZ + l)b - ) -v < &lbnpl + Qvzb - + bn- -v 5 @lb - + (bP + uz)b - + b --l -v = u,,bn + ulb - + uZbn-' + bn- -v 5 uObn + uibn- + uZbnp2 2 u. In other words, u < u, and this is a contradiction. 21. (Solution by G. K. Goyal.) The inequality ~24 5 bP + us implies that we have Q 5 (uob + ulb + uz)/(vlb + VZ) 5 u/((vlb + v2)bnp2). Now u modv = u -qv = ~(1 -o) where 0 5 (Y = q -u/w 5 Q - u/w 5 u(l/((vrb + w2)bnp2) -l/v) = u(vsb+ + . ..)/((v~b + vz)b - v) < u/(vlbv) 2 Q/(vlb) 5 (b -l)/(vrb), and this is at most 2/b since vi 2 a(b -1). 22. Let u = 4100, w = 588. We first try 0 = 191 = 8, but 8.8 > 10(41-40) + 0. Then we set 0 = 7, and now we find 7 . 8 < lO(41 -35) + 0. But 7 times 588 equals 4116, so the true quotient is q = 6. (Incidentally, this example shows that Theorem B cannot be improved under the given hypotheses, when b = 10.) 23. Obviously wlb/(w + 1)J < (v $ l)]b/(v + l)] 2 (v f l)b/(w + 1) = b; also if v 2 [b/Z] we obviously have vlb/(v + 1)J 2 w 2 [b/2]. Finally, assume that we have 1 5 u < lb/2J. Then wlb/(w + l)J > w(b/(w + 1) -1) 2 b/2 -1 2 Lb/S] -1, because v(b/(w + 1) -1) -(b/2 -1) = (b/2 -w -l)(v -l)/(v + 1) 2 0. Since wlb/(v + 1)J > [b/2] -1, we must have v]b/(v + l)] 2 lb/2j. 24. The approximate probability is only log, 2, not f. (For example, if b = 235, the probability is approximately &; this is still high enough to warrant the special test for d = 1 in steps Dl and D8.) 25. 002 ENTA 1 1 003 ADD V+l 1 004 STA TEMP 1 00.5 ENTA 1 1 006 JOV IF 1 Jump if ~1 = b - 1. 007 ENTX 0 1 008 DIV TEMP 1 Otherwise compute b/(vl + 1). 009 JOV DIVBYZERO 1 Jump if w1 = 0. MO IH STA D 1 011 DECA 1 1 012 JANZ *+3 1 Jump if d# 1. 013 STZ U 1-A 014 JMP D2 1-A

4.3.1 ANSWERSTOEXERCISES 581 8. ENNl N 1 2H LDA W+N+l,2 K JOV OFLO 1 INCA 1 K STZ W 1 STA W+N+1,2 K IH LDA U+N+l,l N DEC2 1 K ADD V+N+l,l iV JOV 2B K STA W+N+i,i N 3H INC2 1 N JNOV 3F N J2N 1B N ENT2 -1,l L I The running time depends on L, the number of positions in which uj + v3 2 b; and on K, the total number of carries. It is not difficult to see that K is the same quantity that appears in Program A. The analysis in the text shows that L has the average value N((b -1)/2b), and K has the average value +(N -b-l -b- -. . . -b- ). So if we ignore terms of order l/b, the running time is 9N + L + i K + 3 z 13N + 3 cycles. Note: Since a carry occurs almost half of the time, it would be more efficient to delay storing the result by one step. This leads to a somewhat longer program whose running time is approximately 12N + 5 cycles, based on the somewhat more detailed information calculated in exercise 7. 9. Replace b by bnp3 everywhere in step A2. 10. If lines 06 and 07 were interchanged, we would almost always have overflow, but register A might have a negative value at line 08, so this would not work. If the instructions on lines 05 and 06 were interchanged, the sequence of overflows occurring in the program would be slightly different in some cases, but the program would still be right. 11. (a) Set j + 1; (b) if 2~~ < vi, terminate [u < v]; if ZL~ = v~j and j = n, terminate [u=v];ifu3=v3andj v3, terminate [u > v]. This algorithm tends to be quite fast, since there is usually low probability that j will have to get very high before we encounter a case with 2~~ # vj. 12. Use Algorithm S with u3 = 0 and v~j = wj. Another borrow will occur at the end of the algorithm; this time it should be ignored. 13. ENTX N 1 ADD CARRY N JOV OFLO 1 JNOV *+2 N ENTX 0 1 INCX 1 K 2H STX CARRY N STA W.1 N LDA U,l N DECl 1 N MULV N JlP 2B N SLC 5 N STX W 1 I The running time is 23N + K + 5 cycles, and K is roughly fN. 14. The key inductive assertion is the one that should be valid at the beginning of step M4; all others are readily filled in from this one, which is as follows: 1 2 i 2 n; 1 < j 5 m; 0 5 u,. < b for 1 5 r 5 n; 0 5 v7 < b for 1 < r 2 m; 0 5 w?- < b for j

580 ANSWERS TO EXERCISES 4.3.1 4. We may make the following assertion before Al: n 2 1; and 0 2 ui, 21, < b for 1 5 i 5 n. Before A2, we assert: 1 2 j 2 n; 0 2 uz, vz < b for 1 2 i 5 n; 0 5 W, < b for j < i 5 n; 0 5 k 5 1; and (u?+~. . . u,)* + (Vj+l . %)b = (kwJ+l wn)b. The latter statement means more precisely that c utbn- + c vtbn- = kb -3 + c wtbn-t. j

4.3.1 ANSWERS TO EXERCISES 579 18. Let p(a) = P(La) and p(a, b) = xaikib p(k) for 1 5 a < b. Since L, = Lloa U Lloa+l I-, .. U Lloa+g for all a, we have;(a) = p(lOa, lO(a + 1)) by (i). Furthermore since P(S) = P(2S) + P(2S + 1) by (i), (ii), m , we have p(a) = p(2a, 2(a + 1)). ( ) It follows that p(a, b) = ~(2~lO~a, 2m10nb) for all m, n 2 0. If 1 < b/a < b /a , then p(a, b) 5 ~(a , b ). The reason is that there exist integers m, n, m , n such that 2 lO a 5 2m10na < 2 lO b 5 2m 10n b as a consequence of the fact that log 2/ log 10 is irrational, hence we can apply (v). (Cf. exercise 3.5-22 with Ic = 1 and U,, = nlog 2/ log 10.) In particular, p(a) 2 p(a + l), and it follows that p(a, b)/p(a, b + 1) 2 (b -a)/(b + 1 -a). (Cf. Eq. 4.2.2-15.) Now we can prove that p(a, b) = p(a , b ) w h enever b/a = b fa ; for p(a, b) = p(lOna, 10 b) 5 c,p(lOna, 10 b -1) 5 c,p(a , b ), for arbitrarily large values of n, where c,, = 10n(b -a)/(lO (b -a) -1) = 1 + O(lOmn). For any positive integer n we have p(an, b ) = p(a , ba - )+p(ba - , b2anp2)+ . . +p(bn- a, b ) = np(a, b). If 10m 5 an 5 10m+ and 10 2 b < 10n + , then PC10 m+l, 10m ) 5 p(an, b ) 5 p(lO , lo + ) by (v). But ~(1, 10) = Thy (iv), hence p(lO , 10m ) = m -m for all m 2 m. We conclude that [log,, b J -[log,, a ] -1 2 np(a, b) 5 Llogio b ] + ]logio a ] + 1 for all n, and p(a, b) = log,,(b/a). [This exercise was inspired by D. I. A. Cohen, who proved a slightly weaker result in J. Combinatorial Theory (A) 20 (1976), 367370.1 SECTION 4.3.1 2. If the ith number to be added is ui = (uziuis.. Uzn)b, use Algorithm A with step A2 changed to the following: A2 . [Add digits.] Set wj +- (urj + . + umj + k) mod b, and k t ](uiJ + . . . + urn3 + k)/bJ. (The maximum value of k- is m -1, so step A3 would have to be altered if m > b.) 3. ENTI N 1 JOV OFLO 1 Ensure overflow is off. ENTA 0 1 k + 0. 2H ENT2 0 N (r12 G next value of k) ENT3 MN-N, 1 N (LOC(ui,) = U + n(i -1) + j) 3H ADD U,3 MN rA t rA+u,,. JNOV *+2 MN INC2 1 K Carry one. DEC3 N MN Repeat for m 2 i 2 0. J3P 3B MN (r13 = n(i -1) + j) STA W,l N wj + rA. ENTA 0,2 N k + r12. DECl 1 N JIP 2B N Repeat for n 2 j 2 0. STA W 1 Store final carry in wc. 1 Running time, assuming that K = ;MN, is 5.5MN + 7N + 4 cycles.

578 ANSWERS TO EXERCISES 4.2.4 (The latter integral is essentially a dilogarithm. ) Hence the probability of a carry when k = 0 is (1/ln10)2(.rr2/6-2~n,1 l/n210 ) = .27154. [Note: When b = 2 and k = 0, fraction overflow always occurs,.so this derivation proves that zn>i - l/n22 = ?/12 -f(ln2)2.] When k > 0, the probability is Thus when b = 10, fraction overflow should occur with probability ,272~s + .Ol i pl f .002p2 +. . . When b = 2 the corresponding figures are PO +.655p1+.288p2 +.137ps + .067p4 + . Now if we use the probabilities from Table 1, dividing by .91 to eliminate zero operands and assuming that the probabilities are independent of the operand signs, we predict a probability of about 14 percent when b = 10, instead of the 15 percent in exercise 1. For b = 2, we predict about 48 percent, while the table yields 44 percent. These results are certainly in agreement within the limits of experimental error. 15. When k = 0, the leading digit is 1 if and only if there is a carry. (It is possible for fraction overflow and subsequent rounding to yield a leading digit of 2, when b 2 4, but we are ignoring rounding in this exercise.) The probability of fraction overflow is .272 < log,, 2, as shown in the previous exercise. When k > 0, the leading digit is 1 with probability 16. To prove the hint [which is due to Landau, Race matematyczno-fizyczne 21(1910), 103-1131, assume first that lim sup a, = X > 0. Let E = X/(X + 4M) and choose N so that ]ai +. . . + a,] < &cXn for all n > N. Let n > N/(1 -E), n > 5/e be such that a, > +X. Then, by induction, an-k 2 a,, -kM/(n -En) > i1 for 0 5 k < En, and c n--en $xcn. But since n -en > N. A similar contradiction applies if liminf a, < 0. Assuming that P,+r(n) --t X as n + 00, let ok = Pm(k) -A. If m > 0, the ak satisfy the hypotheses of the hint (cf. Eq. 4.2.2-15) since 0 5 Pm(k) 5 1; hence Pm(n) -+ A. 17. See Fibonacci Quarterly 7 (1969), 474-475. (Persi Diaconis [Ph.D. thesis, Harvard University, 19741 has shown among other things that the definition of probability by repeated averaging is weaker than harmonic probability, in the following precise sense: If lim,,, liminf,,, P,(n) = lim,,, lim SUP~+~ P,(n) = X then the harmonic probability is X. On the other hand the statement YOk2 2 n < 10k2+k for some integer k > 0 has logarithmic probability f , while repeated averaging never settles down to give it any particular probability.)