Horner's rule for polynomial evaluation: Difference between revisions

{{trans|Python}}

V acc = 0

L(c) reversed(coeffs)

R acc

{{out}}

=={{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|Action!}}==

INT v,i

res=Horner(coeffs,4,x)

PrintF("=%I%E",res)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Horner's_rule_for_polynomial_evaluation.png Screenshot from Atari 8-bit computer]

=={{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|ALGOL W}}==

% Horner's rule for polynominal evaluation %

% returns the value of the polynominal defined by coefficients, %

write( r_format := "A", r_w := 8, r_d := 2, Horner( coefficients, 4, 3 ) )

end test_cases

{{out}}

<pre>

=={{header|APL}}==

Works in [[Dyalog APL]]

{{output}}

<pre>

=={{header|ATS}}==

"share/atspre_staload.hats"

in

println! (res)

=={{header|Arturo}}==

result: 0

loop reverse coeffs 'c ->

]

{{out}}

=={{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}}

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

@echo off

echo %return%

exit /b

{{out}}

<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|EDSAC order code}}==

[Copyright <2021> <ERIK SARGSYAN>

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"),

EZPF

{{out}}

<pre>

{{trans|C#}}

ELENA 5.0 :

import system'routines;

{

console.printLine(horner(new real[]{-19.0r, 7.0r, -4.0r, 6.0r}, 3.0r))

{{out}}

<pre>

=={{header|Elixir}}==

{{out}}

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

{{trans|Common Lisp}}

(defun horner (coeffs x)

coeffs :from-end t :initial-value 0))

{{out}}

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

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

10 Y = Y*X + A(I)

END

=={{header|FreeBASIC}}==

Function AlgoritmoHorner(coeffs() As Integer, x As Integer) As Integer

Dim As Integer i, acumulador = 0

Print AlgoritmoHorner(coeficientes(), x)

End

{{out}}

<pre>

=={{header|FunL}}==

{{trans|Haskell}}

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

{{out}}

=={{header|FutureBasic}}==

local fn horner( coeffs as CFArrayRef, x as NSInteger ) as double

NSLog( @"%7.1f", fn horner( coeffs, 2 ) )

{{out}}

=={{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}}==

horner =: (#."0 _ |.)~ NB. Tacit

horner =: [: +`*/ [: }: ,@,. NB. Alternate tacit (equivalent)

horner =: 4 : ' (+ *&y)/x' NB. Alternate explicit (equivalent)

'''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''':

s = coefs[end] * one(x)

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

end

{{out}}

'''Functional''':

{{out}}

'''Note''':

In Julia 1.4 or later one would normally use the built-in '''evalpoly''' function for this purpose:

{{out}}

=={{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}}

=={{header|Lambdatalk}}==

{def horner

{def horner.r

-> 2.220446049250313e-16 ~ 0

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

=={{header|Objeck}}==

class Horner {

function : Main(args : String[]) ~ Nil {

}

}

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

=={{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}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">horner</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">coeff</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">horner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,{-</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">})</span>

{{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|Picat}}==

===Recursion===

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

horner(T,X,V1),

===Iterative===

Acc = 0,

foreach(I in Coeff.length..-1..1)

Acc := Acc*X + Coeff[I]

end,

===Functional approach===

===Test===

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

println(V),

V3 = horner3([-19, 7, -4, 6], 3),

println(V3),

{{out}}

=={{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|Raku}}==

(formerly Perl 6)

@coeffs.reverse.reduce: { $^a * $x + $^b };

}

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 Raku implements lists is not optimized for this kind of treatment. [[Lisp]]-style lists are, and fortunately it is possible to emulate them with [http://doc.raku.org/type/Pair Pairs] and the reduction meta-operator:

multi horner(Pair $c, $x) {

$c.key + $x * horner( $c.value, $x )

}

We can also use the composition operator:

([o] map { $_ + $x * * }, @coeffs)(0);

}

{{out}}

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

map { .(0) }, [\o] map { $_ + $x * * }, @coeffs;

}

say horner( [ 1 X/ (1, |[\*] 1 .. *) ], i*pi )[20];

{{out}}

<pre>-0.999999999924349-5.28918515954219e-10i</pre>

=={{header|Rascal}}==