640 ANSWERS TO EXERCISES 4.6.4 2. Replacing z (Web host sites)
640 ANSWERS TO EXERCISES 4.6.4 2. Replacing z in (2) by the polynomial z + ~0 leads to the following procedure: Gl. Do step G2 for k = n, n -1, . . . , 0 (in this order), and stop. G2. Set uk t Uk, and then set v3 +- v3 j- sovj+l for j = k, k + 1, . . . , n -1. (When k = n, this step simply sets vn +-un.) 1 The computations turn out to be identical to those in Hl and H2, but performed in a different order. (This application was, in fact, Newton s original motivation for using scheme (2)) 3. The coefficient of zk is a polynomial in y that may be evaluated by Horner s rule: ( . . (u,,ox+(u,-l,ly+un-l,o))x+. . )x+(( . . . (uo,~~+uo,+-I)~+. )Y+uo,o). [For a homogeneous polynomial, such as unxn + u~-I?- Y +. .. + ~15~~~ + uoyn, another scheme is more efficient: if 0 < 1×1 2 IyJ, first divide x by y, evaluate a polynomial in x/y, then multiply by y .] 4. Rule (2) involves 4n or 3n real multiplications and 4n or 7n real additions; (3) is worse, it takes 4n + 2 or 4n + 1 mults, 4n + 2 or 4n + 5 adds. 5. One multiplication to compute x2; Ln/2] multiplications and Ln/2J additions to evaluate the first line; [n/21 multiplications and [n/21 -1 additions to evaluate the second line; and one addition to add the two lines together. Total: n+ 1 multiplications and n additions. 6. Jl. Compute and store the values xi, . . , xr . 52. Set vj + u3xo3–Ln 2J for 0 2 j 5 n. 53. For k = 0, 1, . . . , n -1, set vj + Vj + V~+I for j = n -1, , k + 1, k. 54. Set v, + v3xoLn 2J–j for 0 5 j < 72. 1 There are (n2 j-n)/2 additions, n+ [n/21 -1 multiplications, n divisions. Another mul- tiplication and division can be saved by treating vn and vo as special cases. Reference: SIGACT News 7, 3 (Summer 1975), 32-34. 7. Let Zj = xo + jh, and consider (42), (44). Set yj + U(xj) for 0 5 j 2 n. For k = 1, 2, . . . , n (in this order), set yj + yJ -y3-l for j = k, k + 1, . . , n (in this order). Now & = yj for all j. 8. See (43). 9. [Combinatorid Mathematics (Buffalo: Math. Assoc. of America, 1963), 26-28.1 This formula can be regarded as an application of the principle of inclusion and exclusion (Section 1.3.3), since the sum of the terms for n -~1 -. . . -en = k is the sum of all ZIP, ~2~~ . . . xnj, for which k values of the j, do not appear. A direct proof can be given by observing that the coefficient of xlJ1 . . . xnj, is c (-l),- - - , EjI . . . Ej,; if the j s are distinct, this equals unity, but if jI, . . . , j, # k then it is zero, since the terms for Ek = 0 cancel the terms for ek = 1. To evaluate the sum efficiently, we can start with ~1 = 1, ~2 = . . . = 6n = 0, and we can then proceed through all combinations of the E S in such a way that only one E changes from one term to the next. (See Gray code in Chapter 7.) The work to compute the first term is n- 1 multiplications; the subsequent 2n -2 terms each involve n additions, then n -1 multiplications, then one more addition. Total: (2% - l)(n -1) multiplications, and (2n -2)(n + 1) add i t ions. Only n + 1 temp storage locations are needed, one for the main partial sum and one for each factor of the current product.