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 orderx:=3 accumulator:=0foriinlength(coefficients)downto1do# Assumes 1-based indexing for arraysaccumulator:=( 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; }

Content is available under GNU Free Documentation License 1.2.