Horner’s rule

Horner’s rule is a technique to reduce the work required for the computation of a polynomialMathworldPlanetmathPlanetmath at a particular value. Its simplest form makes use of the repeated factorizations

y = a0+a1x+a2x2++anxn
= a0+x(a1+x(a2+x(a3++xan)))

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

The rule can be generalized to a finite series


of orthogonal polynomials pk=pk(x). Using the recurrence relation


for orthogonal polynomials, one obtains



bn+1 = bn+2=0,
bk-1 = (Ak+Bka)bk+Ck+1+bk+1+ak-1

for the evaluation of y at some particular a. This is a simpler calculation than the straightforward approach, since a0 and C2 are known, p0(a) and p1(a) are easy to compute (possibly themselves by Horner’s rule), and b1 and b2 are given by a backwards-recurrence which is linear in n.


  • 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 AlgorithmMathworldPlanetmath
Classification msc 68W01
Classification msc 13P05
Classification msc 65Y99