A fast scheme for evaluating a polynomial such as:

 



−
19
+
7
x
−
4

x

2


+
6

x

3





{\displaystyle -19+7x-4x^{2}+6x^{3}\,}


when

 



x
=
3



{\displaystyle x=3\;}

.
is to arrange the computation as follows:

 



(
(
(
(
0
)
x
+
6
)
x
+
(
−
4
)
)
x
+
7
)
x
+
(
−
19
)



{\displaystyle ((((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.
Cf. Formal power series

/* Function horner already exists in Maxima, though it operates on expressions, not lists of coefficients */
horner(5*x^3+2*x+1);
x*(5*x^2+2)+1
 
/* Here is an implementation */
horner2(p, x) := block([n, y, i],
   n: length(p),
   y: p[n],
   for i: n - 1 step -1 thru 1 do y: y*x + p[i],
   y
)$
 
horner2([-19, 7, -4, 6], 3);
128
 
/* Another with rreduce */
horner3(p,x):=rreduce(lambda([a,y],x*y+a),p);
horner3([a,b,c,d,e,f],x);
x*(x*(x*(x*(f*x+e)+d)+c)+b)+a
 
/* Extension to compute also derivatives up to a specified order.
   See William Kahan, Roundoff in Polynomial Evaluation, 1986
   http://www.cs.berkeley.edu/~wkahan/Math128/Poly.pdf */
 
poleval(a, x, [m]) := block(
   [n: length(a), v, k: 1],
   if emptyp(m) then m: 1 else m: 1 + first(m),
   v: makelist(0, m),
   v[1]: a[n],
   for i from n - 1 thru 1 step -1 do (
      for j from m thru 2 step -1 do v[j]: v[j] * x + v[j - 1],
      v[1]: v[1] * x + a[i]
   ),
   for i from 2 thru m do (
      v[i]: v[i] * k,
      k: k * i
   ),
   if m = 1 then first(v) else v
)$
 
poleval([0, 0, 0, 0, 1], x, 4);
[x^4, 4 * x^3, 12 * x^2, 24 * x, 24]
 
poleval([0, 0, 0, 0, 1], x);
x^4