MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

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

646 ANSWERS TO EXERCISES 4.6.4 For the given rational function we have QYj Pj w[j (x) & (x) 1 2 x+5 3x+ 19 3 4 1 5 so u[ l(x)/w[o~(x) = 1 + 2/(x + 3 + 4/(x + 5)). Notes: A general rational function of the stated form has 2n + 1 degrees of freedom, in the sense that it can be shown to have 2n + 1 essentially independent parameters. If we generalize polynomial chains to arithmetic chains, which allow division operations as well as addition, subtraction, and multiplication, we can obtain the following results with slight modifications to the proofs of Theorems A and M: An arithmetic chain with q addition-subtraction steps has at most q+l degrees of freedom. An arithmetic chain with m multiplication-division steps has at most 2m + 1 degrees of freedom. Therefore an arithmetic chain that computes almost all rational functions of the stated form must have at least 2n addition-subtractions, and n multiplication- divisions; the method in this exercise is optimal. 38. The theorem is certainly true if n = 0. Assume that n is positive, and that a polynomial chain computing P(x; ~0, . . . , 2~~) is given, where each of the parameters aj has been replaced by a real number. Let Xi = Xj X Xk be the first chain multiplication step that involves one of ~0, . . . , un; such a step must exist because of the rank of A. Without loss of generality, we may assume that X, involves u,; thus, Xj has the form houo +. . . + hnun + f(x), where ho, . . , h, are real, h, # 0, and f(x) is a polynomial with real coefficients. (The h s and the coefficients of f(x) are derived from the values assigned to the cy s.) Now change step i to Xi = oi X Xk, where cr is an arbitrary real number. (We could take QI = 0; general cr is used liere merely to show that there is a certain amount of flexibility available in the proof.) Add further steps to calculate X = (a -f(x) -houo -. . . - h,-lu,-1)/h,; these new steps involve only additions and parameter multiplications (by suitable new parameters). Finally, replace X-,-1 = 2~~ everywhere in the chain by this new element X. The result is a chain that calculates Q(x; 210,. . . , t&.-1) = P(x; uo, . . . , h-1, (a -f(x) -houo -.. . - hn-1%~1)lhn); and this chain has one less chain multiplication. The proof will be complete if we can show that Q satisfies the hypotheses. The quantity (a -f(x))/hn leads to a possibly increased value of m, and a new vector B . If the columns of A are Ao, AI, . . . > A, (these vectors being linearly independent over the reals), the new matrix A corresponding to Q has the column vectors Ao -(ho/h&k , An-1 -(hn-l/hn)An, plus perhaps a few rows of zeros to account for an increased value of m, and these columns are clearly also linearly independent. By induction, the chain that computes Q has at least n -1 chain multiplications, so the original chain has at least n. [Pan showed also that the use of division would give no improvement; cf. Problemy Kibernetiki 7 (1962), 21-30. Generalizations to the computation of several polynomials in several variables, with and without various kinds of preconditioning, have been given by S. Winograd, Comm. Pure and Applied Math. 23 (1970), 165-179.1

4.6.4 ANSWERS TO EXERCISES 645 that calculates a fourth-degree polynomial has the form x1= &+x0 x2 = 02 +x0 x3 =x1x x2 x4 = ara+X3 x5 =04+x3 x6 =x4 x x5 x7 = a5+A6 Actually this chain has one addition too many, but any correct scheme can be put into this form if we restrict some of the o s to be functions of the others. Now X7 has the form (x2 +Az+B)(z2+Az+C)+D = x4+2Az3+(E+A2)x2+EAx+F, where A=cul+crz,B=crlcrz$ff~g,C=crlcrz+ar,D=(rs,E=B$C,F=BC+D; and since this involves only three independent parameters it cannot represent a general manic fourth-degree polynomial. 36. As in the solution to exercise 35, we may assume that the chain computes a general manic polynomial of degree six, using only three chain multiplications and six parameter additions. The computation must take one of two general forms x1= &+x0 x1= %+x0 x2 = orz+xo x2 = @2+X0 x3 =x1 x x2 x3 =x1 x x2 x4 =aa+Xo x4 = as+X3 x5 =ffr+XB x5 =cy4+x3 x6 =x4 x x5 x6=x4 x x5 x7 =aS+x6 x7 = a5 +X3 b3 =a6+A6 &I = a6+i6 x9 =x7 x x6 19 =x7 x x&3 AlO =&7+x9 110 =07+x9 where, as in exercise 35, an extra addition has been inserted to cover a more general case. Neither of these schemes can calculate a general sixth-degree manic polynomial, since the first case is a polynomial of the form and the second case (cf. exercise 35) is a polynomial of the form (x4 + 2Az3 + (E + A2)x2 + EAx + F)(x2 + Az + G) + H; both of these involve only five independent parameters. 37. Let u[Ol(x) = unxn + ~~-~x~–l + . . . + uc, v[ ](z) = zn + 21n-15n-1 f.. . + ~0. For 1 2 j 5 n, divide U[J- l(z) by the manic polynomial v(~-~](x), obtaining u[ - l(z) = (y3vIwl (x) + pjv[jl(x). Assume that a manic polynomial v[~](x) of degree n - j exists satisfying this relation; this will be true for almost all rational functions. Let u[jl(x) = ~[j+ l(x) -XW~~~(X). These definitions imply that deg(uln]) < 1, so we may let on+1 = u( ](z).

644 ANSWERS TO EXERCISES 4.6.4 30. Starting with the construction in Theorem M, we will prove that mp+(l-~~om,) of the /3 s may effectively be eliminated: If pi corresponds to a parameter multiplication, we have pLz = PZG-1 x (Tz + Pz~); add P -P c 2% 1 2%t o each pj for which cpi occurs in Tj, and replace ,& by zero. This removes one parameter for each parameter multiplication. If pLz is the first chain multiplication, then /-lZ is the first chain multiplication, then pZ = (ylz + 81-k ,&-1) X (7~~ + 02 $ &), where 71, 72, 01, 02 are polynomials in pi, . . . , pzZ-z with integer coefficients. Here 6 1 and 6 2 can be absorbed into ,&-I and &, respectively, so we may assume that 01 = 82 = 0. Now add c&i-1pzi to each & for which cpL2 occurs in Tj; add &–172/71 to &; and set &-I to zero. The result set is unchanged by this elimination of &i-1, except for the values of CQ, . . . , cr, such that y1 is zero. [This proof is essentially due to V. I^a. Pan, Russian Mathematical Surveys 21,l (1966), 105-136.1 The latter case can be handled as in the proof of Theorem A, since the polynomials with yl = 0 can be evaluated by eliminating p2i (as in the first construction, where pLz corresponds to a parameter multiplication). 31. Otherwise we could add one parameter multiplication as a final step, and violate Theorem C. (The exercise is an improvement over Theorem A, in this special case, since there are only n degrees of freedom in the coefficients of a manic polynomial of degree n.) 32. XI = X0 X X0, X2 = cyl X XI, X3 = (~2 +X2, X4 = X3 x X1, X5 = ct3 +X4. We need at least three multiplications to compute 2~4~~ (see Section 4.6.3), and at least two additions by Theorem A. 33. We must have n+l 2 2m,+m,+&,,, and mc+mp = (n+l)/2; so there are no parameter multiplications. Now the first X, whose leading coefficient (as a polynomial in Z) is not an integer must be obtained by a chain addition; and there must be at least n + 1 parameters, so there are at least n + 1 parameter additions. 34. Transform the given chain step by step, and also define the content ci of Xi, as follows: (Intuitively, cz is the leading coefficient of Xi.) Define CO = 1. (a) If the step has the form A, = cyj + xk, replace it by A, = @, + &, where pj = &j/ck; and define cz = ck. (b) If the step has the form Xi = aj -xk, replace it by Xi = pj + Xk, where p, = -cr,/ck; and define ci = -ck. (c) If the step has the form 1, = Yj X xk, replace it by X, = xk (the step will be deleted later); and define cz = (d) If the ajck. step has the form A, = 1, X xk, leave it unchanged; and define ci = cjck. After this process is finished, delete all steps of the form Xi = &, replacing Xi by xk in each future step that uses Xj. Then add a final step X,+1 = p X X,, where p = CT. This is the desired scheme, since it is easy to verify that the new Xi are just the old ones divided by the factor ct. The p s are given functions of the CY S; division by zero is no problem, because if any ck = 0 we must have cr = 0 (hence the coefficient of xn is zero), or else xk never contributes to the final result. 35. Since there are at least five parameter steps, the result is trivial unless there is at least one parameter multiplication; considering the ways in which three multiplications can form u4z4, we see that there must be one parameter multiplication and two chain multiplications. Therefore the four addition-subtractions must each be parameter steps, and exercise 34 applies. We can now assume that only additions are used, and that we have a chain to compute a general manic fourth-degree polynomial with two chain multiplications and four parameter additions. The only possible scheme of this type

4.6.4 ANSWERS TO EXERCISES 643 22. 0Z6 = 1, ff,, = -1, 01 = 1, p1 = -2, p2 = -2, /& = -2, @z, = 1, Cy3 = -4, ~2 = 0, ~4 = 4, CQ = -2. We form z = (X -1)X + 1, w = z + X, and u(X) = ((z -x -4)w + 4)~ -2. In th IS special case we see that one of the seven additions can be saved if we compute w = x2 + 1, z = w -X. 23. (a) We may use induction on n; the result is trivial if n < 2. If f(0) = 0, then the result is true for the polynomial f(z)/ Z, SO it holds for f(z). If f(Q) = 0 for some real y # 0, then g(fiy) = h&y) = 0; since the result is true for f(z)/(z2 + y ), it hold8 also for f(z). Therefore we may assume that f(z) has no root8 whose real part is zero. NOW the net number of times the given path circles the origin is the number of roots of f(z) inside the region, which is at most 1. When R is large, the path f(ReZt) for r/2 5 t < 37~/2 will circle the origin clockwise approximately n/2 times; so the path f(it) for -R 5 t < R must go counterclockwise around the origin at least n/2 -I times. For n even, this implies that f(it) crosses the imaginary axis at least n-2 times, and the real axis at least n -3 times; for n odd, f(it) crosses the real axis at least n -2 times and the imaginary axis at least n -3 times. These are roots respectively of g(it) = 0, h(it) = 0. (b) If not, g or h would have a root of the form a + bi with o # 0 and b # 0. But this would imply the existence of at least three other such roots, namely o -bi and –a f bi, while g(z) and h(z) have at most n roots. 24. The roots of u are -7, -3 * i, -2 f i, and -1; permissible value8 of c are 2 and 4 (but not 3, since c = 3 makes the sum of the roots equal to zero). Case I, c = 2: p(x) = (x + 5)(x2 + 2x + 2)(x + 1)(X -1) = x6 +6X5 +6×4 +4X3 -5×2 -2x -10; q(x) = 6×2 +4x -2 = 6(s + 1)(x -4). L et (~2 = -1, cyi = 5; pr(x) = x4 f 6×3 + 5×2 -2x -10 = (x2 + 6x + q)(x -3) -9 ; CYO= 6, PO = 9, p1 = -y. Case 2, c = 4: A similar analysis gives oz = 9, crl = -3, are = -6, PO = 12, pi = -26. 25.h = 02, p2 = 201, /33 = a-r, /34 = a6, /35 = PEG = 0, /& = CY~, ,&, = 0, p9 = 2ffl -as. 26. (a) Xl = cyl x XO, X2 = cy2+Xl, X3 =X2 xX0, X4 = cy3+X3, X5 =X4 x X0, x6 =04+x5. (b)n~ = l+piX, ~2 = l-l-P~KIX, 1c3 = l+ 03~25, U(X)= p4~3 = ,&/32~3~4×3 +p2p3p4×2 +/33/34x+/?4. (c) If any coefficient is zero, the coefficient of x3 must also be zero in (b), while (a) yields an arbitrary polynomial 01×3+~2×2+03x+~4 of degree 5 3. 27. Otherwise there would be a nonzero polynomial f(qn, . . . , 41, qo) with integer coeffi- cients such that q,, . f(qn, , 41, qo) = 0 for all sets (qn, . . . , qo) of real numbers. This cannot happen, since it is easy to prove by induction on n that a nonzero polynomial always takes on some nonzero value. (Cf. exercise 4.6.1-16. However, this result is false for finite fields in place of the real numbers.) 28. The indeterminate quantities CY~, . . . , cyLl form an algebraic basis for the polynomial domain &[cyi, . . , cys], where & is the field of rational numbers. Since s + 1 is greater than the number of elements in a basis, the polynomials f3(01, . , a,) are algebraically dependent; this means that there is a nonzero polynomial g with rational coefficients such that g(fo(cui, . , as), . . . , fs(cyl,. , as)) is identically zero. 29. Given j8, . . . , j, E (0, 1, . . . , n}, there are nonzero polynomials with integer coefficients such that gj(qj,, . . . , qjt) = 0 for all (qn,. . . , qo) in Rj, 1 5 j 5 m. The product glg2 . ..g.isthereforezeroforall(q,,…,qo)inR1U…UR,.

642 ANSWERS TO EXERCISES 4.6.4 These calculations assume that the given numbers F(t) are complex. If the F(t) are real, then f(s) is the complex conjugate of f(2 -s), so we can avoid the redundancy by computing only the 2 independent real numbers f(O), Xif(l), . . . , Bf(2 - -l), fP-1), Sf(l), . . . , Sf(2 -l -1). The entire calculation in this case can be done by working with 2n real values, using the fact that flkl(&-k+l, .. . , sn, ti, . . . , i&-k) will be the Complex COnjUgate Of flkl(sk-k+i,. . . , SL, ti, . . . , tn.-k) when (S1 . . . S~)Z + (si . . sk)z E 0 (modulo 2 ). About half as many multiplications and additions are needed as in the complex case. [The fast Fourier transform algorithm is essentially due to C. Runge and H. Kijnig in 1924, and it was generalized by J. W. Cooley and J. W. Tukey, Math. Comp. 1s (i965), 297-301 . Its interesting history has been traced by J. W. Cooley, P. A. W. Lewis, and P. D. Welch, Proc. IEEE 55 (1967), 1675-1677. Details concerning its use have been discussed by R. C. Singleton, CACM 10 (1967), 647-654; M. C. Pease, JACM 15 (1968), 252-264; G. D. Berglund, Math. Comp. 22 (1968), 275-276, CACM11(1968), 703-710; A. M. Macnaghten and C. A. R. Hoare, Comp. J. 20 (1977), 78-83. See also exercises 53, 57, and 59.1 15. (a) The hint follows by integration and induction. Let f( )(e) take on all values be- tween A and B inclusive, as 19 varies from min(zs, . . , xn) to max(zc, . . . , zn). Replacing f( ) by each of these bounds, in the stated integral, yields A/n! 2 f(zo, . . . , z,) 5 B/n!. (b) It suffices to prove this for j = 7~. Let f be Newton s interpolation polyno- mial, then f( ) is the constant n!a,. 16. Carry out the multiplications and additions of (43) as operations on polynomials. (The special case ~0 = ~1 = . . . = zn is considered in exercise 2. We have used this method in step C8 of Algorithm 4.3.3C.) 17. T. M. Vari has shown that n -1 multiplications are necessary, by proving that 12 multiplications are necessary to compute ~2 + . . . + 2: [Cornell Computer Science Report 120 (Jan. 1972)]. 18. cio = +(us/uq+l), p = uz/uq-oo(cyo-1), ~1 = crop-uul/ur, CYZ= p-2~~1, a3 = uo/u4 -W(crl + (Yz), a4 = u4. 19. Since cy5 is the leading coefficient, we may assume without loss of generality that U(Z) is manic (i.e., us = 1). Then QO is a root of the cubic equation 40z3 - 24.2~4~~+ (4U: + 2Us)Z + (Uz - usu,) = 0; this equation always has at least one real root, and it may have three. Once (~0 is determined, we have 01s = u4 -4o0, CY~ = us - 4acos - 6a;, ff2 = 1~1-QO(CXOQ~+ 4c&3 + 2oi(rs + a;), (~4 = uo -CQ(~; + ala; + (~2). For the given polynomial we are to solve the cubic equation 40z3 -120~~ + 802 = 0; this leads to three solutions (CYO, cyi, cy2, cys, CY~, as) = (0, -10,13,5, -5, l), (1, -20,68,1,11, l), (2, -10,13, -3,27,1). 20. LDA X FADD =a~= FADD =cY~= FMUL TEMP2 STA TEMPI FADD =a~= FADD =a,~-a3= FMUL TEMPl STA TEMPZ FADD =a4= FMUL TEMP2 FMUL =cx5= I STA TEMP2 21. z = (z+l)s-2, w = (x+5)z+9, U(Z) = (w+z-8)w-8; or z = (%+9)x+26, w = (5 -3)~ + 73, u(x) = (w + z - 24)~ -12.

4.6.4 ANSWERS TO EXERCISES 641 10. c rlkcn(k + l)(kT1) = n(2%- -1) multiplications and xilkcn /~(~;i) = n2n-1 -2n + 1 additions. This is approximately half as many arithmetic operations as the method of exercise 9, although it requires a more complicated program to control the sequence. Approximately (rnTzl) + (ml.$-l) temporary storage locations must be used, and this grows exponentially large (on the order of 2n/,,/?i). The method in this exercise is equivalent to the unusual matrix factorization of the permanent function given by Jurkat and Ryser in J. Algebra 5 (1967), 342-357. It may also be regarded as an application of (39) and (40), in an appropriate sense. 12. Here is a brief summary of progress on this famous research problem: J. Hopcroft and L. R. Kerr proved, among other things, that seven multiplications are necessary in 2 X 2 matrix multiplication [SIAM J. Appl. Math. 20 (1971), 30-361. R. L. Probert showed that all 7-multiplication schemes, in which each multiplication takes a linear combination of elements from one matrix and multiplies by a linear combination of elements from the other, must have at least 15 additions [SIAM J. Computing 5 (1976), 187-2031. For n = 3, the best method known is due to J. D. Laderman [Bull. Amer. Math. Sot. 82 (1976), 126-1281, who showed that 23 noncommutative multiplications suffice. His construction has been generalized by Ondrej Sykora, who exhibited a method requiring n3-(n-l)2 noncommutative multiplications and n3-n2+11(n-l)2 additions, a result that also reduces to (36) when n = 2 [Lecture Notes in Comp. Sci. 53 (1977), 504-5121. The best lower bound known to hold for all n is the fact that 2n2 -1 nonscalar multiplications are necessary [Jean-Claude Lafon and S. Winograd, Theoretical Camp. Sci., to appear]. Pan has generalized this to a lower bound of mn + ns f m -n -1 in the m X n X s case [see SIAM J. Computing 9 (1980), 3411. The best upper bounds known for large n were changing rapidly as this book was being prepared for publication; see exercises 60-64. 13. By summing geometric series, we find that F(tr, . , t,) equals c 0js1

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.

4.6.4 ANSWERS TO EXERCISES 639 37. The statement is true. The labels in the reduced graph of the binary chain are [TZ/~~] for k = eo, . . . , 0; they are 1, 2, . . . , 2e0, n in the dual graph. [Similarly, the right-to-le% m-ary method of exercise 9 is the dual of the left-to-right method.] 38. 2t are equivalent to the binary chain; it would be 2t-1 if eo = el + 1. The nu ber of chains equivalent to the scheme of Algorithm A is the number of ways to cornT ute the sum of t + 2 numbers of which two are identical. This is fjt+, + +ft, where fm is the number of ways to compute the sum of m + 1 distinct numbers. When we take commutativity into account, we see that fm is 2-m times (m + l)! times the number of binary trees on m nodes, so fm = (2m -1)(2m -3). . . 1. 39. The quantity l([nl, nz,. . . , nm]) is the minimum of arcs -vertices + m taken over all directed graphs having m vertices Sj whose in-degree is zero and one vertex t whose out-degree is zero, where there are exactly nj oriented paths from sj to t for 1 < j 5 m. The quantity l(nl, 722,. . , n,) is the minimum of arcs-vertices+1 taken over all directed graphs having one vertex s whose in-degree is zero and m vertices tj whose out-degree is zero, where there are exactly nJ oriented paths from s to tj for 1 2 j 5 m. These problems are dual to each other, if we change the direction of all the arcs. Note: C. H. Papadimitriou points out that this is a special case of a much more general theorem. Let N = (nij) be an m X p matrix of nonnegative integers having no row or column entirely zero. We can define I(N) to be the minimum number of multiplications needed to compute the set of monomials { z; ~. . . xkrn3 1 1 5 j 5 p}. Now 1(N) is also the minimum of arcs - vertices + m taken over all directed graphs having m vertices si whose in-degree is zero and p vertices t, whose out-degree is zero, where there are exactly nt3 oriented paths from si to t, for each i and j. By duality we have I(N) = l(NT) + m -p. N. Pippenger has proved a comprehensive generalization of the results of exercises 27 and 32. Let L(m, p, n) be the maximum of I(N) taken over all m X p matrices N of nonnegative integers nij 5 n. Then L(m,p, n) = min(m,p)lgn + H/lgH f O(m + p + H(loglogH) /2(logH)-3/2), w h ere H = mpIg(n + 1). [SIAM J. Com- puting 9 (1980), 230-250.1 40. By exercise 33, it suffices to show that l(mlnl $ . . + mtnt) _< l(ml, . . . , mt) + l([nl,. . . , n,]). But this is clear, since we can first form {xml,. . . , rmt} and then compute the monomial (~~l)~l.. . (xmt) +. Notes: Theorem F is a special case of this result, since we clearly have 1(2 , Z) 2 m + V(Z) -1 when X(Z) 2 m. One strong way to state Olivos s theorem is that if a~, . . I a, andbo, . . . . b, are any addition chains, then 1(c cijaib,) < r + s + c ct3 -1 for any (T + 1) X (s + 1) matrix of nonnegative integers Cij. 41. [To appear.] The stated formula can be proved whenever A 2 9m2. Since this is a polynomial in m, and since the problem of finding a minimum vertex cover is NP hard (cf. Section 7.9), the problem of computing l(nl, . . . , n,) is NP complete. [It is unknown whether or not the problem of computing l(n) is NP complete.] SECTION 4.6.4 1. Set y +- x2, then compute (( . . . (~2~+ly $ u~~-l)y + . . . )y + 2~1)~.

638 ANSWERS TO EXERCISES 4.6.3 blocks of > CY in a row. If m and m have P(o), so does m V m ; if m has P(a) then p(m) has P(cy + 6). Hence Bi has P(l + 6~). Finally if-m has P(a) then v(p(m)) 5 (a + G)v(m)/a; for v(m) = vi + . . . + vq, where each block size vj is 2 cr, hence &Cm)) I (~1 + 6) + . . . i- (vq + 6) I (1 -I- 6/@1 i-. . . t (1-k bl4b (4 Let f = b, + cI be the number of nondoublings and s the number of small steps. If f 2 3.2711gv(n) we have s 2 lgv(n) as desired, by (16). Otherwise we have ai 5 (1 + 2-6)bi2CE+dt for 0 5 i < r, hence n 2 ((1 + 2-6)/2)br2r, and r 2 lgn + b, - b, lg(1 + 2-6) 2 lg n + lg v(K) -lg(1 + bc,) -b, lg(1 + 2-6). Let 6 = [lg(f + l)]; then ln(1 f 2X6) 5 ln(1 f l/(f + 1)) 5 l/(f + 1) 2 6/(1 + Sf), and it follows that lg(1 + bz) + (f -Z) lg(1 + 2-6) 2 lg(1 + Sf) for 0 2 z 5 f. Hence finally l(n) 2 lgn+lgv(n)-lg(l+(3.271 lgv(n))[lg(l+3.271 lgv(n))]). [Theoretical Comp. Sci. 1 (1975) l-121 29. In the paper just cited, Schonhage refined the method of exercise 28 to prove that l(n) 2 lgn + lgv(n) -2.13 for all n. Can the remaining gap be closed? 30. n = 31 is the smallest example; 1(31) = 7, but 1, 2, 4, 8, 16, 32, 31 is an addition-subtraction chain of length 6. [After proving Theorem E, Erdiis stated that the same result holds also for addition-subtraction chains. Schijnhage has extended the lower bound of exercise 28 to addition-subtraction chains, with v(n) replaced by v(n) = minimum number of nonzero digits to represent n = (nnq . . . ns)a where each nj is -1, 0, or +l. This quantity P(n) is the number of l s, in the ordinary binary representation of n, that are immediately preceded by 0 or by the string OO(lO)kl for some k 2 0.1 32. First compute 2i for 1 2 i 5 x(n,), then compute each n = nj by the following variant of the 2k-ary method: For all odd i < 2k, compute fi = c{ 2kt-te ] dt = 2%) where n = (. . . drds)+, in at most [i lgn] steps; then compute n = c ifi in at most cl(i) + 2k- f ur th er steps. The number of steps per nj is 5 Li lgnj + O(/C~~), and this is x(n)/U(n) + O(x(n)Ux(n)/U(n) ) when k = llg lgn -3 lg lg lg n]. [A generalization of Theorem E gives the corresponding lower bound. Reference: SIAM J. Computing 5 (1976), 100-103. See also exercise 39.1 33. The following construction due to D. J. Newman provides the best upper bound currently known: Let k = pl . . . p7 be the product of the first r primes. Compute k and all quadratic residues mod k by the method of exercise 32, in 0(2- klog k) steps (because there are approximately 2- k quadratic residues). Also compute all multiples of k that are < m2, in about m2/k further steps. Now m additions suffice to compute 12, 22, . . . , m2. We have k = exp(p, + O(p,/(logp,) ooo)) where p7 is given by the formula in exercise 4.5.4-35; so by choosing r = [( 1 + (1 + 4 In 2)/lg lg m) In m/in In ml it follows that 1(12,. . . , m2) = m + O(m . exp(-3 In 2 In m/in In m)). On the other hand, D. Dobkin and R. Lipton have shown that, for any E > 0, 1(12,. . . , m2) > m+m2f3-e when m is sufficiently large [SIAM J. Computing 9 (1980), 121-1251. 35. See Discrete Math. 23 (1978), 115-119. 36. Eight; there are four ways to compute 39 = 12 + 12 + 12 + 3 and two ways to compute 79 = 39 + 39 + 1.