582 ANSWERS TO EXERCISES 4.3.1 15. The error
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