A fast scheme for evaluating a polynomial such as:

when

- .

is to arrange the computation as follows:

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*

**Task Description**

- 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.

*Related*