MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

4.6.4 EVALUATION OF POLYNOMIALS 505 62. [M24] The border rank of (&k), denoted by &(t,,k), is mind2srankd(tzjk), where rankd is defined in exercise 61. Prove that the tensor (i Y>(i i> has rank 3 but border rank 2, over every field. 63. [AR?O] Let T(m, n, s) be the tensor for matrix multiplication as in exercise 59. (a) Show that T(m, n, s) @ T(M, N, S) = T(mM,nN, sS). (b) If T(m,n, s) has rank 5 r, show that the number of noncommutative multiplications M(N) for the product of N x N matrices is O(N ( ~ z ~ )) as N + co, where p(m,n, S,T) = 3 logr/logmns. (c) If T(m, n, s) has border rank 5 r, show that we have M(N) = O(N p(mznzs,r)(log N)2). (d) If the tensor pT(m, n, s) obtained by taking the direct sum of p copies of T(m,n, s) has border rank 5 pr, where p < r, show that a similar formula holds. (This tensor corresponds to p independent matrix multiplications.) 64. [M40] (Pan and Winograd.) The purpose of this exercise is to combine the ideas of exercises 60-63, in order to obtain asymptotic bounds on M(N) as N + co. a) Modify the construction of exercise 60(b) to show that T(m, n, s) $ T(s, m, n) has border rank < mns + mn + ns. b) Show that the construction of exercise 60(c) can be altered to prove that the border rank of T(m, n, 2s) $ T(2n, s, m) @ T(s, 2m, n) is at most 2(m + l)n(s + 2) by finding constants oi, o2, . . . , os such that E c (C&j + Udxj, + C7ud+2Xki)(aud-1?J3g + C7UdYkt + yij) i,J,k,o x (ud+l z& + a&j + CTUd-2 &k) l tam QlffX23 + flu d+2 c, ~k,)((Y& + a Ud c, ykz) %,3>0 x (WZ%~ + Ud+l c, ZCJ + cy3 c ((Txi3 + Ud c, X?k)(Yi3 + Oud–l c, Y,,&) 2,3>a x (gzi? + cud- c, s&k) + a4 3Fo (0 xi tj + udX?k)(xi YQ + oud-llJ,L) x (g c, zij + cud- &k) + a5 c (O ci xV + Ud c, X?k)(C, %3 + CTud-l c, !&) jP x (g c, .& + gUd- c, ZJk) + @6 c (c ci %)(C, G> YG)(U c, jr0 (modulo uZdfl ), for sufficiently large d. Here the summations are to be carried out for 1 5-i 5 m, 1 5 j 5 n, 1 5 k 5 s, and o = fl; the subscript Z means ai, so that z takes the 2m values fl, . , +m. c) Use the result of(b) in connection with exercise 63 to show that M(N) = O(Np+ ) for all E > 0, where p = @m, n, 2s, #(m + l)n(s + 2)).

504 ARITHMETIC 4.6.4 a) The first construction is based on the identity abc + ABC = (a + A)(b + B)(c + C) -(a + A)bC -A(b + B)c -aB(c + C). It follows that c xij y2 k zkz = c ( ii + Zi)(?, jk + ?&)(zki + ZjR) -cl -x2 -x3, 1 7711 hand side of the above identity and Ci, CZ, Cs correspond respectively to the next three groups of terms; the remaining terms (namely those corresponding to uBC + ABC + AbC) cancel out of the sum. The set S in this case is different from the S in part (a); it consists of all (i, j, k) E 0 X 0 X 0 such that i 5 j and i < k. It follows from this construction that M(n) 2 $(($)3 -(4)) + 6n2 when n is even. 61. [M23] Let (tijk) be a tensor over an arbitrary field. We define rankd(t,,k) as the minimum value of r such that there is a realization of the form where ail(u), bil(u), cki(U) are polynomials in u over the field. Thus ranks is the ordinary rank of a tensor. Prove that (a) rankd+l(tijk) 5 rankd(tijk); (b) rank(tijk) 2 (d$2)rankd(tt3k); (c) rankd((t%,k) @ (t&)) < rank&&k) + rankd(ti,,), in the sense of exercise 48; (d) rankd+,+jk) @ (t&k)) 2 rank&k) . rank&jk).

