Efficient evaluation of polynomial forms

摘要

The evaluation of several polynomial forms is considered. New algorithms for the evaluation of a polynomial and its derivative, a polynomial at two points, a polynomial of high degree using multiple precision arithmetic, and a bivariate polynomial of the form Σa(i) xiyn−i are presented. Various “coefficient splitting techniques” are introduced in these algorithms and the optimality of certain techniques is shown.