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

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.

## 360 Assembly

`*        Horner's rule for polynomial evaluation - 07/10/2015HORNER   CSECT         USING  HORNER,R15         set base register         SR     R5,R5              accumulator=0         LA     R2,N               i=number_of_coeffLOOP     M      R4,X               accumulator=accumulator*x         LR     R1,R2              i         SLA    R1,2               i*4         L      R3,COEF-4(R1)      coef(i)         AR     R5,R3              accumulator=accumulator+coef(i)         BCT    R2,LOOP            i=i-1; loop n times         XDECO  R5,PG              edit accumulator          XPRNT  PG,12              print buffer         XR     R15,R15            set return code         BR     R14                return to callerCOEF     DC     F'-19',F'7',F'-4',F'6'    <== input valuesX        DC     F'3'                      <== input valueN        EQU    (X-COEF)/4         number of coefficients PG       DS     CL12               buffer         YREGS         END    HORNER`
Output:
```         128
```

## ACL2

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

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

## Aime

`realhorner(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;}  integermain(void){    o_plan(horner(l_effect(-19r, 7.0, -real(4), 6r), 3), "\n");     return 0;}`

## 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) ))`

## ATS

`#include"share/atspre_staload.hats" funhorner(  x: int, cs: List int) : int = let//implementlist_foldright\$fopr<int><int> (a, b) = a + b * x//in  list_foldright<int><int> (cs, 0)end // end of [horner] implementmain0 () = let  val x = 3  val cs = \$list{int}(~19, 7, ~4, 6)  val res = horner (x, cs)in  println! (res)end // end of [main0]`

## AutoHotkey

`Coefficients = -19, 7, -4, 6x := 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`

## AWK

`#!/usr/bin/awk -ffunction horner(x, A) {	acc = 0;		for (i = length(A); 0<i; i--) {		acc = acc*x + A[i];	}	return acc;}BEGIN {        split(p,P);	print horner(x,P);}`
Output:
```   awk  -v X=3 -v p="-19  7 -4  6" -f horner.awk
128
```

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

## Bracmat

`( ( Horner  =   accumulator coefficients x coeff    .   !arg:(?coefficients.?x)      & 0:?accumulator      &   whl        ' ( !coefficients:?coefficients #%@?coeff          & !accumulator*!x+!coeff:?accumulator          )      & !accumulator  )& Horner\$(-19 7 -4 6.3));`

Output:

`128`

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

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

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

## Clojure

`(defn horner [coeffs x]  (reduce #(-> %1 (* x) (+ %2)) (reverse coeffs))) (println (horner [-19 7 -4 6] 3))`

## 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] # 128console.log eval_poly 10, [4, 3, 2, 1] # 1234console.log eval_poly 2, [1, 1, 0, 0, 1] # 19 `

## Common Lisp

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

## D

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

`void main() {  void main() {    import std.stdio, std.math; double x = 3.0;static real[] pp = [-19,7,-4,6];     poly(x,pp).writeln;}}`

Basic implementation:

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

More functional style:

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

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

## EchoLisp

###  Functional version

` (define (horner x poly)(foldr (lambda (coeff acc) (+ coeff (* acc x))) 0 poly)) (horner 3 '(-19 7 -4 6)) → 128 `

###  Library

` (lib 'math)Lib: math.lib loaded. (define P '(-19 7 -4 6))(poly->string 'x P) → 6x^3 -4x^2 +7x -19 (poly 3 P) → 128 `

## Elixir

`horner = fn(list, x)-> List.foldr(list, 0, fn(c,acc)-> x*acc+c end) end IO.puts horner.([-19,7,-4,6], 3)`
Output:
```128
```

## Emacs Lisp

Translation of: Common Lisp
` (defun horner (coeffs x)  (reduce #'(lambda (coef acc) (+ (* acc x) coef) )	  coeffs :from-end t :initial-value 0) ) (horner '(-19 7 -4 6) 3) `

Output:

```
128
```

## Erlang

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

## ERRE

` PROGRAM HORNER !                        2   3! polynomial is -19+7x-4x +6x! DIM C[3] PROCEDURE HORNER(C[],X->RES)  LOCAL I%,V  FOR I%=UBOUND(C,1) TO 0 STEP -1 DO     V=V*X+C[I%]  END FOR  RES=VEND PROCEDURE BEGIN  C[]=(-19,7,-4,6)  HORNER(C[],3->RES)  PRINT(RES)END PROGRAM `

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

## F#

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

## Factor

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

## 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.`

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

