# channelflow.org

### Site Tools

gibson:teaching:fall-2016:math753:horner

# Horner's method for polynomial evaluation

#### Horner's method without base points

Horner's method is a simple trick that reduces the number of operations needed to evaluate a polynomial. For example, the 4th order polynomial

would require 4 adds and 10 multiplies, if it were evaulated as written. But if we rewrite as

evaluation only requires 4 adds and 4 multiplies. It's easy to see that these are just two different ways of writing the exact same polynomial. The approach generalizes to arbitrary-order polynomials, and the payoff gets bigger as the order of the polynomial increases.

#### Horner's method with base points

It's sometime convenient to introduce base points to Horner's method. That is, we write a polynomial in this form

The above polynomial is still 4th order, and it is clearly possible to write any polynomial in a form like this for arbitrary 's. The base points require an additional set of subtractions, but it's often worth the trouble, primarily because this is the most natural form for polynomial interpolation via Newton's Divided Differences.