4.6.4 EVALUATION OF POLYNOMIALS 503 54. [A-4.%?] Theorem W refers to an infinite field. How many elements must a finite field have in order for the proof of Theorem W to be valid? 55. [HA&??] Determine the rank of tensor (72) when P is an arbitrary n x n matrix. 56. [A&??] (V. Strassen.) Show that any polynomial chain that evaluates a set of quadratic forms c Ili,jln723k~z~k for 1 5 k 2 s must use at least Jrank(r,,k +r]ik) chain multiplications. [Hint: Show that the minimum number of chain multiplications iS the ~iniInU~ rank Of (i&k) taken over all tenSOrS (tzjk) such that tijk + tjik = TtJk + rJZk for all i, j, k.] Use this to prove that any polynomial chain that evaluates a set of bilinear forms (45) corresponding to a tensor (tijk), whether normal or abnormal, must use at least ?jrank(t,,k) chain multiplications. 57. [MZO] Show that fast Fourier transforms can be used to compute the coefficients of the product z(u)y(~) of two given polynomials of degree n, using O(n log n) operations of (exact) addition and multiplication of complex numbers. [Hint: Consider the product of Fourier transforms of the coefficients.] 58. [HA&B] (a) Show that any realization A, B, C of the polynomial multiplication tensor (53) must have the following property: Any nonzero linear combination of the three rows of A must be a vector with at least four nonzero elements; and any nonzero linear combination of the four rows of B must have at least three nonzero elements. (b) Find a realization A, B, C of (53) using only 0, +l, and -1 as elements, where t = 8. Try to use as many O s as possible. b 59. [M40] (H. J. Nussbaumer, 1980.) The text defines the cyclic convolution of two sequences (so, Q, . . . , ~~-1) and (ye, yr, . . . , y,-I) to be the sequence (~0, ~1,. . , ~~-1) where zk = x,,yk + . . + sky0 + Xk+lYn-1 + + xn-lyk+l. Let us define the negacyclic convolution similarly, but with zk = XOyk + . . . + ZkyO -(Xk+lyn-1 + . . . + xn-lyk+l), Construct efficient algorithms for cyclic and negacyclic convolution over the integers when n is a power of 2. Your algorithms should deal entirely with integers, and they should perform at most O(n log n) multiplications and at most O(n log n log log n) additions or subtractions or divisions of even numbers by 2. 60. [M.Z7] (V. I^a. Pan.) The problem of (m X n) times (n X s) matrix multiplication corresponds to an mn X 72s X sm tensor (t(,,j1)(3,k )(k,z )) where t(i,j )(j,k/)(k,$) = 1 if and only i = i and j = j and k = k. The rank of this tensor T(m, n, s) is the Smallest r such that numbers c&j/l, bjk l, ckill exist satisfying Let M(n) be the rank of T(n,n, n). The purpose of this exercise is to exploit the symmetry of such a trilinear representation, obtaining efficient realizations of matrix multiplication over the integers when m = n = s = 2~. For convenience we divide the indices { 1, . . , n} into two subsets 0 = { 1,3, . , n -l} and E = { 2,4, . . , n} of v elements each, and we set up a one-to-one correspondence between 0 and E by the rule Z = i $1 if i E 0; Z = i -1 if i E E. Thus we have i = i for all indices i.

