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

	$\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
Canonical name	HornersRule
Date of creation	2013-03-22 12:06:17
Last modified on	2013-03-22 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