Web hosting providers - 584 ANSWERS TO EXERCISES 4.3.1 The minimum value
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.