4.6.4 EVALUATION OF POLYNOMIALS 475 largest (Web host sites) real part
4.6.4 EVALUATION OF POLYNOMIALS 475 largest real part is real, but the root with second smallest (or second largest) real part is nonreal, the same transformation applies. If the two roots with smallest (or largest) real parts are both real, they can be expressed in the form a -b and a + b, respectively; let c = -a and CY, = b2. Again x2 -QI, is a factor of U(Z -c). (Still other values of c are often possible; see exercise 24.) The coefficient a,-1 will be nonzero for at least one of these alternatives, unless q(x) is identically zero. 1 Note that this method of proof usually gives at least two values of c, and we also have the chance to permute al, . . . , am-i in (m -l)! ways. Some of these alternatives may give more desirable numerical accuracy than others. *Polynomial chains. Now let us consider questions of optimality. What are the best possible schemes for evaluating polynomials of various degrees, in terms of the minimum possible number of arithmetic operations? This question was first analyzed by A. M. Ostrowski in the case that no preliminary adaptation of coefficients is allowed [Studies in Mathematics and Mechanics presented to R. von Mises (New York: Academic Press, 1954) 40-481, and by T. S. Motzkin in the case of adapted coefficients [cf. Bull. Amer. Math. Sot. 61 (955), 1631. In order to investigate this question, we can extend Section 4.6.3 s concept of addition chains to the notion of polynomial chains. A polynomial chain is a sequence of the form where U(X) is some polynomial in x, and for 1 2 i 5 r either Xi = (*Aj) o Xk, 0 I j, k < i, or Xi = ffj 0 Xk, O