Horner’s Method for Polynomial Evaluation

Overview

Horner's method, also known as Horner's scheme or Horner's rule, is an algorithm used for efficiently evaluating polynomials. It allows for the calculation of polynomial values by reducing the number of required multiplications and additions compared to the standard polynomial evaluation method.

In Horner's method, a polynomial is expressed in the form:

$$P(x) = a₀ + a₁x + a₂x² + a₃x³ + ... + aₙxⁿ$$

where a₀, a₁, a₂, ..., aₙ are the coefficients of the polynomial, and x is the value at which the polynomial is to be evaluated.

The algorithm works by repeatedly factoring out the x term and simplifying the expression:

$$P(x) = a₀ + x(a₁ + x(a₂ + x(a₃ + ... + x(aₙ-1 + xaₙ)...))).$$

We can understand it by a simple example

$$f(x) = 7x^4 + 2x^3 – 5x^2 + 4x − 3$$

By applying Horner's method we get

$$f(x)= (((7x + 2)x − 5)x + 4)x − 3)$$

Explanation:

$$= 7x^4 + 2x^3 – 5x^2 + 4x − 3 $$

$$=((7x^3 + 2x^2 – 5x + 4)x − 3) $$

$$=(((7x^2 + 2x – 5)x + 4)x − 3)$$

$$= (((7x + 2)x − 5)x + 4)x − 3)$$

Code of Horners Method

#include<bits/stdc++.h>
using namespace std;

//here the function will return value of poly[0]x(n-1) + poly[1]x(n-2) + .. + poly[n-1]
int horner(vector<int>poly,int x){
    int value = poly[0];
    int len = poly.size();
    for(int i=1;i<len;i++){
        value = value * x +poly[i];
    }
    return value;
}
int main()
{
  //let us evaluate the value for f(x) = 7x^4 + 2x^3 – 5x^2 + 4x − 3 
    vector<int>poly = {7,2,-5,4,-3};
    int x;
    cin>>x;
    cout<<"Result for polynomial is (for x = "<<x<<") : "<<horner(poly,x)<<endl;
    return 0;
}