Results 1 to 4 of 4

Math Help - Horner's Method

  1. #1
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    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}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by aaronrj View Post
    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.


    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    n additions?

    Would there also be n additions used to evaluate a polynomial of degree n at x = c? (Not counting additions used to increment the loop variable)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by aaronrj View Post
    Would there also be n additions used to evaluate a polynomial of degree n at x = c? (Not counting additions used to increment the loop variable)
    yes, and one loop increment and test

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: March 6th 2010, 04:40 AM
  2. Polynomial ladders vs Horner's Scheme
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: August 31st 2009, 06:02 AM
  3. Replies: 2
    Last Post: August 17th 2008, 01:02 PM
  4. Replies: 3
    Last Post: November 3rd 2007, 02:43 PM
  5. Replies: 0
    Last Post: January 4th 2007, 02:29 PM

Search Tags


/mathhelpforum @mathhelpforum