# Horner’s rule

 $\displaystyle y$ $\displaystyle=$ $\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{n}x^{n}$ $\displaystyle=$ $\displaystyle a_{0}+x(a_{1}+x(a_{2}+x(a_{3}+\cdots+xa_{n}))\cdots)$

of the terms of the $n$th degree polynomial in $x$ in order to reduce the computation of the polynomial $y(a)$ (at some value $x=a$) to $n$ multiplications  and $n$ additions.

The rule can be generalized to a finite series

 $y=a_{0}p_{0}+a_{1}p_{1}+\cdots+a_{n}p_{n}$

of orthogonal polynomials $p_{k}=p_{k}(x)$. Using the recurrence relation

 $p_{k}=(A_{k}+B_{k}x)p_{k-1}+C_{k}p_{k-2}$

for orthogonal polynomials, one obtains

 $y(a)=(a_{0}+C_{2}b_{2})p_{0}(a)+b_{1}p_{1}(a)$

with

 $\displaystyle b_{n+1}$ $\displaystyle=$ $\displaystyle b_{n+2}=0,$ $\displaystyle b_{k-1}$ $\displaystyle=$ $\displaystyle(A_{k}+B_{k}\cdot a)b_{k}+C_{k+1}+b_{k+1}+a_{k-1}$

for the evaluation of $y$ at some particular $a$. This is a simpler calculation than the straightforward approach, since $a_{0}$ and $C_{2}$ are known, $p_{0}(a)$ and $p_{1}(a)$ are easy to compute (possibly themselves by Horner’s rule), and $b_{1}$ and $b_{2}$ are given by a backwards-recurrence which is linear in $n$.

References

• Originally from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)

Title Horner’s rule HornersRule 2013-03-22 12:06:17 2013-03-22 12:06:17 akrowne (2) akrowne (2) 11 akrowne (2) Algorithm  msc 68W01 msc 13P05 msc 65Y99