Horner's rule

Horner's rule is the factorization

of a polynomial. It reduces the computation to n multiplications and n additions.

The rule can be generalized, e.g. to a finite series

orthogonal polynomials p_k=p_k(x). Using the recurrence relation

one obtains

with