Horner's rule for polynomial evaluation

From Rosetta Code
Jump to: navigation, search
Task
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.

Cf. Formal power series

Contents

[edit] ACL2

(defun horner (ps x)
   (if (endp ps)
       0
       (+ (first ps)
          (* x (horner (rest ps) x)))))

[edit] Ada

with Ada.Float_Text_IO; use Ada.Float_Text_IO;
 
procedure Horners_Rule is
   type Coef is array(Positive range <>) of Float;
 
   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(Coeffs => (-19.0, 7.0, -4.0, 6.0), Val => 3.0), Aft=>1, Exp=>0);
end Horners_Rule;

Output: 

128.0

[edit] Aime

real
horner(list coeffs, real x)
{
    integer i;
    real z;
 
    z = 0;
 
    i = l_length(coeffs);
    while (i) {
	i -= 1;
	z *= x;
	z += l_q_real(coeffs, i);
    }
 
    return z;
}
 
 
integer
main(void)
{
    list l;
 
    l_append(l, -19r);
    l_append(l, 7.0);
    l_append(l, -real(4));
    l_append(l, 6r);
 
    o_real(1, horner(l, 3));
    o_byte('\n');
 
    return 0;
}

[edit] ALGOL 68

Works with: ALGOL 68G
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) )
)

[edit] ATS

staload "prelude/SATS/list.sats"
staload "prelude/DATS/list.dats"
 
fun horner (x: int, coeff: List int): int = let
  val f = lam (a: int, b: int) =<cloref1> a + b*x
in
  list_fold_right_cloref (f, coeff, 0)
end
 
implement main () = let
  val x = 3
  val coeff = '[~19,7,~4,6]
  val res = horner (x, coeff)
in
  print! (res, "\n")
end

[edit] 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
}

Message box shows: 

128

[edit] BBC BASIC

      DIM coefficients(3)
      coefficients() = -19, 7, -4, 6
      PRINT FNhorner(coefficients(), 3)
      END
 
      DEF FNhorner(coeffs(), x)
      LOCAL i%, v
      FOR i% = DIM(coeffs(), 1) TO 0 STEP -1
        v = v * x + coeffs(i%)
      NEXT
      = v

[edit] C

Translation of: Fortran
#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;
}

[edit] C#

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));
    }
}

Output: 

128

[edit] C++

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

#include <iostream>
#include <vector>
 
using namespace std;
 
double horner(vector<double> v, double x)
{
  double s = 0;
 
  for( vector<double>::const_reverse_iterator i = v.rbegin(); i != v.rend(); i++ )
    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;
}

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;
}
 

[edit] Clojure

(defn horner [coeffs x]
  (reduce (fn [acc coeff] (+ (* acc x) coeff)) (reverse coeffs)))
 
(println (horner [-19 7 -4 6] 3))

[edit] CoffeeScript

 
eval_poly = (x, coefficients) ->
  # coefficients are for ascending powers
  return 0 if coefficients.length == 0
  ones_place = coefficients.shift()
  x * eval_poly(x, coefficients) + ones_place
 
console.log eval_poly 3, [-19, 7, -4, 6] # 128
console.log eval_poly 10, [4, 3, 2, 1] # 1234
console.log eval_poly 2, [1, 1, 0, 0, 1] # 19
 

[edit] Common Lisp

(defun horner (coeffs x)
  (reduce #'(lambda (coef acc) (+ (* acc x) coef))
	  coeffs :from-end t :initial-value 0))

[edit] D

The poly() function of the standard library std.math module uses Horner's rule: 

import std.stdio, std.math;
 
void main() {
    writeln(poly(3.0, [-19, 7, -4, 6]));
}

Basic implementation: 

import std.stdio, std.traits;
 
CommonType!(U, V) horner(U, V)(U[] p, V x) {
    typeof(return) accumulator = 0;
    foreach_reverse (c; p)
        accumulator = accumulator * x + c;
    return accumulator;
}
 
void main() {
    writeln([-19, 7, -4, 6].horner(3.0));
}

More functional style: 

import std.stdio, std.algorithm, std.range;
 
