Analysis of a Family of Algorithms for the Evaluation of a Polynomial and Some of Its Derivatives,
Abstract
The authors have previously presented a new one parameter family of algorithms and a program for evaluating the first m derivatives of a polynomial of degree n. In this paper the authors analyze that family of algorithms and present practical algorithms for selecting optimal or good values of the parameter q. A program for selecting the optimal value of q under the constraint at q divides n+l is given. The authors also analyze a program that eliminates that constraint and a simple program that selects a good, but not always optimal, value of q. Bounds are derived on how close to optimal the 'good' value will be. The above results apply for n > 12. The authors extend the results to all n by tabulating the cost function for n < or = 12.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 26, 1975
- Accession Number
- ADA009250
Entities
People
- J. F. Traub
- Mary Shaw
Organizations
- Carnegie Institute of Technology