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:

$(((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
reversedcoeffs := reverse coefficients
accumulator := reversedcoeffs[0]
for i in 1 to length(reversedcoffs) do
    accumulator := ( accumulator * x ) + reversedcoeffs[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.

C.f: Formal power series

Fortran

Works with: Fortran version 90 and later

<lang fortran>program test_horner

 implicit none

 write (*, '(f5.1)') horner ((/-19.0, 7.0, -4.0, 6.0/), 3.0)

contains

 function horner (coeffs, x) result (res)

   implicit none
   real, dimension (:), intent (in) :: coeffs
   real, intent (in) :: x
   real :: res
   integer :: i

   res = 0.0
   do i = size (coeffs), 1, -1
     res = res * x + coeffs (i)
   end do

 end function horner

end program test_horner</lang> Output: <lang>128.0</lang>

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:

128.0

Oz

<lang oz>declare

 fun {Horner Coeffs X}
    {FoldL1 {Reverse Coeffs} 
     fun {$ Acc Coeff}
        Acc*X + Coeff
     end}
 end
 
 fun {FoldL1 X|Xr Fun}
    {FoldL Xr Fun X}
 end

in

 {Show {Horner [~19 7 ~4 6] 3}}</lang>

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) 128</lang>

Functional version

<lang python>>>> try: from functools import reduce except: pass

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

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

Scheme

Works with: Scheme version R$^{5}$RS

<lang scheme>(define (horner lst x)

 (define (*horner lst x acc)
   (if (null? lst)
       acc
       (*horner (cdr lst) x (+ (* acc x) (car lst)))))
 (*horner (reverse lst) x 0))

(display (horner (list -19 7 -4 6) 3)) (newline)</lang> Output: <lang>128</lang>

Tcl

<lang tcl>package require Tcl 8.5 proc horner {coeffs x} {

   set y 0
   foreach c [lreverse $coeffs] {
       set y [expr { $y*$x+$c }]
   }
   return $y

}</lang> Demonstrating: <lang tcl>puts [horner {-19 7 -4 6} 3]</lang> Output:

128