Horner's Method for Polynomial Evaluation | GeeksforGeeks

Horner's Method for Polynomial Evaluation | GeeksforGeeks
Given a polynomial of the form c_nxⁿ + c_n-1x^n-1 + c_n-2x^n-2 + … + c₁x + c₀ and a value of x, find the value of polynomial for a given value of x. Here c_n, c_n-1, .. are integers (may be negative) and n is a positive integer.

Horner’s method can be used to evaluate polynomial in O(n) time. To understand the method, let us consider the example of 2x3 – 6x2 + 2x – 1. The polynomial can be evaluated as ((2x – 6)x + 2)x – 1. The idea is to initialize result as coefficient of xn which is 2 in this case, repeatedly multiply result with x and add next coefficient to result. Finally return result.

// returns value of poly[0]x(n-1) + poly[1]x(n-2) + .. + poly[n-1]

int horner(int poly[], int n, int x)

{

    int result = poly[0];  // Initialize result

    // Evaluate value of polynomial using Horner's method

    for (int i=1; i<n; i++)

        result = result*x + poly[i];

    return result;

}

http://www.math10.com/en/algebra/horner.html

f(x₀) = a₀ + a₁x₀ + a₂x₀² + ... + a_nx₀ⁿ

This can, also, be written as:

f(x₀) = a₀ + x₀(a₁ + x₀(a₂ + x₀(a₃ + ... + (a_n-1 + a_nx₀)....)

f(x) = a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴ + a₅x⁵

which can be evaluated at x = x₀ by re-arranging it as:

f(x₀) = a₀ + x₀(a₁ + x₀(a₂ + x₀(a₃ + x₀(a₄ + a₅x₀))))

http://n1b-algo.blogspot.com/2010/02/polynomial-evaluation.html


Read full article from Horner's Method for Polynomial Evaluation | GeeksforGeeks