XP Math - Forums - View Single Post - Hornerâ€™s method
 Thread: Hornerâ€™s method View Single Post
03-24-2007   #15
Temperal
Guest

Posts: n/a

Quote:
 Originally Posted by hyderman 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.