Generalizations of Horner's Rule for Polynomial Evaluation

Polynomials are generally evaluated by use of Horner's rule, sometimes referred to as the nesting rule. This rule is sequential and affords no opportunity for parallel computation, i.e., completion of several of the arithmetic operations simultaneously. Two generalizations of Horner's rule which allow for parallel computation are presented here. Schedules and, in some cases, machine codes for evaluating a polynomial on a computer with several parallel arithmetic units are developed. Some advantages of the generalized rules in sequential computations on a computer with a single arithmetic unit are presented.