4.6.4 EVALUATION OF POLYNOMIALS 497 4. [M,20] The (Virtual web hosting)
4.6.4 EVALUATION OF POLYNOMIALS 497 4. [M,20] The text shows that scheme (3) is superior to Homer s rule when we are evaluating a polynomial with real coefficients at a complex point z. Compare (3) to Horner s rule when both the coefficients and the variable z are complex numbers; how many (real) multiplications and addition-subtractions are required by each method? 5. [MIS] Count the number of multiplications and additions required by the second- order rule (4). 6. [,?Z] (L. de Jong and J. van Leeuwen.) Show how to improve on steps Sl, . . . , S4 of the Shaw-Traub algorithm by computing only about in powers of 20. 7. [A424] How can PO, . . , Pn be calculated so that (6) has the value U(ZO + kh) for all integers k? 8. [MBI] The factorial power xk is defined to be k!(i) = ~(a: - 1). . . (z -k + 1). Explain how to evaluate unxE + . . . + ulxi + ZLO with at most n multiplications and 2n -1 additions, starting with z and the n + 3 constants un, . . . , UO, 1, n -1. 9. [A424] (H. J. Ryser.) Show that if X = (xij) is an n X n matrix, then summed over all 2n choices of ~1, . . . , en equal to 0 or 1 independently. Count the number of addition and multiplication operations required to evaluate per(X) by this formula. 10. [A&I] The permanent of an n X n matrix X = (xi3) may be calculated as follows: Start with the n quantities x11, 212, . , ~1~. For 1 5 k < n, assume that the (;) quantities ADS have been computed, for all k-element subsets S of {1,2, . . . , n}, where z&s = ~Xlj,... xkjk summed over all k! permutations j, . . . jk of the elements of S; then form all of the sums We have per(X) = &{I,...,,). How many additions and multiplications does this method require? How much temporary storage is needed? 11. [A4461 Is there any way to evaluate the permanent of a general n X n matrix using fewer than 2n arithmetic operations? 12. [A4501 What is the minimum number of multiplications required to form the product of two n X n matrices? What is the smallest exponent p such that O(np+ ) multiplications are sufficient for all E > O? 13. [M,%?] Find the inverse of the general discrete Fourier transform (3 7), by express- ing F(tl,. . . , tn) in terms of the values of f(sl, . . . , sn). [Hint: See Eq. 1.2.9-13.1 b 14. [HMZB] ( Fast Fourier transforms. ) Show that the scheme (40) can be used to evaluate the one-dimensional discrete Fourier transform f(s) = c F(t)@, w = ew2n, 0 5 s < 2 , using arithmetic on complex numbers. Estimate the number of arithmetic operations performed.