Managed web hosting - 4.6.4 ANSWERS TO EXERCISES 647 39. By induction
4.6.4 ANSWERS TO EXERCISES 647 39. By induction on m. Let W,(Z) = z2m + ~~~~~~~~~~ + . . . + 2~c, WJ~-~(Z) = X 2m-2 +f2m–3x 2m-3 f . . . + VO, a = cyi + yrn, b = om, and let f(r) = Ci,j~o(-l)i+3(i~3)u,+i+2jai~. It follows that v7 = f(r + 2) for r 2 0, and 6, = f(1). If 6, = 0 and a is given, we have a polynomial of degree m -1 in b, with leading coefficient &(21z,,+l -mu) = *(r2 + … +~~-m-d. In Motzkin s unpublished notes he arranged to make 6k = 0 almost always, by choosing y s so that this leading coefficient is # 0 when m is even and = 0 when m is odd; then we almost always can let b be a (real) root of an odd-degree polynomial. 40. No; S. Winograd found a way to compute all polynomials of degree 13 with only 7 (possibly complex) multiplications [Comm. Pure and Applied Math. 25 (1972), 455-4571. L. Revah found schemes that evaluate almost all polynomials of degree n > 9 with ]n/2] + 1 (possibly complex) multiplications [SIAM J. Computing 4 (1975), 381-3921; she also showed that when n = 9 it is possible to achieve [n/2] + 1 multiplications only with at least n+3 additions. By appending sufficiently many additions (cf. exercise 39), the almost all and possibly complex provisos disappear. V. I^a. Pan [Proc. ACM Symp. Theory Comp. 10 (1978), 162-172; IBM Research Report RC7754 (1979)] found schemes with Ln/2]+1 (complex) multiplications and the minimum number n+2+&s of (complex) additions, for all odd n 2 9; his method for n = 9 is V(X) = ((x + a) + D)(x + Y), w(x) = V(X) + x, t(x) = (v(x) + 6)(4x) + 6) -(v(x) + b )(w(x) + E ), 4×1 = (v(x) + c)(e) + rl) + K. The minimum number of real additions necessary, when the minimum number of (real) multiplications is achieved, remains unknown for n 2 9. 41. u(c + d) -(a + b)d + i(u(c + d) + (b-a)~). [B eware numerical instability. Three multiplications are necessary, since complex multiplication is a special case of (69) with p(u) = u2 + 1. Without the restriction on additions there are other possibilities. For example, the symmetric formula UC - bd + i((u + b)(c + d) -UC - bd) was suggested by Peter Ungar in 1963; cf. Eq. 4.3.3-2 with 2 replaced by i. See I. Munro, Proc. ACM Symp. Theory Comp. 3 (1960), 40-44; S. Winograd, Linear Alg. Appl. 4 (1971), 381-388.1 Alternatively, if u2 + b2 = 1 and t = (1 -u)/b = b/(1 + a), the algorithm w = c - td, v = d + bw, u = w -tv for calculating the product (u + bi)(c + di) = u + iv has been suggested by Oscar Buneman [J. Comp. Phys. 12 (1973), 127-1281. In this method if a = cos 6 and b = sin 8, we have t = tan(0/2). [Helmut Alt and Jan van Leeuwen have shown that four real multiplications or divisions are necessary for computing l/(u + b ) a , and four are sufficient for computing u/(b + ci). It is unknown whether (u + bi)/(c + di) can be computed with only five multiplications or divisions.] 42. (a) Let ~1, . . . , 7rTm be the Xi s that correspond to chain multiplications; then 7ri = Pzz-l XPZ~ and U(X) = Pz,,+i, where each Pj has the form @+&x+p~i~i+…+ p37(j)rY(3), where r(j) 5 [j/2] -1 and each of the & and &k is a polynomial in the o s with integer coefficients. We can systematically modify the chain (cf. exercise 30) so that p3 = 0 and ,&l = 1, for 1 5 j 5 2m; furthermore we can assume that