###  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 DERIVATIVEC SEE "ROUNDOFF IN POLYNOMIAL EVALUATION", W. KAHAN, 1986C 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`

## FunL

`import lists.foldr def horner( poly, x ) = foldr( \a, b -> a + b*x, 0, poly ) println( horner([-19, 7, -4, 6], 3) )`
Output:
```128
```

## GAP

`# The idiomatic way to compute with polynomials x := Indeterminate(Rationals, "x"); # This is a value in a polynomial ring, not a functionp := 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 coefficientsq := UnivariatePolynomial(Rationals, [-19, 7, -4, 6], x);# 6*x^3-4*x^2+7*x-19 p = q;# true # Now a Horner implementationHorner := 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`

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

## 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]```

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

## 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)   ENDDOEND`

## Icon and Unicon

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

## J

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

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

`   _19 7 _4 6 p. 3128`

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

## JavaScript

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

## Julia

Imperative:

`  function horner(coef,x)     sum = coef[end]     for k = length(coef)-1:-1:1       sum = coef[k] + x*sum     end     sum end`

Output:

`julia> horner([-19,7,-4,6], 3)128`

Functional:

`horner2(coef,x) = foldr((u,v) -> u + x*v, 0, coef)`

Output:

`julia> horner2([-19,7,-4,6], 3)128`

## K

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

## Liberty BASIC

`src\$ = "Hello"coefficients\$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in orderx = 3print horner(coefficients\$, x)      '128 print horner("4  3  2  1", 10)      '1234print horner("1  1  0  0  1", 2)    '19end 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 = accumulatorend function `

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

## Lua

`function horners_rule( coeff, x )    local res = 0        for i = #coeff, 1, -1 do        res = res * x + coeff[i]    end    return resend x = 3coefficients = { -19, 7, -4, 6 }print( horners_rule( coefficients, x ) )`

## Maple

` applyhorner:=(L::list,x)->foldl((s,t)->s*x+t,op(ListTools:-Reverse(L))): applyhorner([-19,7,-4,6],x); applyhorner([-19,7,-4,6],3); `

Output:

```                    ((6 x - 4) x + 7) x - 19

128
```

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

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

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

## 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). `

## МК-61/52

`ИП0	1	+	П0ИПE	ИПD	*	КИП0	+	ПEИП0	1	-	x=0	04ИПE	С/П`

Input: Р1:РС - coefficients, Р0 - number of the coefficients, РD - x.

## NetRexx

`/* NetRexx */options replace format comments java crossref savelog symbols nobinary c = [-19, 7, -4, 6] -- # list coefficients of all x^0..x^n in ordern=3x=3r=0loop i=n to 0 by -1  r=r*x+c[i]  EndSay rSay 6*x**3-4*x**2+7*x-19`

Output:

```128
128```

## Nim

`iterator reversed(x) =  for i in countdown(x.high, x.low):    yield x[i] proc horner(coeffs, x): int =  for c in reversed(coeffs):    result = result * x + c echo horner([-19, 7, -4, 6], 3)`

## 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(){  @autoreleasepool {     NSArray *coeff = @[@-19.0, @7.0, @-4.0, @6.0];    printf("%f\n", [coeff horner: 3.0]);   }  return 0;}`

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

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

## Octave

`function r = horner(a, x)  r = 0.0;  for i = length(a):-1:1    r = r*x + a(i);  endforendfunction horner([-19, 7, -4, 6], 3)`

## ooRexx

`/* Rexx ---------------------------------------------------------------* 04.03.2014 Walter Pachl*--------------------------------------------------------------------*/c = .array~of(-19,7,-4,6) -- coefficients of all x^0..x^n in ordern=3x=3r=0loop i=n+1 to 1 by -1  r=r*x+c[i]  EndSay rSay 6*x**3-4*x**2+7*x-19`

Output:

```128
128```

## 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}  endin  {Show {Horner [~19 7 ~4 6] 3}}`

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

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

## 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;`

### 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";`

### Recursive version

`sub horner {    my (\$coeff, \$x) = @_;    @\$coeff and    \$\$coeff[0] + \$x * horner( [@\$coeff[1 .. \$#\$coeff]], \$x ) } print horner( [ -19, 7, -4, 6 ], 3 );`

## Perl 6

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

A recursive version would spare us the need for reversing the list of coefficients. However, special care must be taken in order to write it, because the way Perl 6 implements lists is not optimized for this kind of treatment. Lisp-style lists are, and fortunately it is possible to emulate them with Pairs and the reduction meta-operator:

