====== 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

\begin{equation*}
P(x) = c_0 + c_1 x + c_2 x^2 + c_3 x^3 + c_4 x^4
\end{equation*}

would require 4 adds and 10 multiplies, if it were evaulated as written. But if we rewrite $P(x)$ as 

\begin{equation*}
P(x) = c_0 + x \, [c_1 + x \, [c_2 + x \, [c_3 + x \, c_4]]]
\end{equation*}

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

\begin{equation*}
P(x) = c_0 + (x - b_0) \, [c_1 + (x - b_1) [c_2 + (x - b_2) [c_3 + (x - b_3) \, c_4]]]
\end{equation*}

The above polynomial is still 4th order, and it is clearly possible to write any polynomial in a form like this for arbitrary $b$'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 [[gibson:teaching:fall-2016:math753:newtondivdiff|Newton's Divided Differences]].

Further reading:

  * [[https://en.wikipedia.org/wiki/Horner%27s_method | Horner's method]] (wikipedia). 

Strangely, there aren't many good online resources for Horner's method. Perhaps it's too simple. so