502 ARITHMETIC 4.6.4 45. [AA%] Prove that all pairs (~1,~s) of bilinear forms in ($1, ~2) and (~1, yz) can be evaluated with at most three chain multiplications. In other words, show that every 2 X 2 X 2 tensor has rank 2 3. 46. [M.%] Prove that for all m, n, and s there exists an m X n X s tensor whose rank is at least [mns/(m + n + .s)j. Conversely, show that every m X n X s tensor has rank at most mns/max(m, n, s). 47. [MQ?] Is it possible to determine the rank of any given tensor (tijk) over, say, the field of rational numbers, in a finite number of steps? (There is a finite way to compute the tensor rank over algebraically closed fields like the complex numbers, since this is a special case of the results of Alfred Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd ed. (Berkeley, California: Univ. of California Press, 1951); but the known algorithms do not make this computation really feasible except for very small tensors. Over the field of rational numbers, the problem isn t even known to be solvable in finite time.) 48. [M49] If (&k) and (tijk) are tensors of sizes m X n X s and m X n X s , respectively, their direct sum (tijk)@(t&J = (tGk) is the (m+m ) x (n+n ) X (s+s ) tensor defined by tck = tzjk if i 5 m, j 5 n, k 2 s; t$k = t:–m,j–n,k–s if i > m, j > n, k > s; and tyjk = 0 otherwise. Their direct product (tijk) @ (tlzjk) = (trik) is the mm X nn X SS tensor defined by t(iif)(jj )(kk!) = tijktiljlkt. Derive the upper bounds rank(tyJk) 2 rank(tijk) + rank($,) and rank(t ,i,) 2 rank(tijk) . rank(t&,). b 49. [HA&&Y] Show that the rank of an m X n X 1 tensor (tijk) is the same as its rank as an m X n matrix (tijl), according to the traditional definition of matrix rank as the maximum number of linearly independent rows. 50. [HMZO] (S. Winograd.) Let (tijk) be the mn X n X m tensor corresponding to multiplication of an m X n matrix by an n X 1 column vector. Prove that the rank of (&jk) is mn. b 51. [M.Z4] (S. Winograd.) Devise an algorithm for cyclic convolution of degree 2 that uses 2 multiplications and 4 additions, not counting operations on the 5%. Similarly, devise an algorithm for degree 3, using 4 multiplications and 11 additions. (Cf. (67), which solves the analogous problem for degree 4.) 52. [M25] (S. Winograd.) Let n = n n where gcd(n ,n ) = 1. Given normal schemes for cyclic convolutions of degrees n and n , using respectively (m , m ) chain multiplications, (p , p ) parameter multiplications, and (a , a ) additions, show how to construct a normal scheme for cyclic convolution of degree n using m m chain multiplications, p n + m p parameter multiplications, and a n + m a additions. @. [HM40] (S. Winograd.) Let w be a complex mth root of unity, and consider the one-dimensional discrete Fourier transform for s 5 f(s)= c wwst, 1 5 m. (a) When m = pe is a power of an odd prime, show that efficient normal schemes for computing cyclic convolutions of degrees (p-l)pk, for 0 5 k < e, will lead to efficient algorithms for computing the Fourier transform on m complex numbers. Give a similar construction for the case p = 2. (b) When m = m m and gcd(m , m ) = 1, show that Fourier transformation algorithms for m and m can be combined to yield a Fourier transformation algorithm for m elements.

4.6.4 EVALUATION OF POLYNOMIALS 501 b 38. [HiK%] (V. I^a. Pan, 1962.) The purpose of this exercise is to prove that Horner s rule is really optimal if no preliminary adaptation of coefficients is made; we need n multiplications and n additions to compute unxn + . . . + ~1 x + 1~0, if the variables ZL~, , ~1, ~0, 2, and arbitrary constants are given. Consider chains that are as before except that un, . . . , ~1, ~0, x are each considered to be variables; we may say, for example, that X-j-1 = uj, X0 = x. In order to show that Horner s rule is best, it is convenient to prove a somewhat more general theorem: Let A = (aij), 0 2 i 5 m, 0 5 j 5 n, be an (m f 1) X (n $ 1) matrix of real numbers, of rank n + 1; and let B = (bo, . , b,) be a vector of real numbers. Prove that any polynomial chain that computes P(x; uo, . . , u,) = C( azouo + . . . + ainun + b,)xi O

500 ARITHMETIC 4.6.4 b 29. [M.ZO] Let RI, Rz, . , R, all be sets of (n + 1)-tuples of real numbers having at most t degrees of freedom. Show that the union RI U RZ U . . . U R, also has at most t degrees of freedom. b 30. [MB?] Prove that a polynomial chain with m, chain multiplications and mp parameter multiplications has at most 2m, + rnr + 60,~ degrees of freedom. [Hint: Generalize Theorem M, showing that the first chain multiplication and each parameter multiplication can essentially introduce only one new parameter into the result set.] 31. [ME?] Prove that a polynomial chain capable of computing all manic polynomials of degree n has at least [n/2] multiplications and at least n addition-subtractions. 32. [M.Z4] Find a polynomial chain of minimum possible length that can compute all polynomials of the form 1~4~~ + U& + us; and prove that its length is minimal. b 33. [M,%] Let n 2 3 be odd. Prove that a polynomial chain with [n/2] + 1 multiplication steps cannot compute all polynomials of degree n unless it has at least n + 2 addition-subtraction steps. [Hint: See exercise 30.1 34. [M%] Let X0, XI, . . . , X, be a polynomial chain in which all of the addition and subtraction steps are parameter steps, and in which there is at least one param- eter multiplication. Assume that this scheme has m multiplications and k = r -m addition-subtractions, and that the polynomial computed by the chain has maximum degree n. Prove that all polynomials computable by this chain, for which the coefficient of x is not zero, can be computed by another chain that has at most m multiplications and at most k additions, and no subtractions; and whose last step is the only parameter multiplication. b 35. [MB] Show that any polynomial chain that computes a general fourth-degree polynomial using three multiplications must have at least five addition-subtractions. [Hint: Assume that there are only four addition-subtractions, and show that exercise 34 applies; this means the scheme must have a particular form that is incapable of representing all fourth-degree polynomials.] 36. [Mw] Show that any polynomial chain that computes a general sixth-degree poly- nomial using only four multiplications must have at least seven addition-subtractions. (Cf. exercise 35.) 37. [MB] (T. S. Motzkin.) Show that almost all rational functions of the form (U,xn + 7Ln–15n–1 + … + 2112 + uo)/(x” + v,-lxn-l +. ..+ ‘UlZ + vo), with coefficients in a field S, can be evaluated using the scheme a1 + W(x + a2 + + . . . + /A/(x + an+1). . . )), @z/(x for suitable oj, /3? in S. (This continued fraction scheme has n divisions and 2n additions; by almost all rational functions we mean all except those whose coeffi- cients satisfy some nontrivial polynomial equation.) Determine the (Y S and p s for the rational function (x2 + 1Oa: + 29)/(x2 + 8x + 19).

4.6.4 EVALUATION OF POLYNOMIALS 499 23. [HM30] (J. Eve.) Let f(z) = a,zn + an-lzn- + … + a0 be a polynomial of degree n with real coefficients, having at least n -1 roots with a nonnegative real part. Let g(z) = a,zn + un-2Zn–2 + . . + hm0dzZ nmod2 7 h(z) = a,-lz–l + &-3zn-3 + f ~(,-l)~~d2Z(n-1)mod2. Assume that h(z) is not identically zero. a) Show that g(z) has at least n -2 imaginary roots (i.e., roots whose real part is zero), and h(z) has at least n -3 imaginary roots. [Hint: Consider the number of times the path f(z) circles the origin as z goes around the path shown in Fig. 15, for a sufficiently large radius R.] b) Prove that the squares of the roots of g(z) = 0 and h(z) = 0 are all real. - R Fig. 15. Proof of Eve s theorem. b 24. [h .Z4] Find values of c and &k, Pk satisfying the conditions of Theorem E, for the polynomial U(Z) = (Z + 7)(x* + 6~ + 10)(~ $4~ j-5)(2 + 1). Choose these values so that PZ = 0. Give two different solutions to this problem! 25. [M.Z0] When the construction in the proof of Theorem M is applied to the (ineffi- cient) polynomial chain Xl = 0.1 +x0, x2 = —x0 -x0, x3 = Xl + Xl, x4 = a2 x X3, x5 = x0 –x0, X6 = cl6 -x5, x7 = ff7 +x63, X8 = x7 x X7, x9 = Xl x x4, x10 = Q8 -x9, 111 = x3 -x10, how can PI, fiz, . . . , /3s be expressed in terms of CQ, , cvs? b 26. [M.21] (a) Give the polynomial chain corresponding to Horner s rule for evaluating polynomials of degree n = 3. (b) Using the construction that appears in the text s proof of Theorem A, express ~1, ~2, 1c3, and the result polynomial U(X) in terms of ,&, Pz, ps, p4, and 5. (c) Show that the result set obtained in (b), as PI, &, /33, and p4 independently assume all real values, omits certain vectors in the result set of (a). 27. [Mz?] Let R be a set that inciudes all (n+l)-tuples (q,, . . , ~,qo) of real numbers such that qn # 0; prove that R dpes not have at most n degrees of freedom. 28. [HMz?~] Show that if fo(crl,. . , as), . . . , fs(o~, . . , cu,) are multivariate polyno- mials with integer coefficients, then there is a nonzero polynomial g(zo, . . , z~) with integer coefficients such that g(f ( . , fs(crl,. = all real al, 0 CXI, , as), . . , as)) 0 for . ..) as. (Hence any polynomial chain with s parameters has at most s degrees of freedom.) [Hint: Use the theorems about algebraic dependence that are found, for example, in B. L. van der Waerden s Modern Algebra, tr. by Fred Blum (New York: Ungar, 1949), Section 64.1

498 ARITHMETIC 4.6.4 b 15. [HA4.28] The nth divided difference f(zs, ~1,. . , z~) of a function f(r) at n + 1 distinct points ~0, x1, . , 5% is defined by the formula f(50,21,…,2n)=(f( ~0,~1,…,Z~-1)-f(Z1,…,271–1,21L))/(Z0 -Zn), for n > 0. Thus f(zo, 21,. . ,G) = COCkCn f(%)/ no,,I,,j+&k -23) is a - symmetric function of its n + 1 arguments. (a) Prove that f(zo, . , G) = f (e)/n!, for some 0 between min(zo, , CC,) and max(zo, , G), if the nth derivative f( )(z) exists and is continuous. [Hint: Prove the identity &it1 lit,. . .~nit,l (xo(l-tl) + xl(tl–t2) + . . . f(xo,51,…,xn)= +~n-l(tn-l-tn) + zn(tn-0)). This formula also defines f(zo, ~1,. , z,) in a useful manner when the x3 are not distinct.] (b) If yj = f(xj), show that oj = f(xo, . . . , xj) in Newton s interpolation polynomial (42). 16. [AL%?] How can we readily compute the coefficients of ul ](x) = u,xn +. + ~0, if we are given the values of x0, xl, . . . , ~~-1, CQ, al, . . . , on in Newton s interpolation polynomial (42)? 17. [M45] Is there a way to evaluate the polynomial c 22×3+.. . + xn-lxn = x152 llz<3ln with fewer than n -1 multiplications and 2n -4 additions? (There are (y) terms.) 18. [A&V] If the fourth-degree scheme (9) were changed to Y = (x + ao)x + Ql, 4x) = ((Y -x + m)y + cy3)Ly4, what formulas for computing the q s in terms of the @ s would take the place of (lo)? b 19. [M24] Explain how to determine the adapted coefficients oo, ol, , cy5 in (11) from the coefficients ~5, , ZL~, uo of u(z), and find the o s for the particular polynomial u(z) = x5 + 5×4 -10×3 -50×2 + 13x + 60. b 20. [ZY] Write a MIX program that evaluates a fifth-degree polynomial according to scheme (11); try to make the program as efficient as possible, by making slight modifications to (11). Use MIX s floating point arithmetic operators FADD and FMUL, which are described in Section 4.2.1. 21. [Zoo] Find two additional ways to evaluate the polynomial x6 + 13~~ + 49×4 + 33×3 -61×2 -37x $ 3 by scheme (12) using the two roots of (15) that were not considered in the text. 22. [IL?] What is the scheme for evaluating x6 -3×5 +x4 -2×3 + z2 -32 -1, using Pan s method (16)?

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.

