Horner's rule for polynomial evaluation: Difference between revisions

Content added Content deleted

Inline

Revision as of 07:23, 23 November 2010

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:

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#

<lang csharp>using System; using System.Linq;

class Program {

   static double Horner(double[] coefficients, double variable)
   {
       return coefficients.Reverse().Aggregate((accumulator, coefficient) => accumulator * variable + coefficient);
   }

   static void Main()
   {
       Console.WriteLine(Horner(new[] { -19.0, 7.0, -4.0, 6.0 }, 3.0));
   }

}</lang> Output: <lang>128</lang>

C++

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

<lang cpp>#include <iostream>

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:

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>

Common Lisp

<lang lisp>(defun horner (coeffs x)

 (reduce #'(lambda (coef acc) (+ (* acc x) coef))

coeffs :from-end t))</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,0, 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>

HicEst

<lang HicEst>REAL :: x=3, coeffs(4) DATA coeffs/-19.0, 7.0, -4.0, 6.0/

WRITE(Messagebox) Horner(coeffs, x) ! shows 128

FUNCTION Horner(c, x)

  DIMENSION c(1)
  Horner = 0
  DO i = LEN(c), 1, -1
     Horner = x*Horner + c(i)
  ENDDO

END</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>

Lua

<lang lua>function horners_rule( coeff, x )

   local res = 0    
   for i = #coeff, 1, -1 do
       res = res * x + coeff[i]
   end
   return res

end

x = 3 coefficients = { -19, 7, -4, 6 } print( horners_rule( coefficients, x ) )</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>

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>

PARI/GP

Also note that Pari has a polynomial type. Evaluating these is as simple as polsubst(P,variable(P),x). <lang>horner(v,x)={

 my(s=0);
 forstep(i=#v,1,-1,s=s*x+v[i]);
 s

};</lang>

Perl

<lang Perl> use feature ':5.10'; use strict; use warnings;

sub horner($$){ my ($coeff_ref, $x) = @_; my $result = pop @$coeff_ref; while(@$coeff_ref){ $result = $result * $x + pop @$coeff_ref; } return $result; }

my @coeff = (-19.0, 7, -4, 6); my $x = 3; say horner(\@coeff, $x); </lang>

Perl 6

<lang perl6>sub horner ( @coeffs, $x ) {

   @coeffs.reverse.reduce: { $^a * $x + $^b };

}

say 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>

Prolog

Tested with SWI-Prolog. Works with other dialects. <lang Prolog>horner([], _X, 0).

horner([H|T], X, V) :- horner(T, X, V1), V is V1 * X + H. </lang> Output : <lang Prolog> ?- horner([-19, 7, -4, 6], 3, V). V = 128.</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

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>

REXX

<lang rexx> /*REXX program using Horner's rule for polynomial evaulation. */

arg 'X=' x poly /*get value of X and coefficients*/ equ= /*start with equation clean slate*/

                                      /*works for any degree equation. */
 do deg=0 until poly==              /*get the equation's coefficents.*/
 parse var poly c.deg poly            /*get  a  equation   coefficent. */
 c.deg=(c.deg+0)/1                    /*normalize it  (add 1, div by 1)*/
 if c.deg>=0 then c.deg='+'c.deg      /*if positive, then preprend a + */
 equ=equ c.deg                        /*concatenate it to the equation.*/
 if deg\==0 &,                        /*if not the first coefficient & */
    c.deg\=0 then equ=equ 'x^'deg     /* not 0,  append power (^) of X.*/
 equ=equ '  '                         /*insert some blanks, look pretty*/
 end

say ' x=' x say ' degree=' deg say 'equation=' equ a=c.deg

 do j=deg by -1 to 1                  /*apply Horner's rule to evaulate*/
 jm1=j-1
 a=a*x + c.jm1
 end

say ' answer=' a </lang> Output when the following is used for input:

x=3 -19 7 -4 6

       x= 3
  degree= 3
equation=  -19    +7 x^1    -4 x^2    +6 x^3
  answer= 128

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>

RLaB

RLaB implements horner's scheme for polynomial evaluation in its built-in function polyval. What is important is that RLaB stores the polynomials as row vectors starting from the highest power just as matlab and octave do.

This said, solution to the problem is <lang RLaB> >> a = [6, -4, 7, -19]

          6            -4             7           -19

>> x=3

>> polyval(x, a)

</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: