Horner's rule for polynomial evaluation

Horner's rule for polynomial evaluation
You are encouraged to solve this task according to the task description, using any language you may know.

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.

C.f: Formal power series

Ada

<lang Ada> with Ada.Float_Text_IO; use Ada.Float_Text_IO; procedure horners_rule is type Coef is array(Positive range <>) of Float; coefficients : Coef := (-19.0,7.0,-4.0,6.0); x : Float := 3.0;

function horner(coeffs: Coef; val: Float) return Float is res : Float := 0.0; begin for p in reverse coeffs'Range loop res := res*val + coeffs(p); end loop; return res; end horner;

begin put(horner(coefficients,x),Aft=>1,Exp=>0); end horners_rule; </lang> Output:

128.0

ALGOL 68

Works with: ALGOL 68G

<lang algol68>PROC horner = ([]REAL c, REAL x)REAL : (

 REAL res := 0.0;
 FOR i FROM UPB c BY -1 TO LWB c DO
   res := res * x + c[i]
 OD;
 res

);

main:(

 [4]REAL coeffs := (-19.0, 7.0, -4.0, 6.0);
 print( horner(coeffs, 3.0) )

)</lang>

AutoHotkey

<lang autohotkey>Coefficients = -19, 7, -4, 6 x := 3

MsgBox, % EvalPolynom(Coefficients, x)

---------------------------------------------------------------------------

