Quantcast XP Math - Forums - View Single Post - Horner’s method
View Single Post
Old 03-24-2007   #15
Temperal
Guest
 
Posts: n/a
Default

Quote:
Originally Posted by hyderman View Post
here you go guys look how easy

--------------------------------------------------------------------------------

The Horner’s method is an algorithm that evaluates polynomials. The following pseudocode shows how to use this method to find the
value of a_nx^n + a_{n-1}x^{n-1} + . . . + a_1x + a_0 at x = c.
procedure Horner(c, a_0, a_1, a_2, . . . , a_n : real numbers)
y := a_n
for i := 1 to n
y := y * c + a_{n-i}
end {y = a_nc^n + a_{n-1}c^{n-1} + . . . + a_1c + a_0}

(a) Evaluate x^2 + 5x + 3 at x = 2 by working through each step of the algorithm.

y:=1 [since n=2 and a_2=1]
i:=1 [first time the loop runs]
y:=y*2+5 =1*2+5=2+5=7 [since c=2 and a_1=5]
i:=2 [second time the loop runs]
y:=y*2+3=7*2+3=14+3=17 [since c=2 and a_0=3]
end [loop runs n=2 times only]

Indeed, 2^2+5*2+3=4+10+3=17 !

(b) Exactly how many multiplications and additions are used by this algorithm to evaluate a polynomial of degree n at x = c? (Do not count additions used to increment the loop variable.)

Each time the loop repeats it performs 1 multiplication [y*c] and 1 addition [adds a_{n-i} to it]. Loop repeats n times [i goes from 1 to n] so this algorithm performs n multiplications and n additions !

The crazy thing is, I actually almost understood part of that.