On the Number of Multiplications for the Evaluation of a Polynomial and Some of Its Derivatives

ABSTRACT

A family of new algorithms is given for evaluating the first m derivatives of a polynomial. In particular, it is shown that all derivatives may be evaluated in 3n - 2 multiplications. The best previous result required 1/2n(n + 1) multiplications. Some optimality results are presented.

REFERENCES

• 1: BORODIN, A. Horner's rule is uniquely optimal. In Theory of Machines and Computations, Kohavi and Paz, Eds., Academic Press, New York, 1971, pp. 45-58.
• 2: BOROD1N, A. Computational complexity--theory and practice. In Currenls in the Theory o} Computing, A. Aho, Ed., Prentice-Hall, Englewood Cliffs, N. J., 1973, pp. 35-89.
• 3: BORODIN, A. Private communication.
• 4: KIRKP.~TRICK, D. On the additions necessary to compute certain functions. M.Se. Th., Dep. of Computer Sci., U. of Toronto, 1971.
• 5: MUNRO, J. I. Some results in the study of algorithms. Tech. Rep. 32, Dep. of Computer Sci., U. of Toronto, 1971.
• 6: PATERSON, M. S., AND STOCKMEYER, L. Bounds on the evaluation time for rational polynomials. IEEE Conf. Rec., 12th Ann. Symp. on Switching and Automata Theory, 1971, pp. 140-143.
• 7: STEWART, G.W. Error analysis of the algorithm for shifting the zeros of a polynomial by synthetic division. Math. Comp. 25 (1971), 135-139.
• 8: TRAtTB, J. F. Iterative Methods for the Solution of Equations. Prentice-Hall, Englewood Cliffs, N. J., 1964.
• 9: TRAUB, J.F. Associated polynomials and uniform methods for the solution of linear problems. SIAM Rev. 8 (1966), 277-301.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Performance, Theory, Verification