Horner's rule for polynomial evaluation: Difference between revisions
Added a solution for MATLAB |
|||
Line 289: | Line 289: | ||
Output: |
Output: |
||
<lang MATLAB>>> hornersRule(3,[-19, 7, -4, 6]) |
<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 = |
ans = |
Revision as of 22:17, 9 August 2010
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
Ada
<lang Ada> with Ada.Float_Text_IO; use Ada.Float_Text_IO; procedure horners_rule is type Coef is array(Positive range <>) of Float; coefficients : Coef := (-19.0,7.0,-4.0,6.0); x : Float := 3.0;
function horner(coeffs: Coef; val: Float) return Float is res : Float := 0.0; begin for p in reverse coeffs'Range loop res := res*val + coeffs(p); end loop; return res; end horner;
begin put(horner(coefficients,x),Aft=>1,Exp=>0); end horners_rule; </lang> Output:
128.0
ALGOL 68
<lang algol68>PROC horner = ([]REAL c, REAL x)REAL : (
REAL res := 0.0; FOR i FROM UPB c BY -1 TO LWB c DO res := res * x + c[i] OD; res
);
main:(
[4]REAL coeffs := (-19.0, 7.0, -4.0, 6.0); print( horner(coeffs, 3.0) )
)</lang>
AutoHotkey
<lang autohotkey>Coefficients = -19, 7, -4, 6 x := 3
MsgBox, % EvalPolynom(Coefficients, x)
- ---------------------------------------------------------------------------
EvalPolynom(Coefficients, x) { ; using Horner's rule
- ---------------------------------------------------------------------------
StringSplit, Co, coefficients, `,, %A_Space% Result := 0 Loop, % Co0 i := Co0 - A_Index + 1, Result := Result * x + Co%i% Return, Result
}</lang> Message box shows:
128
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++
The same C function works too, but another solution could be:
<lang cpp>#include <iostream>
- include <vector>
using namespace std;
double horner(vector<double> v, double x) {
double s = 0; vector<double>::iterator i = v.end(); while( i >= v.begin() ) s = s*x + *i--; return s;
}
int main() {
double c[] = { -19, 7, -4, 6 }; vector<double> v(c, c + sizeof(c)/sizeof(double)); cout << horner(v, 3.0) << endl; return 0;
}</lang>
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>
Erlang
<lang erlang> horner(L,X) ->
lists:foldl(fun(C, Acc) -> X*Acc+C end, lists:reverse(L)).
t() ->
horner([-19,7,-4,6], 3).
</lang>
F#
<lang fsharp> let horner l x =
List.rev l |> List.fold ( fun acc c -> x*acc+c) 0
horner [-19;7;-4;6] 3 </lang>
Factor
<lang factor>: horner ( coeff x -- res )
[ <reversed> 0 ] dip '[ [ _ * ] dip + ] reduce ;</lang>
( scratchpad ) { -19 7 -4 6 } 3 horner . 128
Forth
<lang forth>: fhorner ( coeffs len F: x -- F: val )
0e floats bounds ?do fover f* i f@ f+ 1 floats +loop fswap fdrop ;
create coeffs 6e f, -4e f, 7e f, -19e f,
coeffs 4 3e fhorner f. \ 128.</lang>
Fortran
<lang fortran>program test_horner
implicit none
write (*, '(f5.1)') horner ((/-19.0, 7.0, -4.0, 6.0/), 3.0)
contains
function horner (coeffs, x) result (res)
implicit none real, dimension (:), intent (in) :: coeffs real, intent (in) :: x real :: res integer :: i
res = 0.0 do i = size (coeffs), 1, -1 res = res * x + coeffs (i) end do
end function horner
end program test_horner</lang> Output:
128.0
Haskell
<lang haskell>horner :: [Float] -> Float -> Float horner v x = foldl (\a b -> a*x + b) 0 (reverse v)
main = do
print (horner [-19, 7, -4, 6] 3)</lang>
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>
MATLAB
<lang MATLAB>function accumulator = hornersRule(x,coefficients)
accumulator = 0; for i = (numel(coefficients):-1:1) accumulator = (accumulator * x) + coefficients(i); end
end</lang> Output: <lang MATLAB>>> hornersRule(3,[-19, 7, -4, 6])
ans =
128</lang>
Matlab also has a built-in function "polyval" which uses Horner's Method to evaluate polynomials. The list of coefficients is in descending order of power, where as to task spec specifies ascending order. <lang MATLAB>>> polyval(fliplr([-19, 7, -4, 6]),3)
ans =
128</lang>
Objective-C
<lang objc>#import <Foundation/Foundation.h>
typedef double (*mfunc)(double, double, double);
double accumulateFunc(double s, double x, double a) {
return s * x + a;
}
@interface NSArray (HornerRule) - (double)horner: (double)x; - (NSArray *)reversedArray; - (double)injectDouble: (double)s xValue: (double)x with: (mfunc)op; @end
@implementation NSArray (HornerRule) - (NSArray *)reversedArray {
NSMutableArray *array = [NSMutableArray arrayWithCapacity: [self count]]; NSEnumerator *e = [self reverseObjectEnumerator]; id el; while( (el = [e nextObject]) != nil) { [array addObject: el]; } return array;
}
- (double)injectDouble: (double)s xValue: (double)x with: (mfunc)op
{
double sum = s; NSEnumerator *e = [self objectEnumerator]; id el; while( (el = [e nextObject]) != nil) { sum = op(sum, x, [el doubleValue]); } return sum;
}
- (double)horner: (double)x {
return [[self reversedArray] injectDouble: 0.0 xValue: x with: (mfunc)accumulateFunc ];
} @end
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
NSArray *coeff = [NSArray
arrayWithObjects: [NSNumber numberWithDouble: -19.0],
[NSNumber numberWithDouble: 7.0],
[NSNumber numberWithDouble: -4.0], [NSNumber numberWithDouble: 6.0], nil];
printf("%lf\n", [coeff horner: 3.0]);
[pool release]; return 0;
}</lang>
OCaml
<lang ocaml># let horner coeffs x =
List.fold_left (fun acc coef -> acc * x + coef) 0 (List.rev coeffs) ;;
val horner : int list -> int -> int = <fun>
- let coeffs = [-19; 7; -4; 6] in
horner coeffs 3 ;;
- : int = 128</lang> It's also possible to do fold_right instead of reversing and doing fold_left; but fold_right is not tail-recursive.
Octave
<lang octave>function r = horner(a, x)
r = 0.0; for i = length(a):-1:1 r = r*x + a(i); endfor
endfunction
horner([-19, 7, -4, 6], 3)</lang>
Oz
<lang oz>declare
fun {Horner Coeffs X} {FoldL1 {Reverse Coeffs} fun {$ Acc Coeff} Acc*X + Coeff end} end fun {FoldL1 X|Xr Fun} {FoldL Xr Fun X} end
in
{Show {Horner [~19 7 ~4 6] 3}}</lang>
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>
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
<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>
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>
Sather
<lang sather>class MAIN is
action(s, e, x:FLT):FLT is return s*x + e; end;
horner(v:ARRAY{FLT}, x:FLT):FLT is rv ::= v.reverse; return rv.reduce(bind(action(_, _, x))); end;
main is #OUT + horner(|-19.0, 7.0, -4.0, 6.0|, 3.0) + "\n"; end;
end;</lang>
Scheme
<lang scheme>(define (horner lst x)
(define (*horner lst x acc) (if (null? lst) acc (*horner (cdr lst) x (+ (* acc x) (car lst))))) (*horner (reverse lst) x 0))
(display (horner (list -19 7 -4 6) 3)) (newline)</lang> Output: <lang>128</lang>
Smalltalk
<lang smalltalk>OrderedCollection extend [
horner: aValue [ ^ self reverse inject: 0 into: [:acc :c | acc * aValue + c]. ]
].
(#(-19 7 -4 6) asOrderedCollection horner: 3) displayNl.</lang>
Tcl
<lang tcl>package require Tcl 8.5 proc horner {coeffs x} {
set y 0 foreach c [lreverse $coeffs] { set y [expr { $y*$x+$c }] } return $y
}</lang> Demonstrating: <lang tcl>puts [horner {-19 7 -4 6} 3]</lang> Output:
128