Analysis of a Family of Algorithms for the Evaluation of a Polynomial and Some of Its Derivatives

We have previously presented a new one parameter family of algorithms and a program for evaluation the first m derivatives of a polynomial of degree n. In this paper we analyze that family of algorithms and present practical algorithms for selecting optimal or good values of the parameter q.

A program for selection the optimal value of q under the constraint that q divides n+1 is given. We also analyze a program that eliminates that constraint and a simple program that selects a good, but not always optimal, value of q. We derive bounds on how close to optimal the "good" value will be.

The above results apply for n >12. We extend the results to all n by tabulating the cost function for n ≤ 12.

Some open questions on extensions of our results are stated.