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:
when
- .
is to arrange the computation as follows:
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.
ACL2
<lang Lisp>(defun horner (ps x)
(if (endp ps) 0 (+ (first ps) (* x (horner (rest ps) x)))))</lang>
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;
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;</lang> Output:
128.0
Aime
<lang 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)
{
o_plan(horner(l_effect(-19r, 7.0, -real(4), 6r), 3), "\n");
return 0;
}</lang>
ALGOL 68
<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>
ATS
<lang ATS>#include "share/atspre_staload.hats"
fun horner (
x: int, cs: List int
) : int = let // implement list_foldright$fopr<int><int> (a, b) = a + b * x // in
list_foldright<int><int> (cs, 0)
end // end of [horner]
implement main0 () = let
val x = 3 val cs = $list{int}(~19, 7, ~4, 6) val res = horner (x, cs)
in
println! (res)
end // end of [main0]</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
BBC BASIC
<lang bbcbasic> 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</lang>
C
<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:
128
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; 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;
}</lang>
Yet another solution, which is more idiomatic in C++ and works on any bidirectional sequence:
<lang cpp>
- 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 #(-> %1 (* x) (+ %2)) (reverse coeffs)))
(println (horner [-19 7 -4 6] 3))</lang>
CoffeeScript
<lang 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 </lang>
Common Lisp
<lang lisp>(defun horner (coeffs x)
(reduce #'(lambda (coef acc) (+ (* acc x) coef))
coeffs :from-end t :initial-value 0))</lang>
D
The poly() function of the standard library std.math module uses Horner's rule: <lang d>void main() {
import std.stdio, std.math;
poly(3.0, [-19, 7, -4, 6]).writeln;
}</lang> Basic implementation: <lang d>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;
}</lang> More functional style: <lang d>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;
}</lang>
E
<lang 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 }
}</lang>
<lang e>? makeHornerPolynomial([-19, 7, -4, 6])(3)
- value: 128</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>
ERRE
<lang 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=V
END PROCEDURE
BEGIN
C[]=(-19,7,-4,6) HORNER(C[],3->RES) PRINT(RES)
END PROGRAM </lang>
Euler Math Toolbox
<lang 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
</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
<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
Fortran 77
<lang fortran> 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</lang>
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.
<lang fortran> 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</lang>
FunL
<lang funl>import lists.foldr
def horner( poly, x ) = foldr( \a, b -> a + b*x, 0, poly )
println( horner([-19, 7, -4, 6], 3) )</lang>
- Output:
128
GAP
<lang 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</lang>
Go
<lang 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}))
}</lang> Output:
128
Groovy
Solution: <lang groovy>def hornersRule = { coeff, x -> coeff.reverse().inject(0) { accum, c -> (accum * x) + c } }</lang>
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. <lang groovy>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]])</lang>
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]
Haskell
<lang haskell>horner :: (Num a) => a -> [a] -> a horner x = foldr (\a b -> a + b*x) 0
main = print $ horner 3 [-19, 7, -4, 6]</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>
Icon and Unicon
<lang Icon> 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 </lang>
J
Solution:<lang j>
horner =: 4 : ' (+ *&y)/x'
horner1 =: (#."0 _ |.)~
horner2=: [: +`*/ [: }: ,@,. NB. Alternate
</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
<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
which includes
<lang javascript>function horner(coeffs, x) {
return coeffs.reduceRight(function(acc, coeff) {return(acc * x + coeff)}, 0);
} print(horner([-19,7,-4,6],3)); // ==> 128 </lang>
Julia
Imperative: <lang julia>
function horner(coef,x) sum = coef[end] for k = length(coef)-1:-1:1 sum = coef[k] + x*sum end sum end</lang>
Output: <lang julia>julia> horner([-19,7,-4,6], 3) 128</lang>
Functional: <lang julia>horner2(coef,x) = foldr((u,v) -> u + x*v, 0, coef)</lang> Output: <lang julia>julia> horner2([-19,7,-4,6], 3) 128</lang>
K
<lang K>
horner:{y _sv|x} horner[-19 7 -4 6;3]
128 </lang>
Liberty BASIC
<lang lb>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
</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>
Maple
<lang 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); </lang> Output:
((6 x - 4) x + 7) x - 19 128
Mathematica
<lang 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</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>
Maxima
<lang 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</lang>
Mercury
<lang 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). </lang>
МК-61/52
<lang>ИП0 1 + П0 ИПE ИПD * КИП0 + ПE ИП0 1 - x=0 04 ИПE С/П</lang>
Input: Р1:РС - coefficients, Р0 - number of the coefficients, РD - x.
NetRexx
<lang 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 order n=3 x=3 r=0 loop i=n to 0 by -1
r=r*x+c[i] End
Say r Say 6*x**3-4*x**2+7*x-19</lang> Output:
128 128
Nim
<lang 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)</lang>
Objective-C
Using blocks
<lang objc>#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;
}</lang>
Objeck
<lang 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; }
} </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>
ooRexx
<lang oorexx>/* Rexx ---------------------------------------------------------------
- 04.03.2014 Walter Pachl
- --------------------------------------------------------------------*/
c = .array~of(-19,7,-4,6) -- coefficients of all x^0..x^n in order n=3 x=3 r=0 loop i=n+1 to 1 by -1
r=r*x+c[i] End
Say r Say 6*x**3-4*x**2+7*x-19</lang> Output:
128 128
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 subst(P,variable(P),x)
.
<lang parigp>horner(v,x)={
my(s=0); forstep(i=#v,1,-1,s=s*x+v[i]); s
};</lang>
Pascal
<lang 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.</lang> Output:
Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: 128.0000
Perl
<lang 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;</lang>
Functional version
<lang perl>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";</lang>
Recursive version
<lang perl>sub horner {
my ($coeff, $x) = @_; @$coeff and $$coeff[0] + $x * horner( [@$coeff[1 .. $#$coeff]], $x )
}
print horner( [ -19, 7, -4, 6 ], 3 );</lang>
Perl 6
<lang perl6>sub horner ( @coeffs, $x ) {
@coeffs.reverse.reduce: { $^a * $x + $^b };
}
say horner( [ -19, 7, -4, 6 ], 3 );</lang>
A recursive version would spare us the need for reversing the list of coeffcients (and thus possibly allowing progressive evaluation with lazy lists?). 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:
<lang perl6>multi horner(Numeric $c, $) { $c } multi horner(Pair $c, $x) {
$c.key + $x * horner( $c.value, $x )
}
print horner( [=>](-19, 7, -4, 6 ), 3 );</lang>
An other possibility would consist in creating a list of functions and chain them with a composition operator.
where is a family of function such that:
The Horner rule can then be implemented without reversing the list of coefficients. It could then be applied to a potentially infinite list.
<lang perl6>sub infix:<o>(&f, &g) { -> $x { &f(&g($x)) } }
sub horner ( @c, $x ) {
[\o] map { -> $u { $_ + $x * $u } }, @c;
}
say map { .(0) }, horner( [ -19, 7, -4, 6 ], 3 );
- compute progressive approximations of exp(2)
my @c := 1 X/ 1, [\*] 1 ... *;
say .(0) for horner( @c, 2 ); </lang>
- Output:
-19 2 -34 128 1 3 5 6.333333 7 7.266667 7.355556 7.380952 7.387302 ^C
PHP
<lang 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"; ?></lang>
Functional version
<lang php><?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"; ?></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>
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 <lang Prolog>:- 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). </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
Procedural style: <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> Functional style: <lang r>horner <- function(x, v) {
Reduce(v, right=T, f=function(a, b) { b * x + a })
}</lang>
- Output:
> v <- c(-19, 7, -4, 6) > horner(3, v) [1] 128
Racket
Translated from Haskell
<lang racket>
- lang racket
(define (horner x l)
(foldr (lambda (a b) (+ a (* b x))) 0 l))
(horner 3 '(-19 7 -4 6))
</lang>
Rascal
<lang rascal>import List;
public int horners_rule(list[int] coefficients, int x){ acc = 0; for( i <- reverse(coefficients)){ acc = acc * x + i;} return acc; }</lang> A neater and shorter solution using a reducer: <lang rascal>public int horners_rule2(list[int] coefficients, int x) = (0 | it * x + c | c <- reverse(coefficients));</lang> Output: <lang rascal>rascal>horners_rule([-19, 7, -4, 6], 3) int: 128
rascal>horners_rule2([-19, 7, -4, 6], 3) int: 128</lang>
REBOL
<lang 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</lang>
REXX
version 1
<lang 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 / 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 = ' 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.*/</lang> 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
version 2
<lang rexx>/* 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</lang>
- 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 <lang RLaB> >> a = [6, -4, 7, -19]
6 -4 7 -19
>> x=3
3
>> polyval(x, a)
128
</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>
Rust
<lang Rust>// rust 0.9-pre
fn horner(v: ~[f64], x: f64) -> f64 {
let mut accum = 0.0; let vlen = v.len(); for idx in range(0, vlen) { accum = accum*x + v[vlen - idx - 1]; }; accum
}
fn main() {
let v : ~[f64] = ~[-19., 7., -4., 6.]; println!("result: {}", horner(v, 3.0));
}</lang>
Works with any number type. It uses a reversed left fold to accumulate the result, similar to the Haskell solution. <lang Rust>// rust 0.12-nightly
std::num::zero;
fn horner<T:Num>(cs:&[T], x:T) -> T {
cs.iter().rev().fold(zero::<T>(), |acc, c| (acc*x) + (*c))
}
fn main() {
println!("{}", horner([-19i, 7, -4, 6], 3i));
}</lang>
Run BASIC
<lang runbasic>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</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>
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>
Scheme
<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>
Seed7
<lang 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;</lang>
Output:
128.0
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>
Standard ML
<lang sml>(* Assuming real type for coefficients and x *) fun horner coeffList x = foldr (fn (a, b) => a + b * x) (0.0) coeffList</lang>
Swift
<lang swift>func horner(coefs: [Double], x: Double) -> Double {
return reduce(lazy(coefs).reverse(), 0) { $0 * x + $1 }
}
println(horner([-19, 7, -4, 6], 3))</lang>
- Output:
128.0
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
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.
<lang VBA> 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 </lang>
Output:
print Horner(3, -19, 7, -4, 6) 128
XPL0
<lang 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]));</lang>
Output:
128
zkl
<lang zkl>fcn horner(coeffs,x)
{ coeffs.reverse().reduce('wrap(a,coeff){ a*x + coeff },0.0) }</lang>
- Output:
horner(T(-19,7,-4,6), 3).println(); 128
- Programming Tasks
- Solutions by Programming Task
- ACL2
- Ada
- Aime
- ALGOL 68
- ATS
- AutoHotkey
- BBC BASIC
- C
- C sharp
- C++
- Clojure
- CoffeeScript
- Common Lisp
- D
- E
- Erlang
- ERRE
- Euler Math Toolbox
- F Sharp
- Factor
- Forth
- Fortran
- FunL
- GAP
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- J
- Java
- JavaScript
- Julia
- K
- Liberty BASIC
- Logo
- Lua
- Maple
- Mathematica
- MATLAB
- Maxima
- Mercury
- МК-61/52
- NetRexx
- Nim
- Objective-C
- Objeck
- OCaml
- Octave
- OoRexx
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- Prolog
- PureBasic
- Python
- R
- Racket
- Rascal
- REBOL
- REXX
- RLaB
- Ruby
- Rust
- Run BASIC
- Sather
- Scala
- Scheme
- Seed7
- Smalltalk
- Standard ML
- Swift
- Tcl
- VBA
- XPL0
- Zkl