# Horner's Method

• Oct 6th 2008, 06:26 PM
aaronrj
Horner's Method
I'm attempting to evaluate 3x^2 + x + 1 at x = 2. Also, how many multiplications are used by this algorithm to evaluate a polynomial of degree n at x = c?

procedure Horner(c, a0, a1, a2, ... , an : real numbers)
y:= an
for i := 1 to n
y := y * c + a (n-i)
{y = an c^n + a(n-1) c^n-1 + ... + a1c + a0}
• Oct 7th 2008, 12:06 AM
CaptainBlack
Quote:

Originally Posted by aaronrj
I'm attempting to evaluate 3x^2 + x + 1 at x = 2.

c=2
a0=1, a1=1, a2=3

put y=a3=3

first trip
y=c*y+a1=7

second trip
y=c*y+a0=2*7+1=15

Done.

Quote:

Also, how many multiplications are used by this algorithm to evaluate a polynomial of degree n at x = c?

procedure Horner(c, a0, a1, a2, ... , an : real numbers)
y:= an
for i := 1 to n
y := y * c + a (n-i)
{y = an c^n + a(n-1) c^n-1 + ... + a1c + a0}
There is 1 multiplication per trip around the loop, and the final trip count is n, so there are n multiplications.

RonL
• Oct 7th 2008, 09:08 AM
aaronrj