Polynomial Evaluation using Horner’s Method

Let suppose we have an n-degree polynomial expression

F(x) = cn.xn + cn-1.xn-1 + cn-2.xn-2 + . . . + c1.x + c0

Here cn, cn-1, cn-2, … c0 are integral coefficients.

Now we need to evaluate the polynomial for some given value x. A naive approach for solving would take O(n2) complexity, which costs lots of time in solving this kind of problem.

We can use Horner’s method to solve this in an efficient way. For solving this problem using Horner’s method, the given equation can be written in a form of nested multiplication as

F(x) = ((...(((cn*x + cn-1)*x + cn-2)*x + cn-3)*x + . . . )*x + c0

Ex: Let we have a polynomial f(x) = 6.x3 – 3.x2 + 2.x + 1
We shall evaluate this polynomial for x = 4 using Horner’s Method.
The expression would be (((6*4 -3)*4 + 2)*4 + 1 = 345
Solving it directly, 6*(43) – 3*(42) + 2*(4) + 1 = 345

Horner’s Method implementation in C++

#include <iostream>

using namespace std;

int horner(int n,int c[],int x)
{
    int ans = c[0];
    int i = 0;
    while(i < n)
    {
        ans = ans*x + c[i+1];
        i++;
    }
    return ans;     /*returns evaluated value of polynomial with x*/
}

int main()
{
    int n;          /*degree or order of polynomial*/
    cout<<"Enter degree of polynomial : "; 
    cin>>n;
    int c[n+1];     /*this contains coefficients of the polynomial*/
    int i = 0;
    cout<<"Enter n+1 coefficients of polynomial : ";
    while(i <= n)
    {
        cin>>c[i];
        i++;
    }
    int x;          /*value with which polynomial should be evaluated*/
    cout<<"Enter value of x : "; 
    cin>>x;
    cout<<"\nEvaluated value of x in polynomial is : ";
    cout<<horner(n,c,x)<<endl;
    return 0;
}

Output :

Enter degree of polynomial : 3
Enter n+1 coefficients of polynomial : 6 -3 2 1
Enter value of x : 4

Evaluated value of x in polynomial is : 345

Complexity of evaluation of polynomial is now reduced to O(n). We can see the considerable amount of change in efficiency by using Horner’s Method for this problem.

Problems : POLEVAL(SPOJ)