`multi horner(Numeric \$c, \$) { \$c }multi horner(Pair \$c, \$x) {    \$c.key + \$x * horner( \$c.value, \$x ) } say horner( [=>](-19, 7, -4, 6 ), 3 );`

We can also use the composition operator:

`sub horner ( @coeffs, \$x ) {    ([o] map { \$_ + \$x * * }, @coeffs)(0);} say horner( [ -19, 7, -4, 6 ], 3 );`
Output:
`128`

One advantage of using the composition operator is that it allows for the use of an infinite list of coefficients.

`sub horner ( @coeffs, \$x ) {    map { .(0) }, [\o] map { \$_ + \$x * * }, @coeffs;} say horner( [ 1 X/ (1, |[\*] 1 .. *) ], i*pi )[20]; `
Output:
`-0.999999999924349-5.28918515954219e-10i`

## PHP

`<?phpfunction 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";?>`

### Functional version

Works with: PHP version 5.3+
`<?phpfunction 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";?>`

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

## 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; `

## PowerShell

Works with: PowerShell version 4.0
` function horner(\$coefficients, \$x) {    \$accumulator = 0    foreach(\$i in (\$coefficients.Count-1)..0){         \$accumulator = ( \$accumulator * \$x ) + \$coefficients[\$i]    }    \$accumulator}\$coefficients = @(-19, 7, -4, 6)\$x = 3horner \$coefficients \$x `

Output:

```
128
```

## 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.`

### 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). `

## PureBasic

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

Implemented as

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

Outputs

```128
```

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

### Functional version

`>>> try: from functools import reduceexcept: pass >>> def horner(coeffs, x):	return reduce(lambda acc, c: acc * x + c, reversed(coeffs), 0) >>> horner( (-19, 7, -4, 6), 3)128`

### Library: numpy

`>>> import numpy>>> numpy.polynomial.polynomial.polyval(3, (-19, 7, -4, 6))128.0`

## R

Procedural style:

`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")`

Functional style:

`horner <- function(x, v) {  Reduce(v, right=T, f=function(a, b) {    b * x + a  })}`
Output:
```> v <- c(-19, 7, -4, 6)
> horner(3, v)
[1] 128
```

## Racket

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

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

## REBOL

`rebol [] horner: func [coeffs x] [    result: 0    foreach i reverse coeffs [        result: (result * x) + i        ]    return result    ] print horner [-19 7 -4 6] 3`

## REXX

### version 1

`/*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 / 1                    /*normalize it (by dividing 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 equ= ,   /*if not the first coefficient & */                           equ'∙x^'deg /* not 0,  append power (^) of X.*/  equ = equ '  '                       /*insert some blanks, look pretty*/  end   /*deg*/ say '         x = ' xsay '    degree = ' degsay '  equation = ' equa=c.deg                       do j=deg  by -1  for deg   /*apply Horner's rule.*/                       _ = j-1                       a = a*x + c._                       end   /*j*/saysay '    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

```

### version 2

`/* REXX ---------------------------------------------------------------* 27.07.2012 Walter Pachl*            coefficients reversed to descending order of power*            I'm used to x**2+x-3*            equation formatting prettified (coefficients 1 and 0)*--------------------------------------------------------------------*/  Numeric Digits 30                /* use extra numeric precision.   */  Parse Arg x poly                 /* get value of x and coefficients*/  rpoly=''  Do p=0 To words(poly)-1    rpoly=rpoly word(poly,words(poly)-p)    End  poly=rpoly  equ=''                           /* start with equation clean slate*/  deg=words(poly)-1  pdeg=deg  Do Until deg<0                   /* get the equation's coefficients*/    Parse Var poly c.deg poly      /* in descending order of powers  */    c.deg=c.deg+0                  /* normalize it                   */    If c.deg>0 & deg<pdeg Then     /* positive and not first term    */      prefix='+'                   /*  prefix a + sign.              */    Else prefix=''    Select      When deg=0 Then term=c.deg      When deg=1 Then        If c.deg=1 Then term='x'                   Else term=c.deg'*x'      Otherwise        If c.deg=1 Then term='x^'deg                   Else term=c.deg'*x^'deg      End    If c.deg<>0 Then               /* build up the equation          */      equ=equ||prefix||term    deg=deg-1    End  a=c.pdeg  Do p=pdeg To 1 By -1             /* apply Horner's rule.           */    pm1=p-1    a=a*x+c.pm1    End  Say '        x = ' x  Say '   degree = ' pdeg  Say ' equation = ' equ  Say ' '  Say '   result = ' a`
Output:
```        x =  3
degree =  3
equation =  6*x^3-4*x^2+7*x-19

result =  128```

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

