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

128.00

</pre>

 

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

 

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

 

 

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

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

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

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

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

s = coefs[k] + x * s

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

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

 

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

v.iter().rev().fold(0.0, |acc, coeff| acc*x + coeff)

}

let v = [-19., 7., -4., 6.];

println!("result: {}", horner(&v, 3.0));

 

A generic version that works with any number type and much more. So much more, it's hard to imagine what that may be useful for.

use num::Zero;

use std::ops::{Add, Mul};

let output: f64 = horner(&v, 3.0);

println!("result: {}", output);

 

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

 

=={{header|VBScript}}==

Function horners_rule(coefficients,x)

accumulator = 0

 

WScript.StdOut.WriteLine horners_rule(Array(-19,7,-4,6),3)

 

{{Out}}

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Function Horner(coefficients As Double(), variable As Double) As Double

End Sub

 

{{out}}

<pre>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|Wren}}==

var count = c.count

if (count == 0) return 0

}

 

 

{{out}}

 

=={{header|XPL0}}==

 

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

];

 

 

Output:

 

=={{header|zkl}}==

{{out}}

<pre>