496 ARITHMETIC 4.6.4 One of the most important corollaries of Theorem W is that the rank of a tensor can depend on the field from which we draw the elements of the realization A, B, C. For example, consider the tensor corresponding to cyclic convolution of degree 5; this is equivalent to multiplication of polynomials mod P(U) = u5 -1. Over the field of rational numbers, the complete factorization of p(u) is (u -1) X (u + u3 + u2 + u + 1) by exercise 4.6.2-32, so the tensor rank is 10 -2 = 8. On the other hand, the complete factorization over the real numbers, in terms of the number 4 = &(l + fi), is (U -1)(u2 + #u + 1)(u2 -4-l~ + 1); thus, the rank is only 7, if we allow arbitrary real numbers to appear in A, El, C. Over the complex numbers the rank is 5. This phenomenon does not occur in two-dimensional tensors (i.e., matrices), where the rank can be determined by evaluating determinants of submatrices and testing for 0. The rank of a matrix does not change when the field containing its elements is embedded in a larger field, but the rank of a tensor can decrease when the field gets larger. In the paper that introduced Theorem W [Math. Systems Theory 10 (1977), 169-1801, Winograd went on to show that all realizations of (69) in 2n -q chain multiplications correspond to the use of (57), when q is greater than 1. Furthermore he has shown that the only way to evaluate the coefficients of z(u)y(zl) in deg(z) + deg(y) + 1 chain multiplications is to use interpolation or to use (56) with a polynomial that splits into distinct linear factors in the field. Finally he has proved that the only way to evaluate Z(U)Y(U) mod p(u) in 2n -1 chain multiplications when q = 1 is essentially to use (58). These results hold for all polynomial chains, not only normal ones. He has extended the results to multivariate polynomials in Sm J. Computing 9 (1980), 225-229. The tensor rank of an arbitrary m X n X 2 tensor in a suitably large field has been determined by Joseph Ja Ja , SIAM J. Computing 8 (1979), 443-462. For further reading. In this section we have barely scratched the surface of a very large subject in which many beautiful theories are emerging; a considerably more comprehensive treatment appears in the book Computational Complexity of Mgebraic and Numeric Problems by A. Borodin and I. Munro (New York: American Elsevier, 1975). EXERCISES 1. [IS] What is a good way to evaluate an odd polynomial Znfl 2n-1 + . . . + lL1x? u(x) = U2n+12 + 112n-12 b 2. [A4,%?] Instead of computing U(Z + ~0) by steps Hl and H2 as in the text, discuss the application of Horner s rule (2) when polynomial multiplication and addition are used instead of arithmetic in the domain of coefficients. 3. [.%?I Give a method analogous to Horner s rule, for evaluating a polynomial in two variables c,+jS, uijx yj. (This polynomial has (n + l)(n f 2)/2 coefficients, and total degree n.) Count the number of additions and multiplications you use.