Horner’s rule
Horner’s rule is a technique to reduce the work required for the computation of a polynomial^{} at a particular value. Its simplest form makes use of the repeated factorizations
$y$  $=$  ${a}_{0}+{a}_{1}x+{a}_{2}{x}^{2}+\mathrm{\cdots}+{a}_{n}{x}^{n}$  
$=$  ${a}_{0}+x({a}_{1}+x({a}_{2}+x({a}_{3}+\mathrm{\cdots}+x{a}_{n}))\mathrm{\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}+\mathrm{\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}_{k1}+{C}_{k}{p}_{k2}$$ 
for orthogonal polynomials, one obtains
$$y(a)=({a}_{0}+{C}_{2}{b}_{2}){p}_{0}(a)+{b}_{1}{p}_{1}(a)$$ 
with
${b}_{n+1}$  $=$  ${b}_{n+2}=0,$  
${b}_{k1}$  $=$  $({A}_{k}+{B}_{k}\cdot a){b}_{k}+{C}_{k+1}+{b}_{k+1}+{a}_{k1}$ 
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 backwardsrecurrence 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 

Canonical name  HornersRule 
Date of creation  20130322 12:06:17 
Last modified on  20130322 12:06:17 
Owner  akrowne (2) 
Last modified by  akrowne (2) 
Numerical id  11 
Author  akrowne (2) 
Entry type  Algorithm^{} 
Classification  msc 68W01 
Classification  msc 13P05 
Classification  msc 65Y99 