Web host forum - 4.3.3 ANSWERS TO EXERCISES 587 12. Obvious from
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).