Horner's rule for polynomial evaluation: Difference between revisions

 

Cf. [[Formal power series]]

 

=={{header|360 Assembly}}==

HORNER CSECT

USING HORNER,R15 set base register

PG DS CL12 buffer

YREGS

{{out}}

<pre>

 

=={{header|ACL2}}==

(if (endp ps)

0

(+ (first ps)

 

=={{header|Ada}}==

 

procedure Horners_Rule is

begin

Put(Horner(Coeffs => (-19.0, 7.0, -4.0, 6.0), Val => 3.0), Aft=>1, Exp=>0);

Output:

<pre>128.0</pre>

 

=={{header|Aime}}==

horner(list coeffs, real x)

{

 

0;

 

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G}}

(

REAL res := 0.0;

[4]REAL coeffs := (-19.0, 7.0, -4.0, 6.0);

print( horner(coeffs, 3.0) )

 

=={{header|ATS}}==

"share/atspre_staload.hats"

 

in

println! (res)

 

=={{header|AutoHotkey}}==

x := 3

 

i := Co0 - A_Index + 1, Result := Result * x + Co%i%

Return, Result

Message box shows:

<pre>128</pre>

 

=={{header|AWK}}==

function horner(x, A) {

acc = 0;

split(p,P);

print horner(x,P);

 

{{out}}

128

</pre>

 

=={{header|Batch File}}==

@echo off

 

echo %return%

exit /b

{{out}}

<pre>

128

</pre>

 

=={{header|BBC BASIC}}==

coefficients() = -19, 7, -4, 6

PRINT FNhorner(coefficients(), 3)

v = v * x + coeffs(i%)

NEXT

 

=={{header|Bracmat}}==

= accumulator coefficients x coeff

. !arg:(?coefficients.?x)

)

& Horner$(-19 7 -4 6.3)

Output:

<pre>128</pre>

=={{header|C}}==

{{trans|Fortran}}

 

double horner(double *coeffs, int s, double x)

printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 3.0));

return 0;

 

=={{header|C sharp|C#}}==

using System.Linq;

 

Console.WriteLine(Horner(new[] { -19.0, 7.0, -4.0, 6.0 }, 3.0));

}

Output:

<pre>128</pre>

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

 

#include <vector>

 

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>

 

std::cout << horner(c, c + 4, 3) << std::endl;

}

 

=={{header|Clojure}}==