auto horner(U, V)(U[] p, V x) {
    return reduce!((a, b) => a * x + b)(cast(V)0, retro(p));
}
 
void main() {
    writeln([-19, 7, -4, 6].horner(3.0));
}

[edit] E

def makeHornerPolynomial(coefficients :List) {
    def indexing := (0..!coefficients.size()).descending()
    return def hornerPolynomial(x) {
        var acc := 0
        for i in indexing {
            acc := acc * x + coefficients[i]
        }
        return acc
    }
}
? makeHornerPolynomial([-19, 7, -4, 6])(3)
# value: 128

[edit] Erlang

 
horner(L,X) ->
  lists:foldl(fun(C, Acc) -> X*Acc+C end,0, lists:reverse(L)).
t() ->
  horner([-19,7,-4,6], 3).
 

[edit] Euler Math Toolbox

 
>function horner (x,v) ...
$  n=cols(v); res=v{n};
$  loop 1 to n-1; res=res*x+v{n-#}; end;
$  return res
$endfunction
>v=[-19,7,-4,6]
 [ -19  7  -4  6 ]
>horner(2,v) // test Horner
 27
>evalpoly(2,v) // built-in Horner
 27
>horner(I,v) // complex values
 -15+1i
>horner(1±0.05,v) // interval values
 ~-10.9,-9.11~
>function p(x) &= sum(@v[k]*x^(k-1),k,1,4) // Symbolic Polynomial
                            3      2
                         6 x  - 4 x  + 7 x - 19
 

[edit] F#

 
let horner l x =
    List.rev l |> List.fold ( fun acc c -> x*acc+c) 0
 
horner [-19;7;-4;6] 3
 

[edit] Factor

: horner ( coeff x -- res )
    [ <reversed> 0 ] dip '[ [ _ * ] dip + ] reduce ;
( scratchpad ) { -19 7 -4 6 } 3 horner .
128

[edit] 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.

[edit] Fortran

Works with: Fortran version 90 and later
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

Output: 

128.0

[edit] Fortran 77 

      FUNCTION HORNER(N,A,X)
      IMPLICIT NONE
      INTEGER I,N
      DOUBLE PRECISION A(N),X,Y,HORNER
      Y=A(N)
      DO I=N-1,1,-1
      Y=Y*X+A(I)
      END DO
      HORNER=Y
      END

As a matter of fact, computing the derivative is not much more difficult (see Roundoff in Polynomial Evaluation, W. Kahan, 1986). The following subroutine computes both polynomial value and derivative for argument x. 

      SUBROUTINE HORNER2(N,A,X,Y,Z)
C COMPUTE POLYNOMIAL VALUE AND DERIVATIVE
C SEE "ROUNDOFF IN POLYNOMIAL EVALUATION", W. KAHAN, 1986
C POLY: A(1)+A(2)*X+...+A(N)*X**(N-1)
C Y: VALUE, Z: DERIVATIVE
      IMPLICIT NONE
      INTEGER I,N
      DOUBLE PRECISION A(N),X,Y,Z
      Z=0.0D0
      Y=A(N)
      DO 10 I=N-1,1,-1
      Z=Z*X+Y
   10 Y=Y*X+A(I)
      END

[edit] GAP

# The idiomatic way to compute with polynomials
 
x := Indeterminate(Rationals, "x");
 
# This is a value in a polynomial ring, not a function
p := 6*x^3 - 4*x^2 + 7*x - 19;
 
Value(p, 3);
# 128
 
u := CoefficientsOfUnivariatePolynomial(p);
# [ -19, 7, -4, 6 ]
 
# One may also create the polynomial from coefficients
q := UnivariatePolynomial(Rationals, [-19, 7, -4, 6], x);
# 6*x^3-4*x^2+7*x-19
 
p = q;
# true
 
# Now a Horner implementation
Horner := function(coef, x)
	local v, c;
	v := 0;
	for c in Reversed(coef) do
		v := x*v + c;
	od;
	return v;
end;
 
Horner(u, 3);
# 128

[edit] Go

package main
 
import "fmt"
 
func horner(x int64, c []int64) (acc int64) {
    for i := len(c) - 1; i >= 0; i-- {
        acc = acc*x + c[i]
    }
    return
}
 
func main() {
    fmt.Println(horner(3, []int64{-19, 7, -4, 6}))
}

Output: 

128

[edit] Groovy

Solution: 

def hornersRule = { coeff, x -> coeff.reverse().inject(0) { accum, c -> (accum * x) + c } }

Test includes demonstration of currying to create polynomial functions of one variable from generic Horner's rule calculation. Also demonstrates constructing the derivative function for the given polynomial. And finally demonstrates in the Newton-Raphson method to find one of the polynomial's roots using the polynomial and derivative functions constructed earlier. 

def coefficients = [-19g, 7g, -4g, 6g]
println (["p coefficients":coefficients])
 
def testPoly = hornersRule.curry(coefficients)
println (["p(3)":testPoly(3g)])
println (["p(0)":testPoly(0g)])
 
def derivativeCoefficients = { coeff -> (1..<(coeff.size())).collect { coeff[it] * it } }
println (["p' coefficients":derivativeCoefficients(coefficients)])
 
def testDeriv = hornersRule.curry(derivativeCoefficients(coefficients))
println (["p'(3)":testDeriv(3g)])
println (["p'(0)":testDeriv(0g)])
 
def newtonRaphson = { x, f, fPrime ->
    while (f(x).abs() > 0.0001) {
        x -= f(x)/fPrime(x)
    }
    x
}
 
def root = newtonRaphson(3g, testPoly, testDeriv)
println ([root:root.toString()[0..5], "p(root)":testPoly(root).toString()[0..5], "p'(root)":testDeriv(root).toString()[0..5]])

Output: 

[p coefficients:[-19, 7, -4, 6]]
[p(3):128]
[p(0):-19]
[p' coefficients:[7, -8, 18]]
[p'(3):145]
[p'(0):7]
[root:1.4183, p(root):0.0000, p'(root):31.862]

[edit] Haskell

horner :: (Num a) => a -> [a] -> a
horner x = foldr (\a b -> a + b*x) 0
 
main = print $ horner 3 [-19, 7, -4, 6]

[edit] 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

[edit] Icon and Unicon

 
procedure poly_eval (x, coeffs)
  accumulator := 0
  every index := *coeffs to 1 by -1 do 
    accumulator := accumulator * x + coeffs[index]
  return accumulator
end
 
procedure main ()
  write (poly_eval (3, [-19, 7, -4, 6]))
end
 

[edit] J

Solution:
 
 
   horner =: 4 :  '  (+ *&y)/x'   
 
   horner1 =: (#."0 _ |.)~
 
   horner2=: [: +`*/ [: }: ,@,.    NB. Alternate
 
Example:
   _19 7 _4 6 horner 3
128

Note:
The primitive verb p. would normally be used to evaluate polynomials. 

   _19 7 _4 6 p. 3
128

[edit] Java

Works with: Java version 1.5+
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;
    }
}

Output: 

128.0

[edit] JavaScript

Works with: JavaScript version 1.8
which includes
Works with: Firefox version 3
Translation of: Haskell
function horner(coeffs, x) {
    return coeffs.reduceRight(function(acc, coeff) {return(acc * x + coeff)}, 0);
}
print(horner([-19,7,-4,6],3));  // ==> 128
 

[edit] K

 
  horner:{y _sv|x}
  horner[-19 7 -4 6;3]
128
 

[edit] Liberty BASIC

src$ = "Hello"
coefficients$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in order
x = 3
print horner(coefficients$, x)      '128
 
print horner("4  3  2  1", 10)      '1234
print horner("1  1  0  0  1", 2)    '19
end
 
function horner(coefficients$, x)
    accumulator = 0
    'getting length of a list requires extra pass with WORD$.
    'So we just started from high above
    for index = 100 to 1 step -1
        cft$ = word$(coefficients$, index)
        if cft$<>"" then accumulator = ( accumulator * x ) + val(cft$)
    next
    horner = accumulator
end function
 

[edit] 

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

[edit] 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 ) )

[edit] Mathematica

Horner[l_List, x_] := Fold[x #1 + #2 &, 0, l]
Horner[{6, -4, 7, -19}, x]
-> -19 + x (7 + x (-4 + 6 x))
 
-19 + x (7 + x (-4 + 6 x)) /. x -> 3
-> 128

[edit] MATLAB

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

Output: 

>> hornersRule(3,[-19, 7, -4, 6])
 
ans =
 
   128

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. 

>> polyval(fliplr([-19, 7, -4, 6]),3)
 
ans =
 
   128

[edit] Maxima

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

[edit] Mercury

 
:- module horner.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module int, list, string.
 
main(!IO) :-
    io.format("%i\n", [i(horner(3, [-19, 7, -4, 6]))], !IO).
 
:- func horner(int, list(int)) = int.
 
horner(X, Cs) = list.foldr((func(C, Acc) = Acc * X + C), Cs, 0).
 

[edit] Objective-C

Works with: Mac OS X version 10.6+
Using blocks 
#import <Foundation/Foundation.h>
 
typedef double (^mfunc)(double, double);
 
@interface NSArray (HornerRule)
- (double)horner: (double)x;
- (NSArray *)reversedArray;
- (double)injectDouble: (double)s with: (mfunc)op;
@end
 
@implementation NSArray (HornerRule)
- (NSArray *)reversedArray
{
  return [[self reverseObjectEnumerator] allObjects];
}
 
 
- (double)injectDouble: (double)s with: (mfunc)op
{
  double sum = s;
  for(NSNumber* el in self) {
    sum = op(sum, [el doubleValue]);
  }
  return sum;
}
 
- (double)horner: (double)x
{
  return [[self reversedArray] injectDouble: 0.0 with: ^(double s, double a) { return s * x + a; } ];
}
@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("%f\n", [coeff horner: 3.0]);
 
  [pool release];
  return 0;
}

[edit] Objeck

 
class Horner {
  function : Main(args : String[]) ~ Nil {
    coeffs := Collection.FloatVector->New();  
    coeffs->AddBack(-19.0);
    coeffs->AddBack(7.0);
    coeffs->AddBack(-4.0);
    coeffs->AddBack(6.0);
    PolyEval(coeffs, 3)->PrintLine();
  }
 
  function : PolyEval(coefficients : Collection.FloatVector , x : Float) ~ Float {
    accumulator := coefficients->Get(coefficients->Size() - 1);
    for(i := coefficients->Size() - 2; i > -1; i -= 1;) {
       accumulator := (accumulator * x) + coefficients->Get(i);
    };
 
    return accumulator;
  }
}
 

[edit] 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

It's also possible to do fold_right instead of reversing and doing fold_left; but fold_right is not tail-recursive.

[edit] 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)

[edit] 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}}

[edit] PARI/GP

Also note that Pari has a polynomial type. Evaluating these is as simple as subst(P,variable(P),x). 

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

[edit] Pascal

Program HornerDemo(output);
 
function horner(a: array of double; x: double): double;
  var
    i: integer;
  begin
    horner := a[high(a)];
    for i := high(a) - 1 downto low(a) do
      horner := horner * x + a[i];
  end;
 
const
  poly: array [1..4] of double = (-19.0, 7.0, -4.0, 6.0);
 
begin
  write ('Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: ');
  writeln (horner (poly, 3.0):8:4);
end.

Output: 

Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: 128.0000

[edit] Perl

use 5.10.0;
use strict;
use warnings;
 
sub horner(\@$){
	my ($coef, $x) = @_;
	my $result = 0;
	$result = $result * $x + $_ for reverse @$coef;
	return $result;
}
 
my @coeff = (-19.0, 7, -4, 6);
my $x = 3;
say horner @coeff, $x;

[edit] Functional version

use strict;
use List::Util qw(reduce);
 
sub horner($$){
	my ($coeff_ref, $x) = @_;
	reduce { $a * $x + $b } reverse @$coeff_ref;
}
 
my @coeff = (-19.0, 7, -4, 6);
my $x = 3;
print horner(\@coeff, $x), "\n";

[edit] Perl 6

sub horner ( @coeffs, $x ) {
    @coeffs.reverse.reduce: { $^a * $x + $^b };
}
 
say horner( [ -19, 7, -4, 6 ], 3 );

[edit] PHP

<?php
function horner($coeff, $x) {
    $result = 0;
    foreach (array_reverse($coeff) as $c)
        $result = $result * $x + $c;
    return $result;
}
 
$coeff = array(-19.0, 7, -4, 6);
$x = 3;
echo horner($coeff, $x), "\n";
?>

[edit] Functional version

Works with: PHP version 5.3+
<?php
function horner($coeff, $x) {
    return array_reduce(array_reverse($coeff), function ($a, $b) use ($x) { return $a * $x + $b; }, 0);
}
 
$coeff = array(-19.0, 7, -4, 6);
$x = 3;
echo horner($coeff, $x), "\n";
?>

[edit] PicoLisp

(de horner (Coeffs X)
   (let Res 0
      (for C (reverse Coeffs)
         (setq Res (+ C (* X Res))) ) ) )
: (horner (-19.0 7.0 -4.0 6.0) 3.0)
-> 128

[edit] 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;
 

[edit] Prolog

Tested with SWI-Prolog. Works with other dialects. 

horner([], _X, 0).
 
horner([H|T], X, V) :-
	horner(T, X, V1),
	V is V1 * X + H.
 

Output : 

 ?- horner([-19, 7, -4, 6], 3, V).
V = 128.

[edit] Functionnal approach

Works with SWI-Prolog and module lambda, written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl 

:- use_module(library(lambda)).
 
 
% foldr(Pred, Init, List, R).
%
foldr(_Pred, Val, [], Val).
foldr(Pred, Val, [H | T], Res) :-
	foldr(Pred, Val, T, Res1),
	call(Pred, Res1, H, Res).
 
f_horner(L, V, R) :-
	foldr(\X^Y^Z^(Z is X * V + Y), 0, L, R).
 

[edit] PureBasic

Procedure Horner(List Coefficients(), b)
  Define result
  ForEach Coefficients()
    result*b+Coefficients()
  Next
  ProcedureReturn result
EndProcedure

Implemented as 

NewList a()
AddElement(a()): a()=  6
AddElement(a()): a()= -4
AddElement(a()): a()=  7
AddElement(a()): a()=-19
Debug Horner(a(),3)

Outputs 

128

[edit] 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

[edit] Functional version

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

[edit] 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")

[edit] Racket

Translated from Haskell 

 
#lang racket
(define (horner x l) 
    (foldr (lambda (a b) (+ a (* b x))) 0 l))
 
(horner 3 '(-19 7 -4 6))
 
 

[edit] Rascal

import List;
 
public int horners_rule(list[int] coefficients, int x){
	acc = 0;
	for( i <- reverse(coefficients)){
		acc = acc * x + i;}
	return acc;
}

A neater and shorter solution using a reducer: 

public int horners_rule2(list[int] coefficients, int x) = (0 | it * x + c | c <- reverse(coefficients));

Output: 

rascal>horners_rule([-19, 7, -4, 6], 3)
int: 128
 
rascal>horners_rule2([-19, 7, -4, 6], 3)
int: 128


[edit] REXX

/*REXX program shows using   Horner's rule   for  polynomial evaluation.*/
numeric digits 30                      /*use extra numeric precision.   */
parse arg 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 coefficients*/
  parse var poly c.deg poly            /*get  a  equation   coefficient.*/
  c.deg = (c.deg+0) / 1                /*normalize it  (add 0, div by 1)*/
  if c.deg>=0  then c.deg = '+'c.deg   /*if ¬ neg, then prefix a + sign.*/
  equ=equ c.deg                        /*concatenate it to the equation.*/
  if deg\==0  &  c.deg\=0   then       /*if not the first coefficient & */
              equ = equ'∙x^'deg        /* not 0,  append power (^) of X.*/
  equ = equ '  '                       /*insert some blanks, look pretty*/
  end   /*deg*/
 
say '         x = ' x
say '    degree = ' deg
say '  equation = ' equ
a=c.deg
                       do j=deg  by -1  for deg   /*apply Horner's rule.*/
                       _ = j-1
                       a = a*x + c._
                       end   /*j*/
say
say '    answer = ' a
                                       /*stick a fork in it, we're done.*/

output when the following is used for input: 3 -19 7 -4 6 

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

    answer =  128

[edit] 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 

 
>> a = [6, -4, 7, -19]
           6            -4             7           -19
>> x=3
           3
>> polyval(x, a)
         128
 
 

[edit] Ruby

def horner(coeffs, x)
  coeffs.reverse.inject(0) {|acc, coeff| acc * x + coeff}
end
p horner([-19, 7, -4, 6], 3)  # ==> 128

[edit] Rust

use core::io;
 
fn horner(v: ~[f64], x: f64) -> f64 {
    let mut accum = 0.0;
    let vlen = v.len();
    for uint::range(0,vlen) |idx| {
        accum = accum*x + v[vlen-idx-1];
    };
    accum
}
 
fn main() {
    let mut v : ~[f64] = ~[-19.,7.,-4.,6.];
    io::println(fmt!("result: %?",horner(v,3.0)));
}
 

[edit] Run BASIC

coef$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in order
x = 3
print horner(coef$,x)                     '128
print horner("1.2 2.3 3.4 4.5 5.6", 8)    '25478.8
print horner("5 4 3 2 1", 10)             '12345
print horner("1 0 1 1 1 0 0 1", 2)        '157
end
 
function horner(coef$,x)
  while word$(coef$, i + 1) <> ""        
     i = i + 1                          ' count the num of values
  wend
  for j = i to 1 step -1
    accum = ( accum * x ) + val(word$(coef$, j))
  next
  horner = accum
end function

[edit] 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;

[edit] Scala

def horner(coeffs:List[Double], x:Double)=
   coeffs.reverse.foldLeft(0.0){(a,c)=> a*x+c}
 
val coeffs=List(-19.0, 7.0, -4.0, 6.0)
println(horner(coeffs, 3))
   -> 128.0
 

[edit] Scheme

Works with: Scheme version R5RS
(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)

Output: 

128

[edit] Seed7

$ include "seed7_05.s7i";
  include "float.s7i";
 
const type: coeffType is array float;
 
const func float: horner (in coeffType: coeffs, in float: x) is func
  result
    var float: res is 0.0;
  local
    var integer: i is 0;
  begin
    for i range length(coeffs) downto 1 do
      res := res * x + coeffs[i];
    end for;
  end func;
 
const proc: main is func
  local
    const coeffType: coeffs is [] (-19.0, 7.0, -4.0, 6.0);
  begin
    writeln(horner(coeffs, 3.0) digits 1);
  end func;

Output: 

128.0

[edit] Smalltalk

Works with: GNU Smalltalk
OrderedCollection extend [
  horner: aValue [
    ^ self reverse inject: 0 into: [:acc :c | acc * aValue + c].
  ]
].
 
(#(-19 7 -4 6) asOrderedCollection horner: 3) displayNl.

[edit] Standard ML

(* Assuming real type for coefficients and x *)
fun horner coeffList x = foldr (fn (a, b) => a + b * x) (0.0) coeffList

[edit] 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
}

Demonstrating: 

puts [horner {-19 7 -4 6} 3]

Output: 

128

[edit] VBA

Note: this function, "Horner", gets its coefficients as a ParamArray which has no specified length. This array collect all arguments after the first one(s). This means you must specify x first, then the coefficients. 

 
Public Function Horner(x, ParamArray coeff())
Dim result As Double
Dim ncoeff As Integer
 
result = 0
ncoeff = UBound(coeff())
 
For i = ncoeff To 0 Step -1
  result = (result * x) + coeff(i)
Next i
Horner = result
End Function
 

Output: 

print Horner(3, -19, 7, -4, 6)
 128

[edit] XPL0

code IntOut=11;
 
func Horner(X, N, C);   \Return value of polynomial in X
int X, N, C;            \variable, number of terms, coefficient list
int A, I;
[A:= 0;
for I:= N-1 downto 0 do
        A:= A*X + C(I);
return A;
];
 
IntOut(0, Horner(3, 4, [-19, 7, -4, 6]));

Output: 

128
Retrieved from "http://rosettacode.org/mw/index.php?title=Horner%27s_rule_for_polynomial_evaluation&oldid=158016"
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox