Horner's rule for polynomial evaluation

Horner's rule for polynomial evaluation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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:
$((6x-4)x+7)x-19\;$
And compute the result from the innermost brackets outwards as:

coefficients = [-19, 7, 4, 6] # list coefficients of all x^0..x^n in order
x = 3
reversedcoeffs = reverse(coefficients)
accumulator = reversedcoeffs[0]
for (i=1; i<length(reversedcoffs); i++){
  accumulator = ( accumulator * x ) + reversedcoeffs[i]
}
# 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.

C.f: Formal power series

Java

Works with: Java version 1.5+

<lang java5>import java.util.ArrayList; import java.util.Collections; import java.util.List;

public class Horner {

   public static void main(String[] args){
       List<Double> coeffs = new ArrayList<Double>();
       coeffs.add(-19.0);
       coeffs.add(7.0);
       coeffs.add(4.0);
       coeffs.add(6.0);
       System.out.println(polyEval(coeffs, 3));
   }

   public static double polyEval(List<Double> coefficients, double x) {
       Collections.reverse(coefficients);
       Double accumulator = coefficients.get(0);
       for (int i = 1; i < coefficients.size(); i++) {
           accumulator = (accumulator * x) + (Double) coefficients.get(i);
       }
       return accumulator;
   }

}</lang> Output:

200.0

Python

<lang python>>>> def horner(coeffs, x): acc = coeffs[-1] for c in reversed(coeffs[:-1]): acc = acc * x + c return acc

>>> horner( (-19, 7, 4, 6), 3) 200</lang>

Functional version

<lang python>>>> def horner(coeffs, x): return reduce(lambda acc, c: acc * x + c, reversed(coeffs))

>>> horner( (-19, 7, 4, 6), 3) 200</lang>