# C++: Horner’s Rule for Polynomial Evaluation

A fast scheme for evaluating a polynomial such as:

$-19+7x-4x^2+6x^3\,$

when

$x=3\;$.

is to arrange the computation as follows:

$((((0) x + 6) x + (-4)) x + 7) x + (-19)\;$

And compute the result from the innermost brackets outwards as in this pseudocode:

coefficients := [-19, 7, -4, 6] # list coefficients of all x^0..x^n in order
x := 3
accumulator := 0
for i in length(coefficients) downto 1 do
# Assumes 1-based indexing for arrays
accumulator := ( accumulator * x ) + coefficients[i]
done
# accumulator now has the answer

Create a routine that takes a list of coefficients of a polynomial in order of increasing powers of x; together with a value of x to compute its value at, and return the value of the polynomial at that value using Horner’s rule.

#include <iostream>
#include <vector>

using namespace std;

double horner(vector<double> v, double x)
{
double s = 0;

for( vector<double>::const_reverse_iterator i = v.rbegin(); i != v.rend(); i++ )
s = s*x + *i;
return s;
}

int main()
{
double c[] = { -19, 7, -4, 6 };
vector<double> v(c, c + sizeof(c)/sizeof(double));
cout << horner(v, 3.0) << endl;
return 0;
}

Yet another solution, which is more idiomatic in C++ and works on any bidirectional sequence:

#include <iostream>

template<typename BidirIter>
double horner(BidirIter begin, BidirIter end, double x)
{
double result = 0;
while (end != begin)
result = result*x + *--end;
return result;
}

int main()
{
double c[] = { -19, 7, -4, 6 };
std::cout << horner(c, c + 4, 3) << std::endl;
}

SOURCE

Content is available under GNU Free Documentation License 1.2.