4.2.2 ANSWERS TO EXERCISES 573 Ykqk + qkok (Web hosting account)
4.2.2 ANSWERS TO EXERCISES 573 Ykqk + qkok + YkvkOk)gk-I, for 1 < k < n. Thus fn = 1 + ql -71 + (4n t'?rmS of 2nd order) + (higher order terms) = 1 + ~1 -yi +,0(nc2) is sufficiently small. [The Kahan summation formula was first published in CACA4 8 (1965), 40; cf. Proc. IFIP Congress (lgi l), 2, 1232. For another approach to accurate summation, see R. J. Hanson, CACM 18 (1975), 57-58. See also G. Bohlender, IEEE Trans. C-26 (1977), 621-632, for algorithms that compute round(zi $. . .fsn) and round(zi . . xn) exactly, given (~1,. . . , xn}.] 20. By the proof of Theorem C, (47) fails for e w = p only if ] u( + f 2 ]u, -u( 2 bP- +b- ; hence ]fU] 2 ]fv] 2 l-($b-l)beP. Thisratherrarecase, inwhich ]fw] before normalization takes its maximum value 2, is necessary and sufficient for failure. 21. (Solution by G. W. Veltkamp.) Let c = 2 rpP1 + 1; we may assume that p 2 2, so c is representable. First compute u = u @ c, ui = (u 0 u ) @ u , u2 = u @ ul; similarly, v = w @ c, 2ri = (v 8 v ) $ u , v2 = w 0 VI. Then set w t u @ u, w' + (((Ul @Vl@W) cB('1Ll@aV2))$(U2 @Wl))@(zLZ @w2). It suffices to prove this when u, v > 0 and e U = e, = p, so that u and v are integers E [2p- , 2p). Then u = ui + u2 where 2p-1 2 ui 2 2p, u1 mod2rp/ 1 = 0, and ]uz] 5 2Tp 21-1; similarly u = wi + 212. The operations during the calculation of 20 are exact, because w -uivl is a multiple of 2p- such that ]w -urvi ( 5 Jw - uw] + IUZWl + UlW2 + t&w21 2 2p- + 2p+ p12 + 2p- ; and similarly ]w -2~1~ -uivz] 5 Iw -uw( + Iu2wI < 2p-l + 2 p +l+p, where w -ulul -ulv2 is a multiple of 2 p/21. 22. We may assume that bp- 2 u, v < bP. If uw 2 b2p-1, then xi = uv -r where JrJ 2 $bp- , hence 22 = round(u -r/v) = xo (since [r/v] 5 +bpP1/bp- 2 3, and equality implies v = bp- hence r = 0). If UD > b2p-1, then ~1 = uv -r where JrJ 5 3bp, hence xl/v 2 u -r/v < bP + +b and x2 2 bP. If 52 = bP, then x3 = x1 (for otherwise (bP -$)w 5 xi 2 bp(w -1)). If x2 < bP and xi > b2p-1, then let x2 = XI/W +q where )q) 5 f; we have xs = round(xl + qw) = xi. Finally if 22 < bP and x1 = b2p- and 5s < b2p-1, then x4 = x2 by the first case above. This situation arises, for example, when b = 10, p = 2, u = 19, w = 55, xi = 1000, 22 = 18, z3 = 990. 23. Let [uJ = n, so that u @ 1 = u 0 n = u -n + r where Jr] 5 +bAp; we wish to show that round(n -r) = n. The result is clear if In] > 1; and r = 0 when n = 0 or 1, so the only subtle case is when n = -1, r = –+bmp. The identity fails iff b is a multiple of 4 and –b-l < u < -be2 and umod2bYP = 2bCp (e.g., p = 3, b = 8, u = -(.0124)8). 24. Let u = [ui, u7], w = [v,, We]. Then u $ u = [ul v ~1, ur Au?], where x A y = y A 2, x A +0 = x for all x, 5 f& -0 = x for all x # +0, Ic A +oo = fee for all x # -co, and x & --oo needn t be defined; x v y = -((-x) A(-y)). If x @ y would overflow in normal floating point arithmetic because x + y is too large, then 2 A y is foe and x v y is the largest representable number. For subtraction, let u 0 v = u $ (-v), where --2, = (-v,, -wr]. Multiplication is somewhat more complicated. The correct procedure is to let u@w = [min(ul~vl,ul~v,,u,~vl,2L~~wr), max(ul~wl,u1~w7.,u7~w1,uT~wIUT)], where xAy = yAs, xa(-y) = -(xvy) = (-x)Ay; xA+0 = (j-0 for x > 0, -0 for z < 0); xA--0 = -(xA+O); xA+oo = (+co for x > +0, –co for x < -0). (It is possible to determine the min and max simply by looking at the signs of ul, u,., VI, and v,., thereby computing only two of the eight products, except when