(reduce #(-> %1 (* x) (+ %2)) (reverse coeffs)))

 

 

=={{header|CoffeeScript}}==

eval_poly = (x, coefficients) ->

# coefficients are for ascending powers

console.log eval_poly 10, [4, 3, 2, 1] # 1234

console.log eval_poly 2, [1, 1, 0, 0, 1] # 19

 

=={{header|Common Lisp}}==

(reduce #'(lambda (coef acc) (+ (* acc x) coef))

 

Alternate version using LOOP. Coefficients are passed in a vector.

 

(loop :with y = 0

:for i :from (1- (length a)) :downto 0

:finally (return y)))

 

 

=={{header|D}}==

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

void main() {

import std.stdio, std.math;

poly(x,pp).writeln;

}

Basic implementation:

 

CommonType!(U, V) horner(U, V)(U[] p, V x) pure nothrow @nogc {

void main() {

[-19, 7, -4, 6].horner(3.0).writeln;

More functional style:

 

auto horner(T, U)(in T[] p, in U x) pure nothrow @nogc {

void main() {

[-19, 7, -4, 6].horner(3.0).writeln;

 

=={{header|E}}==

 

def indexing := (0..!coefficients.size()).descending()

return def hornerPolynomial(x) {

return acc

}

 

 

=={{header|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.

(poly->string 'x P) → 6x^3 -4x^2 +7x -19

(poly 3 P) → 128

=={{header|Elena}}==

{{trans|C#}}

horner(coefficients,variable)

{{out}}

<pre>

 

=={{header|Elixir}}==

 

 

{{out}}

=={{header|Emacs Lisp}}==

{{trans|Common Lisp}}

(defun horner (coeffs x)

 

 

=={{header|Erlang}}==

horner(L,X) ->

lists:foldl(fun(C, Acc) -> X*Acc+C end,0, lists:reverse(L)).

t() ->

horner([-19,7,-4,6], 3).

 

=={{header|ERRE}}==

PROGRAM HORNER

 

PRINT(RES)

END PROGRAM

 

=={{header|Euler Math Toolbox}}==

 

>function horner (x,v) ...

$ n=cols(v); res=v{n};

3 2

6 x - 4 x + 7 x - 19

 

=={{header|F Sharp|F#}}==

let horner l x =

List.rev l |> List.fold ( fun acc c -> x*acc+c) 0

 

horner [-19;7;-4;6] 3

 

=={{header|Factor}}==

 

( scratchpad ) { -19 7 -4 6 } 3 horner .

 

=={{header|Forth}}==

0e

floats bounds ?do

create coeffs 6e f, -4e f, 7e f, -19e f,

 

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

 

implicit none

 

 

contains

 

implicit none

real, intent (in) :: x

real :: res

integer :: i

 

res = res * x + coeffs (i)

end do

end function horner

 

Output:

<pre>128.0</pre>

 

=== Fortran 77 ===

IMPLICIT NONE

INTEGER I,N

END DO

HORNER=Y

 

As a matter of fact, computing the derivative is not much more difficult (see [http://www.cs.berkeley.edu/~wkahan/Math128/Poly.pdf Roundoff in Polynomial Evaluation], W. Kahan, 1986). The following subroutine computes both polynomial value and derivative for argument x.

 

C COMPUTE POLYNOMIAL VALUE AND DERIVATIVE

C SEE "ROUNDOFF IN POLYNOMIAL EVALUATION", W. KAHAN, 1986

Z = Z*X + Y

10 Y = Y*X + A(I)

 

=={{header|FunL}}==

{{trans|Haskell}}

 

def horner( poly, x ) = foldr( \a, b -> a + b*x, 0, poly )

 

 

{{out}}

<pre>

128

</pre>

 

=={{header|GAP}}==

 

x := Indeterminate(Rationals, "x");

 

Horner(u, 3);

 

=={{header|Go}}==

 

import "fmt"

func main() {

fmt.Println(horner(3, []int64{-19, 7, -4, 6}))

Output:

<pre>

=={{header|Groovy}}==

Solution:

 

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.

println (["p coefficients":coefficients])

 

 

def root = newtonRaphson(3g, testPoly, testDeriv)

 

Output:

 

=={{header|Haskell}}==

horner x = foldr (\a b -> a + b*x) 0

 

 

=={{header|HicEst}}==

DATA coeffs/-19.0, 7.0, -4.0, 6.0/

 

Horner = x*Horner + c(i)

ENDDO

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure poly_eval (x, coeffs)

accumulator := 0

write (poly_eval (3, [-19, 7, -4, 6]))

end

 

=={{header|J}}==

'''Note:'''<br>

The primitive verb <code>p.</code> would normally be used to evaluate polynomials.

 

=={{header|Java}}==

{{works with|Java|1.5+}}

import java.util.Collections;

import java.util.List;

return accumulator;

}

Output:

<pre>128.0</pre>

 

{{trans|Haskell}}

return coeffs.reduceRight( function(acc, coeff) { return(acc * x + coeff) }, 0);

}

console.log(horner([-19,7,-4,6],3)); // ==> 128

 

=={{header|Julia}}==

 

'''Imperative''':

for k in length(coefs)-1:-1:1

s = coefs[k] + x * s

end

 

 

{{out}}

 

'''Functional''':

 

 

{{out}}

<pre>horner2([-19, 7, -4, 6], 3) = 128</pre>

 

=={{header|K}}==

horner:{y _sv|x}

horner[-19 7 -4 6;3]

128

 

=={{header|Kotlin}}==

 

fun horner(coeffs: DoubleArray, x: Double): Double {

val coeffs = doubleArrayOf(-19.0, 7.0, -4.0, 6.0)

println(horner(coeffs, 3.0))

 

{{out}}

128.0

</pre>

 

=={{header|Liberty BASIC}}==

coefficients$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in order

x = 3

horner = accumulator

end function

 

=={{header|Logo}}==

if empty? :coeffs [output 0]

output (first :coeffs) + (:x * horner :x bf :coeffs)

end

 

 

=={{header|Lua}}==

local res = 0

for i = #coeff, 1, -1 do

x = 3

coefficients = { -19, 7, -4, 6 }

 

=={{header|Maple}}==

applyhorner:=(L::list,x)->foldl((s,t)->s*x+t,op(ListTools:-Reverse(L))):

 

 

applyhorner([-19,7,-4,6],3);

Output:

<pre>

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Horner[{6, -4, 7, -19}, x]

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

 

-19 + x (7 + x (-4 + 6 x)) /. x -> 3

 

=={{header|MATLAB}}==

 

accumulator = 0;

end

Output:

 

ans =

 

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.

 

ans =

 

 

=={{header|Maxima}}==

horner(5*x^3+2*x+1);

x*(5*x^2+2)+1

 

poleval([0, 0, 0, 0, 1], x);

 

=={{header|Mercury}}==

:- module horner.

:- interface.

 

horner(X, Cs) = list.foldr((func(C, Acc) = Acc * X + C), Cs, 0).

 

=={{header|МК-61/52}}==

ИПE ИПD * КИП0 + ПE

ИП0 1 - x=0 04

 

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

 

=={{header|Modula-2}}==

FROM RealStr IMPORT RealToStr;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

WriteLn;

ReadChar

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols nobinary

 

End

Say r

'''Output:'''

<pre>128

 

=={{header|Nim}}==

iterator reversed[T](x: openArray[T]): T =

for i in countdown(x.high, x.low):

result = result * x + c

 

=={{header|Oberon-2}}==

{{works with|oo2c}}

MODULE HornerRule;

IMPORT

Out.Int(Eval(coefs^,4,3),0);Out.Ln

END HornerRule.

{{out}}

<pre>

128

</pre>

=={{header|Objective-C}}==

{{works with|Mac OS X|10.6+}} Using blocks

 

typedef double (^mfunc)(double, double);

}

return 0;

 

=={{header|OCaml}}==

 

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

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

 

=={{header|Octave}}==

r = 0.0;

for i = length(a):-1:1

endfunction

 

 

=={{header|ooRexx}}==

* 04.03.2014 Walter Pachl

*--------------------------------------------------------------------*/

End

Say r

'''Output:'''

<pre>128

128</pre>

=={{header|Oz}}==

fun {Horner Coeffs X}

{FoldL1 {Reverse Coeffs}

end

in

 

=={{header|PARI/GP}}==

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

my(s=0);

forstep(i=#v,1,-1,s=s*x+v[i]);

s

 

=={{header|Pascal}}==

 

function horner(a: array of double; x: double): double;

write ('Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: ');

writeln (horner (poly, 3.0):8:4);

Output:

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

 

=={{header|Perl}}==

use strict;

use warnings;

my @coeff = (-19.0, 7, -4, 6);

my $x = 3;

 

===<!-- Perl -->Functional version===

use List::Util qw(reduce);

 

my @coeff = (-19.0, 7, -4, 6);

my $x = 3;

 

===<!-- Perl -->Recursive version===

my ($coeff, $x) = @_;

@$coeff and

}

 

=={{header|Phix}}==

{{out}}

<pre>

 

=={{header|PHP}}==

function horner($coeff, $x) {

$result = 0;

$x = 3;

echo horner($coeff, $x), "\n";

 

===Functional version===

{{works with|PHP|5.3+}}

function horner($coeff, $x) {

return array_reduce(array_reverse($coeff), function ($a, $b) use ($x) { return $a * $x + $b; }, 0);

$x = 3;

echo horner($coeff, $x), "\n";

 

=={{header|PicoLisp}}==

(let Res 0

(for C (reverse Coeffs)

 

=={{header|PL/I}}==

declare (i, n) fixed binary, (x, value) float; /* 11 May 2010 */

get (x);

put (value);

end;

 

=={{header|Potion}}==

result = 0

coef reverse each (a) :

.

 

 

=={{header|PowerShell}}==

{{works with|PowerShell|4.0}}

function horner($coefficients, $x) {

$accumulator = 0

$x = 3

horner $coefficients $x

<b>Output:</b>

<pre>

=={{header|Prolog}}==

Tested with SWI-Prolog. Works with other dialects.

 

horner([H|T], X, V) :-

horner(T, X, V1),

V is V1 * X + H.

Output :

 

===Functional approach===

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

 

 

f_horner(L, V, R) :-

foldr(\X^Y^Z^(Z is X * V + Y), 0, L, R).

 

===Functional syntax (Ciao)===

Works with Ciao (https://github.com/ciao-lang/ciao) and the fsyntax package:

:- module(_, [horner/3], [fsyntax, hiord]).

:- use_module(library(hiordlib)).

horner(L, X) := ~foldr((''(H,V0,V) :- V is V0*X + H), L, 0).

 

=={{header|PureBasic}}==

Define result

ForEach Coefficients()

Next

ProcedureReturn result

 

'''Implemented as

AddElement(a()): a()= 6

AddElement(a()): a()= -4

AddElement(a()): a()= 7

AddElement(a()): a()=-19

'''Outputs

128

 

=={{header|Python}}==

acc = 0

for c in reversed(coeffs):

 

>>> horner( (-19, 7, -4, 6), 3)

 

===Functional version===

except: pass

 

 

>>> horner( (-19, 7, -4, 6), 3)

 

==={{libheader|NumPy}}===

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

 

=={{header|R}}==

Procedural style:

y <- 0

for(c in rev(a)) {

}

 

Functional style:

Reduce(v, right=T, f=function(a, b) {

b * x + a

})

{{out}}

<pre>

Translated from Haskell

 

#lang racket

(define (horner x l)

(horner 3 '(-19 7 -4 6))

 

 

=={{header|Rascal}}==

 

public int horners_rule(list[int] coefficients, int x){

acc = acc * x + i;}

return acc;

A neater and shorter solution using a reducer:

Output:

int: 128

 

rascal>horners_rule2([-19, 7, -4, 6], 3)

 

=={{header|REBOL}}==

 

 

horner: func [coeffs x] [

]

 

 

=={{header|REXX}}==

===version 1===

numeric digits 30 /*use extra numeric precision. */

parse arg x poly /*get value of X and the coefficients. */

end /*j*/

say /*display a blank line for readability.*/

'''output''' &nbsp; when the following is used for input: &nbsp; <tt> 3 &nbsp; -19 &nbsp; 7 &nbsp; -4 &nbsp; 6 </tt>

<pre>

 

===version 2===

* 27.07.2012 Walter Pachl

* coefficients reversed to descending order of power

Say ' equation = ' equ

Say ' '

{{out}}

<pre> x = 3

 

=={{header|Ring}}==

coefficients = [-19, 7, -4, 6]

see "x = 3" + nl +

next

return w

Output:

<pre>

 

This said, solution to the problem is

>> a = [6, -4, 7, -19]

6 -4 7 -19

128

 

 

=={{header|Ruby}}==

coeffs.reverse.inject(0) {|acc, coeff| acc * x + coeff}

end

 

=={{header|Run BASIC}}==

x = 3

print horner(coef$,x) '128

next

horner = accum

 

=={{header|Sather}}==

action(s, e, x:FLT):FLT is

#OUT + horner(|-19.0, 7.0, -4.0, 6.0|, 3.0) + "\n";

end;

 

=={{header|Scala}}==

coeffs.reverse.foldLeft(0.0){(a,c)=> a*x+c}

println(horner(coeffs, 3))

-> 128.0

 

=={{header|Scheme}}==

{{Works with|Scheme|R<math>^5</math>RS}}

(define (*horner lst x acc)

(if (null? lst)

 

(display (horner (list -19 7 -4 6) 3))

Output:

 

=={{header|Seed7}}==

include "float.s7i";

 

begin

writeln(horner(coeffs, 3.0) digits 1);

 

Output:

=={{header|Sidef}}==

Functional:

coeff.reverse.reduce { |a,b| a*x + b };

}

 

 

Recursive:

}

 

 

=={{header|Smalltalk}}==

{{works with|GNU Smalltalk}}

horner: aValue [

^ self reverse inject: 0 into: [:acc :c | acc * aValue + c].

].

 

 

=={{header|Standard ML}}==

 

=={{header|Swift}}==

return reduce(lazy(coefs).reverse(), 0) { $0 * x + $1 }

}

 

{{out}}

<pre>128.0</pre>

 

=={{header|Tcl}}==

proc horner {coeffs x} {

set y 0

}

return $y

Demonstrating:

Output:

<pre>128</pre>

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

Horner = result

End Function

 

Output:

128

</pre>

 

=={{header|Visual FoxPro}}==

===Coefficients in ascending order.===

LOCAL x As Double

LOCAL ARRAY aCoeffs[1]

RETURN s

ENDFUNC

 

===Coefficients in descending order.===

LOCAL x As Double

LOCAL ARRAY aCoeffs[1]

RETURN s

ENDFUNC

 

 

 

 

=={{header|XPL0}}==

 

func Horner(X, N, C); \Return value of polynomial in X

];

 

 

Output:

 

=={{header|zkl}}==

{{out}}

<pre>