## Ruby

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

## Rust

`fn horner(v: &[f64], x: f64) -> f64 {    v.iter().rev().fold(0.0, |acc, coeff| acc*x + coeff)} fn main() {    let v = [-19., 7., -4., 6.];    println!("result: {}", horner(&v, 3.0));}`

A generic version that works with any number type and much more. So much more, it's hard to imagine what that may be useful for.
Uses a gated feature (the Zero trait), only works in unstable Rust

`#![feature(zero_one)use std::num::Zero;use std::ops::{Mul, Add}; fn horner<Arr,Arg, Out>(v: &[Arr], x: Arg) -> Out 	where Arr: Clone,	      Arg: Clone,	      Out: Zero + Mul<Arg, Output=Out> + Add<Arr, Output=Out>,{    v.iter().rev().fold(Zero::zero(), |acc, coeff| acc*x.clone() + coeff.clone())} fn main() {    let v = [-19., 7., -4., 6.];	let output: f64 = horner(&v, 3.0);    println!("result: {}", output);}`

## Run BASIC

`coef\$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in orderx = 3print horner(coef\$,x)                     '128print horner("1.2 2.3 3.4 4.5 5.6", 8)    '25478.8print horner("5 4 3 2 1", 10)             '12345print horner("1 0 1 1 1 0 0 1", 2)        '157end 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 = accumend function`

## 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;`

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

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

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

## Sidef

Functional:

`func horner(coeff, x) {    coeff.reverse.reduce { |a,b| a*x + b };} say horner([-19, 7, -4, 6], 3);   # => 128`

Recursive:

`func horner(coeff, x) {    coeff.len > 0        && (coeff[0] + x*horner(coeff.ft(1), x));} say horner([-19, 7, -4, 6], 3);   # => 128`

## 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.`

## Standard ML

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

## Swift

`func horner(coefs: [Double], x: Double) -> Double {  return reduce(lazy(coefs).reverse(), 0) { \$0 * x + \$1 }} println(horner([-19, 7, -4, 6], 3))`
Output:
`128.0`

## Tcl

`package require Tcl 8.5proc 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`

## 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 DoubleDim ncoeff As Integer result = 0ncoeff = UBound(coeff()) For i = ncoeff To 0 Step -1  result = (result * x) + coeff(i)Next iHorner = resultEnd Function `

Output:

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

## Visual FoxPro

### Coefficients in ascending order.

` LOCAL x As DoubleLOCAL ARRAY aCoeffs[1]CLEARCREATE CURSOR coeffs (c1 I, c2 I, c3 I, c4 I)INSERT INTO coeffs VALUES (-19,7,-4,6)SCATTER TO aCoeffsx = VAL(INPUTBOX("Value of x:", "Value"))? EvalPoly(@aCoeffs, x)USE IN coeffs FUNCTION EvalPoly(c, x As Double) As DoubleLOCAL s As Double, k As Integer, n As Integern = ALEN(c)s = 0FOR k = n TO 1 STEP -1	s = s*x + c[k]ENDFORRETURN sENDFUNC	 	 `

### Coefficients in descending order.

` LOCAL x As DoubleLOCAL ARRAY aCoeffs[1]CLEARCREATE CURSOR tmp (c1 I, c2 I, c3 I, c4 I)INSERT INTO tmp VALUES (6,-4,7,-19)SCATTER TO aCoeffsx = VAL(INPUTBOX("Value of x:", "Value"))? EvalPolyDesc(@aCoeffs, x)USE IN tmp FUNCTION EvalPolyDesc(c, x As Double) As DoubleLOCAL s As Double, es = 0FOR EACH e IN c FOXOBJECT	s = s*x + eENDFOR	RETURN sENDFUNC	 	 `

## VBScript

` Function horners_rule(coefficients,x)	accumulator = 0	For i = UBound(coefficients) To 0 Step -1		accumulator = (accumulator * x) + coefficients(i)	Next	horners_rule = accumulatorEnd Function WScript.StdOut.WriteLine horners_rule(Array(-19,7,-4,6),3) `
Output:
`128`

## XPL0

`code IntOut=11; func Horner(X, N, C);   \Return value of polynomial in Xint X, N, C;            \variable, number of terms, coefficient listint 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
```

## zkl

`fcn horner(coeffs,x)   { coeffs.reverse().reduce('wrap(a,coeff){ a*x + coeff },0.0) }`
Output:
```horner(T(-19,7,-4,6), 3).println();
128
```