PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
create new user
forget your password?
Main Menu
Horner's rule (Algorithm)

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

$\displaystyle 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

$\displaystyle p_k = (A_k + B_k x) p_{k-1} + C_k p_{k-2} $

for orthogonal polynomials, one obtains

$\displaystyle y(a) = (a_0 + C_2 b_2) p_0(a) + b_1 p_1(a) $


$\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$.


"Horner's rule" is owned by akrowne.
(view preamble)

View style:

Cross-references: recurrence relation, orthogonal polynomials, series, finite, additions, multiplications, order, degree, terms, polynomial
There is 1 reference to this entry.

This is version 7 of Horner's rule, born on 2002-01-04, modified 2002-07-12.
Object id is 1219, canonical name is HornersRule.
Accessed 6729 times total.

AMS MSC68W01 (Computer science :: Algorithms :: General)
 13P05 (Commutative rings and algebras :: Computational aspects of commutative algebra :: Polynomials, factorization)
 65Y99 (Numerical analysis :: Computer aspects of numerical algorithms :: Miscellaneous)

Pending Errata and Addenda
[ View all 2 ]
Style: Expand: Order:
forum policy

No messages.

rate | post | correct | update request | add example | add (any)