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

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;
}