EvalPolynom(Coefficients, x) { ; using Horner's rule

---------------------------------------------------------------------------

   StringSplit, Co, coefficients, `,, %A_Space%
   Result := 0
   Loop, % Co0
       i := Co0 - A_Index + 1, Result := Result * x + Co%i%
   Return, Result

}</lang> Message box shows:

128

C

Translation of: Fortran

<lang c>#include <stdio.h>

double horner(double *coeffs, int s, double x) {

 int i;
 double res = 0.0;
 
 for(i=s-1; i >= 0; i--)
 {
   res = res * x + coeffs[i];
 }
 return res;

}

int main() {

 double coeffs[] = { -19.0, 7.0, -4.0, 6.0 };
 
 printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 3.0));
 return 0;

}</lang>

C++

The same C function works too, but another solution could be:

<lang cpp>#include <iostream>

1. include <vector>

using namespace std;

double horner(vector<double> v, double x) {

 double s = 0;
 vector<double>::iterator i = v.end();
 while( i >= v.begin() ) 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;

}</lang>

Yet another solution, which is more idiomatic in C++ and works on any bidirectional sequence:

<lang cpp>

1. 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;

} </lang>

Clojure

<lang clojure>(defn horner [coeffs x]

 (reduce (fn [acc coeff] (+ (* acc x) coeff)) (reverse coeffs)))

(println (horner [-19 7 -4 6] 3))</lang>

D

<lang d>import std.stdio ; import std.traits ;

CommonType!(U,V) horner(U,V)(U[] p, V x) {

   CommonType!(U,V) acc = 0 ;
   foreach_reverse(c ; p)
       acc = acc * x + c ;
   return acc ;

}

void main() {

   auto poly = [-19, 7, -4 , 6] ;
   writefln("%s", poly.horner(3.0)) ;

} </lang>

Erlang

<lang erlang> horner(L,X) ->

 lists:foldl(fun(C, Acc) -> X*Acc+C end, lists:reverse(L)).

t() ->

 horner([-19,7,-4,6], 3).

</lang>

F#

<lang fsharp> let horner l x =

   List.rev l |> List.fold ( fun acc c -> x*acc+c) 0

horner [-19;7;-4;6] 3 </lang>

Factor

<lang factor>: horner ( coeff x -- res )

   [ <reversed> 0 ] dip '[ [ _ * ] dip + ] reduce ;</lang>

( scratchpad ) { -19 7 -4 6 } 3 horner .
128

Forth

<lang forth>: fhorner ( coeffs len F: x -- F: val )

 0e
 floats bounds ?do
   fover f*  i f@ f+
 1 floats +loop
 fswap fdrop ;

create coeffs 6e f, -4e f, 7e f, -19e f,

coeffs 4 3e fhorner f. \ 128.</lang>

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:

128.0

Haskell

<lang haskell>horner :: [Float] -> Float -> Float horner v x = foldl (\a b -> a*x + b) 0 (reverse v)

main = do

 print (horner [-19, 7, -4, 6] 3)</lang>

J

Solution:<lang j> horner =: (#."0 _ |.)~</lang> Example:<lang j> _19 7 _4 6 horner 3 128</lang> Note:
The primitive verb p. would normally be used to evaluate polynomials. <lang j> _19 7 _4 6 p. 3 128</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

JavaScript

Works with: JavaScript version 1.8

and

Works with: Firefox version 3

Translation of: Ruby

<lang javascript>function horner(coeffs, x) {

   return coeffs.reverse().reduce(function(acc, coeff) {return(acc * x + coeff)}, 0);

} print(horner([-19,7,-4,6],3)); // ==> 128 </lang>

Logo

<lang logo>to horner :x :coeffs

 if empty? :coeffs [output 0]
 output (first :coeffs) + (:x * horner :x bf :coeffs)

end

show horner 3 [-19 7 -4 6]  ; 128</lang>

MATLAB

<lang MATLAB>function accumulator = hornersRule(x,coefficients)

   accumulator = 0;
   
   for i = (numel(coefficients):-1:1)
       accumulator = (accumulator * x) + coefficients(i);
   end
   

end</lang> Output: <lang MATLAB>>> hornersRule(3,[-19, 7, -4, 6])

ans =

  128</lang>

Matlab also has a built-in function "polyval" which uses Horner's Method to evaluate polynomials. The list of coefficients is in descending order of power, where as to task spec specifies ascending order. <lang MATLAB>>> polyval(fliplr([-19, 7, -4, 6]),3)

ans =

  128</lang>

Objective-C

<lang objc>#import <Foundation/Foundation.h>

typedef double (*mfunc)(double, double, double);

double accumulateFunc(double s, double x, double a) {

 return s * x + a;

}

@interface NSArray (HornerRule) - (double)horner: (double)x; - (NSArray *)reversedArray; - (double)injectDouble: (double)s xValue: (double)x with: (mfunc)op; @end

@implementation NSArray (HornerRule) - (NSArray *)reversedArray {

 NSMutableArray *array = [NSMutableArray arrayWithCapacity: [self count]];
 NSEnumerator *e = [self reverseObjectEnumerator];
 id el;
 while( (el = [e nextObject]) != nil) {
   [array addObject: el];
 }
 return array;

}

- (double)injectDouble: (double)s xValue: (double)x with: (mfunc)op {

 double sum = s;
 NSEnumerator *e = [self objectEnumerator];
 id el;
 while( (el = [e nextObject]) != nil) {
   sum = op(sum, x, [el doubleValue]);
 }
 return sum;

}

- (double)horner: (double)x {

 return [[self reversedArray] injectDouble: 0.0 xValue: x with: (mfunc)accumulateFunc ];

} @end

int main() {

 NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

 NSArray *coeff = [NSArray 

arrayWithObjects: [NSNumber numberWithDouble: -19.0],

      		       [NSNumber numberWithDouble: 7.0],

[NSNumber numberWithDouble: -4.0], [NSNumber numberWithDouble: 6.0], nil];

 printf("%lf\n", [coeff horner: 3.0]);

 [pool release];
 return 0;

}</lang>

OCaml

<lang ocaml># let horner coeffs x =

   List.fold_left (fun acc coef -> acc * x + coef) 0 (List.rev coeffs) ;;

val horner : int list -> int -> int = <fun>

1. let coeffs = [-19; 7; -4; 6] in

 horner coeffs 3 ;;

- : int = 128</lang> It's also possible to do fold_right instead of reversing and doing fold_left; but fold_right is not tail-recursive.

Octave

<lang octave>function r = horner(a, x)

 r = 0.0;
 for i = length(a):-1:1
   r = r*x + a(i);
 endfor

endfunction

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

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>

PicoLisp

<lang PicoLisp>(de horner (Coeffs X)

  (let Res 0
     (for C (reverse Coeffs)
        (setq Res (+ C (* X Res))) ) ) )</lang>

<lang PicoLisp>: (horner (-19.0 7.0 -4.0 6.0) 3.0) -> 128</lang>

PL/I

<lang PL/I> declare (i, n) fixed binary, (x, value) float; /* 11 May 2010 */ get (x); get (n); begin;

  declare a(0:n) float;
  get list (a);
  value = a(n);
  do i = n to 1 by -1;
     value = value*x + a(i-1);
  end;
  put (value);

end; </lang>

PureBasic

<lang PureBasic>Procedure Horner(List Coefficients(), b)

 Define result
 ForEach Coefficients()
   result*b+Coefficients()
 Next
 ProcedureReturn result

EndProcedure</lang>

Implemented as <lang PureBasic>NewList a() AddElement(a()): a()= 6 AddElement(a()): a()= -4 AddElement(a()): a()= 7 AddElement(a()): a()=-19 Debug Horner(a(),3)</lang> Outputs

128

Python

<lang python>>>> def horner(coeffs, x): acc = 0 for c in reversed(coeffs): 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), 0)

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

R

<lang r>horner <- function(a, x) {

 iv <- 0
 for(i in length(a):1) {
   iv <- iv * x + a[i]
 }
 iv

}

cat(horner(c(-19, 7, -4, 6), 3), "\n")</lang>

Ruby

<lang ruby>def horner(coeffs, x)

 coeffs.reverse.inject(0) {|acc, coeff| acc * x + coeff}

end p horner([-19, 7, -4, 6], 3) # ==> 128</lang>

Scala

<lang scala>def horner(coeffs:List[Double], x:Double)=

  coeffs.reverse.foldLeft(0.0){(a,c)=> a*x+c}

</lang> <lang scala>val coeffs=List(-19.0, 7.0, -4.0, 6.0) println(horner(coeffs, 3))

  -> 128.0

</lang>

Sather

<lang sather>class MAIN is

 action(s, e, x:FLT):FLT is
   return s*x + e;
 end;

 horner(v:ARRAY{FLT}, x:FLT):FLT is
   rv ::= v.reverse;
   return rv.reduce(bind(action(_, _, x)));
 end;

 main is
   #OUT + horner(|-19.0, 7.0, -4.0, 6.0|, 3.0) + "\n";
 end;

end;</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>

Smalltalk

Works with: GNU Smalltalk

<lang smalltalk>OrderedCollection extend [

 horner: aValue [
   ^ self reverse inject: 0 into: [:acc :c | acc * aValue + c].
 ]

].

(#(-19 7 -4 6) asOrderedCollection horner: 3) displayNl.</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