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.
C.f: Formal power series
Clojure
<lang clojure>(defn horner [coeffs x]
(reduce (fn [acc coeff] (+ (* acc x) coeff)) (reverse coeffs)))
(println (horner [-19 7 -4 6] 3))</lang>
D
<lang d>import std.stdio ; import std.traits ;
CommonType!(U,V) horner(U,V)(U[] p, V x) {
CommonType!(U,V) acc = 0 ;
foreach_reverse(c ; p)
acc = acc * x + c ;
return acc ;
}
void main() {
auto poly = [-19, 7, -4 , 6] ;
writefln("%s", poly.horner(3.0)) ;
} </lang>
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: <lang>128.0</lang>
J
Solution:<lang j> horner =: (#."0 _ |.)~</lang>
Example:<lang j> _19 7 _4 6 horner 3
128</lang>
Note:
The primitive verb p. would normally be used to evaluate polynomials.
<lang j> _19 7 _4 6 p. 3
128</lang>
Java
<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
and
<lang javascript>function horner(coeffs, x) {
return coeffs.reverse().reduce(function(acc, coeff) {return(acc * x + coeff)}, 0);
} print(horner([-19,7,-4,6],3)); // ==> 128 </lang>
Logo
<lang logo>to horner :x :coeffs
if empty? :coeffs [output 0] output (first :coeffs) + (:x * horner :x bf :coeffs)
end
show horner 3 [-19 7 -4 6] ; 128</lang>
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.
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>
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>
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>
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>
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