Horner's rule for polynomial evaluation: Difference between revisions
Updated all three D entries |
PascalABC.NET |
||
(117 intermediate revisions by 68 users not shown) | |||
Line 20: | Line 20: | ||
Cf. [[Formal power series]] |
Cf. [[Formal power series]] |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">F horner(coeffs, x) |
|||
V acc = 0 |
|||
L(c) reversed(coeffs) |
|||
acc = acc * x + c |
|||
R acc |
|||
print(horner([-19, 7, -4, 6], 3))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|360 Assembly}}== |
|||
<syntaxhighlight lang="360asm">* Horner's rule for polynomial evaluation - 07/10/2015 |
|||
HORNER CSECT |
|||
USING HORNER,R15 set base register |
|||
SR R5,R5 accumulator=0 |
|||
LA R2,N i=number_of_coeff |
|||
LOOP M R4,X accumulator=accumulator*x |
|||
LR R1,R2 i |
|||
SLA R1,2 i*4 |
|||
L R3,COEF-4(R1) coef(i) |
|||
AR R5,R3 accumulator=accumulator+coef(i) |
|||
BCT R2,LOOP i=i-1; loop n times |
|||
XDECO R5,PG edit accumulator |
|||
XPRNT PG,12 print buffer |
|||
XR R15,R15 set return code |
|||
BR R14 return to caller |
|||
COEF DC F'-19',F'7',F'-4',F'6' <== input values |
|||
X DC F'3' <== input value |
|||
N EQU (X-COEF)/4 number of coefficients |
|||
PG DS CL12 buffer |
|||
YREGS |
|||
END HORNER</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|ACL2}}== |
=={{header|ACL2}}== |
||
< |
<syntaxhighlight lang="lisp">(defun horner (ps x) |
||
(if (endp ps) |
(if (endp ps) |
||
0 |
0 |
||
(+ (first ps) |
(+ (first ps) |
||
(* x (horner (rest ps) x)))))</ |
(* x (horner (rest ps) x)))))</syntaxhighlight> |
||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">INT FUNC Horner(INT ARRAY coeffs INT count,x) |
|||
INT v,i |
|||
v=0 i=count-1 |
|||
WHILE i>=0 |
|||
DO |
|||
v=v*x+coeffs(i) |
|||
i==-1 |
|||
OD |
|||
RETURN (v) |
|||
PROC Main() |
|||
INT ARRAY coeffs=[65517 7 65532 6] |
|||
INT res,x=[3],i,count=[4] |
|||
PrintF("x=%I%E",x) |
|||
FOR i=0 TO count-1 |
|||
DO |
|||
PrintI(coeffs(i)) |
|||
IF i=1 THEN |
|||
Print("x") |
|||
ELSEIF i>1 THEN |
|||
PrintF("x^%I",i) |
|||
FI |
|||
IF i<count-1 AND coeffs(i+1)>=0 THEN |
|||
Print("+") |
|||
FI |
|||
OD |
|||
res=Horner(coeffs,4,x) |
|||
PrintF("=%I%E",res) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Horner's_rule_for_polynomial_evaluation.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
x=3 |
|||
-19+7x-4x^2+6x^3=128 |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">with Ada.Float_Text_IO; use Ada.Float_Text_IO; |
||
procedure Horners_Rule is |
procedure Horners_Rule is |
||
Line 45: | Line 127: | ||
begin |
begin |
||
Put(Horner(Coeffs => (-19.0, 7.0, -4.0, 6.0), Val => 3.0), Aft=>1, Exp=>0); |
Put(Horner(Coeffs => (-19.0, 7.0, -4.0, 6.0), Val => 3.0), Aft=>1, Exp=>0); |
||
end Horners_Rule;</ |
end Horners_Rule;</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>128.0</pre> |
<pre>128.0</pre> |
||
=={{header|Aime}}== |
=={{header|Aime}}== |
||
< |
<syntaxhighlight lang="aime">real |
||
horner(list coeffs, real x) |
horner(list coeffs, real x) |
||
{ |
{ |
||
real c, z; |
|||
real z; |
|||
z = 0; |
z = 0; |
||
for (, c of coeffs) { |
|||
z *= x; |
|||
z += c; |
|||
z *= x; |
|||
z += l_q_real(coeffs, i); |
|||
} |
} |
||
z; |
|||
} |
} |
||
integer |
integer |
||
main(void) |
main(void) |
||
{ |
{ |
||
o_(horner(list(-19r, 7.0, -4r, 6r), 3), "\n"); |
|||
0; |
|||
}</ |
}</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68G}} |
{{works with|ALGOL 68G}} |
||
< |
<syntaxhighlight lang="algol68">PROC horner = ([]REAL c, REAL x)REAL : |
||
( |
( |
||
REAL res := 0.0; |
REAL res := 0.0; |
||
Line 91: | Line 170: | ||
[4]REAL coeffs := (-19.0, 7.0, -4.0, 6.0); |
[4]REAL coeffs := (-19.0, 7.0, -4.0, 6.0); |
||
print( horner(coeffs, 3.0) ) |
print( horner(coeffs, 3.0) ) |
||
)</ |
)</syntaxhighlight> |
||
=={{header|ALGOL W}}== |
|||
<syntaxhighlight lang="algolw">begin |
|||
% Horner's rule for polynominal evaluation % |
|||
% returns the value of the polynominal defined by coefficients, % |
|||
% at the point x. The number of coefficients must be in ub % |
|||
% the coefficients should be in order with x^0 first, x^n last % |
|||
real procedure Horner( real array coefficients ( * ) |
|||
; integer value ub |
|||
; real value x |
|||
) ; |
|||
begin |
|||
real xValue; |
|||
xValue := 0; |
|||
for i := ub step -1 until 1 do xValue := ( xValue * x ) + coefficients( i ); |
|||
xValue |
|||
end Horner ; |
|||
% task test case % |
|||
begin |
|||
real array coefficients ( 1 :: 4 ); |
|||
integer cPos; |
|||
cPos := 1; |
|||
for i := -19, 7, -4, 6 do begin |
|||
coefficients( cPos ) := i; |
|||
cPos := cPos + 1 |
|||
end for_i ; |
|||
write( r_format := "A", r_w := 8, r_d := 2, Horner( coefficients, 4, 3 ) ) |
|||
end test_cases |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128.00 |
|||
</pre> |
|||
=={{header|APL}}== |
|||
Works in [[Dyalog APL]] |
|||
<syntaxhighlight lang="apl">h←⊥∘⌽</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
3 h ¯19 7 ¯4 6 |
|||
128 |
|||
</pre> |
|||
=={{header|ATS}}== |
=={{header|ATS}}== |
||
<syntaxhighlight lang="ats">#include |
|||
<lang ATS>staload "prelude/SATS/list.sats" |
|||
"share/atspre_staload.hats" |
|||
staload "prelude/DATS/list.dats" |
|||
fun |
|||
fun horner (x: int, coeff: List int): int = let |
|||
horner |
|||
val f = lam (a: int, b: int) =<cloref1> a + b*x |
|||
( |
|||
x: int, cs: List int |
|||
) : int = let |
|||
// |
|||
implement |
|||
list_foldright$fopr<int><int> (a, b) = a + b * x |
|||
// |
|||
in |
in |
||
list_foldright<int><int> (cs, 0) |
|||
list_fold_right_cloref (f, coeff, 0) |
|||
end // end of [horner] |
|||
end |
|||
implement |
implement |
||
main0 () = let |
|||
val x = 3 |
val x = 3 |
||
val |
val cs = $list{int}(~19, 7, ~4, 6) |
||
val res = horner (x, |
val res = horner (x, cs) |
||
in |
in |
||
println! (res) |
|||
end // end of [main0]</syntaxhighlight> |
|||
end</lang> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">horner: function [coeffs, x][ |
|||
result: 0 |
|||
loop reverse coeffs 'c -> |
|||
result: c + result * x |
|||
return result |
|||
] |
|||
print horner @[neg 19, 7, neg 4, 6] 3</syntaxhighlight> |
|||
{{out}} |
|||
<pre>128</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">Coefficients = -19, 7, -4, 6 |
||
x := 3 |
x := 3 |
||
Line 127: | Line 268: | ||
i := Co0 - A_Index + 1, Result := Result * x + Co%i% |
i := Co0 - A_Index + 1, Result := Result * x + Co%i% |
||
Return, Result |
Return, Result |
||
}</ |
}</syntaxhighlight> |
||
Message box shows: |
Message box shows: |
||
<pre>128</pre> |
<pre>128</pre> |
||
=={{header|AWK}}== |
|||
<syntaxhighlight lang="awk">#!/usr/bin/awk -f |
|||
function horner(x, A) { |
|||
acc = 0; |
|||
for (i = length(A); 0<i; i--) { |
|||
acc = acc*x + A[i]; |
|||
} |
|||
return acc; |
|||
} |
|||
BEGIN { |
|||
split(p,P); |
|||
print horner(x,P); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
awk -v X=3 -v p="-19 7 -4 6" -f horner.awk |
|||
128 |
|||
</pre> |
|||
=={{header|BASIC}}== |
|||
==={{header|Applesoft BASIC}}=== |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|GW-BASIC}} |
|||
<syntaxhighlight lang="qbasic">100 HOME : REM 100 CLS for Chipmunk Basic and GW-BASIC |
|||
100 CLS : REM 100 HOME for Applesoft BASIC |
|||
110 X = 3 |
|||
120 DIM COEFFS(3) |
|||
130 COEFFS(0) = -19 |
|||
140 COEFFS(1) = 7 |
|||
150 COEFFS(2) = -4 |
|||
160 COEFFS(3) = 6 |
|||
170 PRINT "Horner's algorithm for the polynomial " |
|||
180 PRINT "6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: "; |
|||
190 ACCUM = 0 |
|||
200 FOR I = 3 TO 0 STEP -1 |
|||
210 ACCUM = (ACCUM*X)+COEFFS(I) |
|||
220 NEXT I |
|||
230 PRINT ACCUM |
|||
240 END</syntaxhighlight> |
|||
==={{header|BASIC256}}=== |
|||
<syntaxhighlight lang="vb">x = 3 |
|||
dim coeficientes = {-19, 7, -4, 6} |
|||
print "Horner's algorithm for the polynomial "; |
|||
print "6*x^3 - 4*x^2 + 7*x - 19 when x = 3: "; |
|||
print AlgoritmoHorner(coeficientes, x) |
|||
end |
|||
function AlgoritmoHorner(coeffs, x) |
|||
acumulador = 0 |
|||
for i = coeffs[?]-1 to 0 step -1 |
|||
acumulador = (acumulador * x) + coeffs[i] |
|||
next i |
|||
return acumulador |
|||
end function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|Chipmunk Basic}}=== |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
{{works with|QBasic}} |
|||
<syntaxhighlight lang="qbasic">100 CLS |
|||
110 x = 3 |
|||
120 DIM coeffs(3) |
|||
130 coeffs(0) = -19 |
|||
140 coeffs(1) = 7 |
|||
150 coeffs(2) = -4 |
|||
160 coeffs(3) = 6 |
|||
170 PRINT "Horner's algorithm for the polynomial " |
|||
180 PRINT "6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: "; |
|||
190 accum = 0 |
|||
200 FOR i = UBOUND(coeffs,1) TO 0 STEP -1 |
|||
210 accum = (accum*x)+coeffs(i) |
|||
220 NEXT i |
|||
230 PRINT accum |
|||
240 END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Horner's algorithm for the polynomial |
|||
6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: 128</pre> |
|||
==={{header|Gambas}}=== |
|||
<syntaxhighlight lang="vbnet">Public coeficientes As New Integer[4] |
|||
Public Function AlgoritmoHorner(coeficientes As Integer[], x As Integer) As Integer |
|||
coeficientes[0] = -19 |
|||
coeficientes[1] = 7 |
|||
coeficientes[2] = -4 |
|||
coeficientes[3] = 6 |
|||
Dim i As Integer, acumulador As Integer = 0 |
|||
For i = coeficientes.Count - 1 To 0 Step -1 |
|||
acumulador = (acumulador * x) + coeficientes[i] |
|||
Next |
|||
Return acumulador |
|||
End Function |
|||
Public Sub Main() |
|||
Dim x As Integer = 3 |
|||
Print "Horner's algorithm for the polynomial 6*x^3 - 4*x^2 + 7*x - 19 when x = 3: "; |
|||
Print AlgoritmoHorner(coeficientes, x) |
|||
End </syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|GW-BASIC}}=== |
|||
{{works with|BASICA}} |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|PC-BASIC|any}} |
|||
{{works with|QBasic}} |
|||
<syntaxhighlight lang="qbasic">100 CLS : REM 100 HOME for Applesoft BASIC |
|||
110 X = 3 |
|||
120 DIM COEFFS(3) |
|||
130 COEFFS(0) = -19 |
|||
140 COEFFS(1) = 7 |
|||
150 COEFFS(2) = -4 |
|||
160 COEFFS(3) = 6 |
|||
170 PRINT "Horner's algorithm for the polynomial " |
|||
180 PRINT "6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: "; |
|||
190 ACCUM = 0 |
|||
200 FOR I = 3 TO 0 STEP -1 |
|||
210 ACCUM = (ACCUM*X)+COEFFS(I) |
|||
220 NEXT I |
|||
230 PRINT ACCUM |
|||
240 END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as Chipmunk Basic entry.</pre> |
|||
==={{header|Minimal BASIC}}=== |
|||
{{works with|QBasic}} |
|||
{{works with|QuickBasic}} |
|||
{{works with|Applesoft BASIC}} |
|||
{{works with|BASICA}} |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|GW-BASIC}} |
|||
{{works with|MSX BASIC}} |
|||
{{works with|Just BASIC}} |
|||
{{works with|Liberty BASIC}} |
|||
{{works with|Run BASIC}} |
|||
{{works with|Yabasic}} |
|||
<syntaxhighlight lang="qbasic">20 LET X = 3 |
|||
30 DIM C(3) |
|||
40 LET C(0) = -19 |
|||
50 LET C(1) = 7 |
|||
60 LET C(2) = -4 |
|||
70 LET C(3) = 6 |
|||
80 PRINT "HORNER'S ALGORITHM FOR THE POLYNOMIAL" |
|||
90 PRINT "6*X^3 - 4*X^2 + 7*X - 19 WHEN X = 3 : "; |
|||
100 LET A = 0 |
|||
110 FOR I = 3 TO 0 STEP -1 |
|||
120 LET A = (A*X)+C(I) |
|||
130 NEXT I |
|||
140 PRINT A |
|||
150 END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as Chipmunk Basic entry.</pre> |
|||
==={{header|MSX Basic}}=== |
|||
The [[#Minimal_BASIC|Minimal BASIC]] solution works without any changes. |
|||
==={{header|QBasic}}=== |
|||
{{works with|QBasic|1.1}} |
|||
{{works with|QuickBasic|4.5}} |
|||
<syntaxhighlight lang="qbasic">FUNCTION Horner (coeffs(), x) |
|||
acumulador = 0 |
|||
FOR i = UBOUND(coeffs) TO LBOUND(coeffs) STEP -1 |
|||
acumulador = (acumulador * x) + coeffs(i) |
|||
NEXT i |
|||
Horner = acumulador |
|||
END FUNCTION |
|||
x = 3 |
|||
DIM coeffs(3) |
|||
DATA -19, 7, -4, 6 |
|||
FOR a = LBOUND(coeffs) TO UBOUND(coeffs) |
|||
READ coeffs(a) |
|||
NEXT a |
|||
PRINT "Horner's algorithm for the polynomial 6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: "; |
|||
PRINT Horner(coeffs(), x) |
|||
END</syntaxhighlight> |
|||
==={{header|Quite BASIC}}=== |
|||
The [[#Minimal_BASIC|Minimal BASIC]] solution works without any changes. |
|||
==={{header|Yabasic}}=== |
|||
<syntaxhighlight lang="vb">x = 3 |
|||
dim coeffs(4) |
|||
coeffs(0) = -19 |
|||
coeffs(1) = 7 |
|||
coeffs(2) = -4 |
|||
coeffs(3) = 6 |
|||
print "Horner's algorithm for the polynomial "; |
|||
print "6*x^3 - 4*x^2 + 7*x - 19 when x = 3: "; |
|||
print AlgoritmoHorner(coeffs, x) |
|||
end |
|||
sub AlgoritmoHorner(coeffs, x) |
|||
local acumulador, i |
|||
acumulador = 0 |
|||
for i = arraysize(coeffs(),1) to 0 step -1 |
|||
acumulador = (acumulador * x) + coeffs(i) |
|||
next i |
|||
return acumulador |
|||
end sub</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
=={{header|Batch File}}== |
|||
<syntaxhighlight lang="dos"> |
|||
@echo off |
|||
call:horners a:-19 b:7 c:-4 d:6 x:3 |
|||
call:horners x:3 a:-19 c:-4 d:6 b:7 |
|||
pause>nul |
|||
exit /b |
|||
:horners |
|||
setlocal enabledelayedexpansion |
|||
set a=0 |
|||
set b=0 |
|||
set c=0 |
|||
set d=0 |
|||
set x=0 |
|||
for %%i in (%*) do ( |
|||
for /f "tokens=1,2 delims=:" %%j in ("%%i") do ( |
|||
set %%j=%%k |
|||
) |
|||
) |
|||
set /a return=((((0)*%x%+%d%)*%x%+(%c%))*%x%+%b%)*%x%+(%a%) |
|||
echo %return% |
|||
exit /b |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
>a:-19 b:7 c:-4 d:6 x:3 |
|||
128 |
|||
>x:3 a:-19 c:-4 d:6 b:7 |
|||
128 |
|||
</pre> |
|||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
< |
<syntaxhighlight lang="bbcbasic"> DIM coefficients(3) |
||
coefficients() = -19, 7, -4, 6 |
coefficients() = -19, 7, -4, 6 |
||
PRINT FNhorner(coefficients(), 3) |
PRINT FNhorner(coefficients(), 3) |
||
Line 142: | Line 531: | ||
v = v * x + coeffs(i%) |
v = v * x + coeffs(i%) |
||
NEXT |
NEXT |
||
= v</ |
= v</syntaxhighlight> |
||
=={{header|Bracmat}}== |
|||
<syntaxhighlight lang="bracmat">( ( Horner |
|||
= accumulator coefficients x coeff |
|||
. !arg:(?coefficients.?x) |
|||
& 0:?accumulator |
|||
& whl |
|||
' ( !coefficients:?coefficients #%@?coeff |
|||
& !accumulator*!x+!coeff:?accumulator |
|||
) |
|||
& !accumulator |
|||
) |
|||
& Horner$(-19 7 -4 6.3) |
|||
);</syntaxhighlight> |
|||
Output: |
|||
<pre>128</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
{{trans|Fortran}} |
{{trans|Fortran}} |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
double horner(double *coeffs, int s, double x) |
double horner(double *coeffs, int s, double x) |
||
Line 167: | Line 572: | ||
printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 3.0)); |
printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 3.0)); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Linq; |
using System.Linq; |
||
Line 185: | Line 590: | ||
Console.WriteLine(Horner(new[] { -19.0, 7.0, -4.0, 6.0 }, 3.0)); |
Console.WriteLine(Horner(new[] { -19.0, 7.0, -4.0, 6.0 }, 3.0)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>128</pre> |
<pre>128</pre> |
||
Line 192: | Line 597: | ||
The same C function works too, but another solution could be: |
The same C function works too, but another solution could be: |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <vector> |
#include <vector> |
||
Line 212: | Line 617: | ||
cout << horner(v, 3.0) << endl; |
cout << horner(v, 3.0) << endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
Yet another solution, which is more idiomatic in C++ and works on any bidirectional sequence: |
Yet another solution, which is more idiomatic in C++ and works on any bidirectional sequence: |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <iostream> |
#include <iostream> |
||
Line 233: | Line 638: | ||
std::cout << horner(c, c + 4, 3) << std::endl; |
std::cout << horner(c, c + 4, 3) << std::endl; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="clojure">(defn horner [coeffs x] |
||
(reduce ( |
(reduce #(-> %1 (* x) (+ %2)) (reverse coeffs))) |
||
(println (horner [-19 7 -4 6] 3))</syntaxhighlight> |
|||
(println (horner [-19 7 -4 6] 3))</lang> |
|||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang="coffeescript"> |
||
eval_poly = (x, coefficients) -> |
eval_poly = (x, coefficients) -> |
||
# coefficients are for ascending powers |
# coefficients are for ascending powers |
||
Line 251: | Line 657: | ||
console.log eval_poly 10, [4, 3, 2, 1] # 1234 |
console.log eval_poly 10, [4, 3, 2, 1] # 1234 |
||
console.log eval_poly 2, [1, 1, 0, 0, 1] # 19 |
console.log eval_poly 2, [1, 1, 0, 0, 1] # 19 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun horner (coeffs x) |
||
(reduce #'(lambda (coef acc) (+ (* acc x) coef)) |
(reduce #'(lambda (coef acc) (+ (* acc x) coef)) |
||
coeffs :from-end t :initial-value 0))</ |
coeffs :from-end t :initial-value 0))</syntaxhighlight> |
||
Alternate version using LOOP. Coefficients are passed in a vector. |
|||
<syntaxhighlight lang="lisp">(defun horner (x a) |
|||
(loop :with y = 0 |
|||
:for i :from (1- (length a)) :downto 0 |
|||
:do (setf y (+ (aref a i) (* y x))) |
|||
:finally (return y))) |
|||
(horner 1.414 #(-2 0 1))</syntaxhighlight> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
The poly() function of the standard library std.math module uses Horner's rule: |
The poly() function of the standard library std.math module uses Horner's rule: |
||
< |
<syntaxhighlight lang="d">void main() { |
||
void main() { |
|||
import std.stdio, std.math; |
import std.stdio, std.math; |
||
double x = 3.0; |
|||
static real[] pp = [-19,7,-4,6]; |
|||
poly( |
poly(x,pp).writeln; |
||
} |
|||
}</lang> |
|||
}</syntaxhighlight> |
|||
Basic implementation: |
Basic implementation: |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.traits; |
||
CommonType!(U, V) horner(U, V)(U[] p, V x) pure nothrow @nogc { |
CommonType!(U, V) horner(U, V)(U[] p, V x) pure nothrow @nogc { |
||
Line 277: | Line 697: | ||
void main() { |
void main() { |
||
[-19, 7, -4, 6].horner(3.0).writeln; |
[-19, 7, -4, 6].horner(3.0).writeln; |
||
}</ |
}</syntaxhighlight> |
||
More functional style: |
More functional style: |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range; |
||
auto horner(T, U)(in T[] p, in U x) pure nothrow |
auto horner(T, U)(in T[] p, in U x) pure nothrow @nogc { |
||
return reduce!((a, b) => a * x + b)(U(0), p.retro); |
return reduce!((a, b) => a * x + b)(U(0), p.retro); |
||
} |
} |
||
Line 287: | Line 707: | ||
void main() { |
void main() { |
||
[-19, 7, -4, 6].horner(3.0).writeln; |
[-19, 7, -4, 6].horner(3.0).writeln; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|Classes,SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
function EvaluatePolynomial(Args: array of double; X: double): double; |
|||
{Evaluate polynomial using Horner's rule } |
|||
var I: integer; |
|||
begin |
|||
Result:=0; |
|||
for I:=High(Args) downto 0 do |
|||
Result:=(Result * X ) + Args[I]; |
|||
end; |
|||
function GetPolynomialStr(Args: array of double; VarName: string): string; |
|||
{Return a string display the polynomial in normal format} |
|||
{for example: 6.0 X^3 - 4.0 X^2 + 7.0 X - 19.0} |
|||
var I: integer; |
|||
begin |
|||
Result:=''; |
|||
for I:=High(Args) downto 0 do |
|||
begin |
|||
if Args[I]>0 then |
|||
begin |
|||
if I<>High(Args) then Result:=Result+' + '; |
|||
end |
|||
else Result:=Result+' - '; |
|||
Result:=Result+FloatToStrF(Abs(Args[I]),ffFixed,18,1); |
|||
if I>0 then Result:=Result+' '+VarName; |
|||
if I>1 then Result:=Result+'^'+IntToStr(I); |
|||
end; |
|||
end; |
|||
procedure ShowHornerPoly(Memo: TMemo; Args: array of double; X: double); |
|||
{Evaluate polynomial, show formated polynomal and the result} |
|||
var R: double; |
|||
begin |
|||
R:=EvaluatePolynomial(Args,X); |
|||
Memo.Lines.Add(FloatToStrF(R,ffFixed, 18,1)); |
|||
Memo.Lines.Add(GetPolynomialStr(Args,'X')); |
|||
end; |
|||
procedure DoHornerPoly(Memo: TMemo); |
|||
begin |
|||
ShowHornerPoly(Memo,[-19, 7, -4, 6],3) |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128.0 |
|||
6.0 X^3 - 4.0 X^2 + 7.0 X - 19.0 |
|||
</pre> |
|||
=={{header|E}}== |
=={{header|E}}== |
||
< |
<syntaxhighlight lang="e">def makeHornerPolynomial(coefficients :List) { |
||
def indexing := (0..!coefficients.size()).descending() |
def indexing := (0..!coefficients.size()).descending() |
||
return def hornerPolynomial(x) { |
return def hornerPolynomial(x) { |
||
Line 300: | Line 779: | ||
return acc |
return acc |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="e">? makeHornerPolynomial([-19, 7, -4, 6])(3) |
||
# value: 128</ |
# value: 128</syntaxhighlight> |
||
=={{header|EasyLang}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang=text> |
|||
func horner coeffs[] x . |
|||
for i = len coeffs[] downto 1 |
|||
res = res * x + coeffs[i] |
|||
. |
|||
return res |
|||
. |
|||
print horner [ -19 7 -4 6 ] 3 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|EchoLisp}}== |
|||
=== Functional version === |
|||
<syntaxhighlight lang="lisp"> |
|||
(define (horner x poly) |
|||
(foldr (lambda (coeff acc) (+ coeff (* acc x))) 0 poly)) |
|||
(horner 3 '(-19 7 -4 6)) → 128 |
|||
</syntaxhighlight> |
|||
=== Library === |
|||
<syntaxhighlight lang="lisp"> |
|||
(lib 'math) |
|||
Lib: math.lib loaded. |
|||
(define P '(-19 7 -4 6)) |
|||
(poly->string 'x P) → 6x^3 -4x^2 +7x -19 |
|||
(poly 3 P) → 128 |
|||
</syntaxhighlight> |
|||
=={{header|EDSAC order code}}== |
|||
<syntaxhighlight lang="edsac"> |
|||
[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"), |
|||
to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, |
|||
and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: |
|||
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. |
|||
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, |
|||
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
|||
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
|||
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
|||
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
|||
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.] |
|||
[Horner's rule for polynomial evaluation on EDSAC by Erik Sargsyan] |
|||
[EDSAC program, Initial Orders 2] |
|||
T 56 K |
|||
GK |
|||
[0] A 3 F |
|||
[1] T 9 F |
|||
[2] A 4 F [loading the address of the 1st array element into the accumulator] |
|||
[3] A 14 @ [add an instruction code with a zero address field] |
|||
[4] T 14 @ [writing the generated instruction, zeroing the accumulator] |
|||
[5 loop] A 1 F [load the counter of unprocessed array elements into the accumulator] |
|||
[6] S 21 @ [Subtract the constant = 1] |
|||
[7] E 10 @ [if (acc >= 0) goto 10 else end] |
|||
[8] T 300 F [zeroing the accumulator] |
|||
[9] E 0 F [breakpoint, end of program] |
|||
[10] T 1 F [update the counter value and reset the accumulator] |
|||
[11] V 2 F [multiplying the number in cell 2 by the number in the multiplier register] |
|||
[12] L 1024 F [shift the number in the accumulator 12 bits to the left] |
|||
[13] L 4 F [shift the number in the accumulator 4 bits to the left] |
|||
[14 r1] A 0 F [loading the value from cell 0 into the accumulator] |
|||
[15] T 2 F [writing this value to the working cell, zeroing the accumulator] |
|||
[16] A 21 @ [loading into accumulator constant value = 1] |
|||
[17] L 0 D [shift the number in the accumulator 1 bit to the left] |
|||
[18] A 14 @ [add the code of the instruction executed in the previous step] |
|||
[19] T 14 @ [write the generated instruction into memory] |
|||
[20] E 5 @ [repeat all operations; accumulator zeroed] |
|||
[21 const 1] P 0 D [1] |
|||
GK |
|||
[0] H 10 @ [writing X0 to the multiplier register] |
|||
[1] A 11 @ [loading into the accumulator of the degree of the polynomial] |
|||
[2] T 1 F [writing the degree of a polynomial in cell 1] |
|||
[3] A 13 @ [loading the leading coefficient into the accumulator] |
|||
[4] T 2 F [writing the senior coefficient to the working cell 2] |
|||
[5] A 12 @ [loading the address of the 1st array element into the accumulator] |
|||
[6] T 4 F [writing the address of the 1st element of the array] |
|||
[7] A 7 @ [\ call] |
|||
[8] G 56 F |
|||
[9] Z 0 F |
|||
[10] P 3 F [X0 is a fixed value of X, by which we calculate the value of the polynomial] |
|||
[11 power] P 2 F [polynomial degree times 2] |
|||
[12 addr] P 14 @ [address of the 1st element of the array] |
|||
[13] P 3 F [a4 = 6] |
|||
[14] P 8 D [a3 = 17] |
|||
[15] P 9 F [a2 = 18] |
|||
[16] P 12 D [a1 = 25] |
|||
[17] P 316 F [a0 = 632] |
|||
EZPF |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Cell 2 will contain the number 12878 |
|||
</pre> |
|||
=={{header|Elena}}== |
|||
{{trans|C#}} |
|||
ELENA 5.0 : |
|||
<syntaxhighlight lang="elena">import extensions; |
|||
import system'routines; |
|||
horner(coefficients,variable) |
|||
{ |
|||
^ coefficients.clone().sequenceReverse().accumulate(new Real(),(accumulator,coefficient => accumulator * variable + coefficient)) |
|||
} |
|||
public program() |
|||
{ |
|||
console.printLine(horner(new real[]{-19.0r, 7.0r, -4.0r, 6.0r}, 3.0r)) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128.0 |
|||
</pre> |
|||
=={{header|Elixir}}== |
|||
<syntaxhighlight lang="elixir">horner = fn(list, x)-> List.foldr(list, 0, fn(c,acc)-> x*acc+c end) end |
|||
IO.puts horner.([-19,7,-4,6], 3)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|Emacs Lisp}}== |
|||
{{trans|Common Lisp}} |
|||
<syntaxhighlight lang="lisp">(require 'cl-lib) |
|||
(defun horner (coeffs x) |
|||
(cl-reduce #'(lambda (coef acc) (+ (* acc x) coef)) |
|||
coeffs :from-end t :initial-value 0)) |
|||
(horner '(-19 7 -4 6) 3)</syntaxhighlight> |
|||
{{out}} |
|||
128 |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang="erlang"> |
||
horner(L,X) -> |
horner(L,X) -> |
||
lists:foldl(fun(C, Acc) -> X*Acc+C end,0, lists:reverse(L)). |
lists:foldl(fun(C, Acc) -> X*Acc+C end,0, lists:reverse(L)). |
||
t() -> |
t() -> |
||
horner([-19,7,-4,6], 3). |
horner([-19,7,-4,6], 3). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ERRE}}== |
|||
<syntaxhighlight lang="erre"> |
|||
PROGRAM HORNER |
|||
! 2 3 |
|||
! polynomial is -19+7x-4x +6x |
|||
! |
|||
DIM C[3] |
|||
PROCEDURE HORNER(C[],X->RES) |
|||
LOCAL I%,V |
|||
FOR I%=UBOUND(C,1) TO 0 STEP -1 DO |
|||
V=V*X+C[I%] |
|||
END FOR |
|||
RES=V |
|||
END PROCEDURE |
|||
BEGIN |
|||
C[]=(-19,7,-4,6) |
|||
HORNER(C[],3->RES) |
|||
PRINT(RES) |
|||
END PROGRAM |
|||
</syntaxhighlight> |
|||
=={{header|Euler Math Toolbox}}== |
=={{header|Euler Math Toolbox}}== |
||
<syntaxhighlight lang="euler math toolbox"> |
|||
<lang Euler Math Toolbox> |
|||
>function horner (x,v) ... |
>function horner (x,v) ... |
||
$ n=cols(v); res=v{n}; |
$ n=cols(v); res=v{n}; |
||
Line 334: | Line 985: | ||
3 2 |
3 2 |
||
6 x - 4 x + 7 x - 19 |
6 x - 4 x + 7 x - 19 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
let horner l x = |
let horner l x = |
||
List.rev l |> List.fold ( fun acc c -> x*acc+c) 0 |
List.rev l |> List.fold ( fun acc c -> x*acc+c) 0 |
||
horner [-19;7;-4;6] 3 |
horner [-19;7;-4;6] 3 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">: horner ( coeff x -- res ) |
||
[ <reversed> 0 ] dip '[ [ _ * ] dip + ] reduce ;</ |
[ <reversed> 0 ] dip '[ [ _ * ] dip + ] reduce ;</syntaxhighlight> |
||
( scratchpad ) { -19 7 -4 6 } 3 horner . |
( scratchpad ) { -19 7 -4 6 } 3 horner . |
||
Line 352: | Line 1,004: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
< |
<syntaxhighlight lang="forth">: fhorner ( coeffs len F: x -- F: val ) |
||
0e |
0e |
||
floats bounds ?do |
floats bounds ?do |
||
Line 361: | Line 1,013: | ||
create coeffs 6e f, -4e f, 7e f, -19e f, |
create coeffs 6e f, -4e f, 7e f, -19e f, |
||
coeffs 4 3e fhorner f. \ 128.</ |
coeffs 4 3e fhorner f. \ 128.</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
||
< |
<syntaxhighlight lang="fortran">program test_horner |
||
implicit none |
implicit none |
||
write (*, '(f5.1)') horner ( |
write (*, '(f5.1)') horner ([-19.0, 7.0, -4.0, 6.0], 3.0) |
||
contains |
contains |
||
Line 376: | Line 1,028: | ||
implicit none |
implicit none |
||
real, dimension (:), intent (in) :: coeffs |
real, dimension (0:), intent (in) :: coeffs |
||
real, intent (in) :: x |
real, intent (in) :: x |
||
real :: res |
real :: res |
||
integer :: i |
integer :: i |
||
res = |
res = coeffs(ubound(coeffs,1)) |
||
do i = |
do i = ubound(coeffs,1)-1, 0, -1 |
||
res = res * x + coeffs (i) |
res = res * x + coeffs (i) |
||
end do |
end do |
||
Line 388: | Line 1,040: | ||
end function horner |
end function horner |
||
end program test_horner</ |
end program test_horner</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>128.0</pre> |
<pre>128.0</pre> |
||
=== Fortran 77 === |
=== Fortran 77 === |
||
< |
<syntaxhighlight lang="fortran"> FUNCTION HORNER(N,A,X) |
||
IMPLICIT NONE |
IMPLICIT NONE |
||
INTEGER I,N |
INTEGER I,N |
||
DOUBLE PRECISION A(N),X,Y,HORNER |
DOUBLE PRECISION A(N),X,Y,HORNER |
||
Y=A(N) |
Y = A(N) |
||
DO I=N-1,1,-1 |
DO I = N - 1,1,-1 |
||
Y=Y*X+A(I) |
Y = Y*X + A(I) |
||
END DO |
END DO |
||
HORNER=Y |
HORNER=Y |
||
END</ |
END</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang="fortran"> SUBROUTINE HORNER2(N,A,X,Y,Z) |
||
C COMPUTE POLYNOMIAL VALUE AND DERIVATIVE |
C COMPUTE POLYNOMIAL VALUE AND DERIVATIVE |
||
C SEE "ROUNDOFF IN POLYNOMIAL EVALUATION", W. KAHAN, 1986 |
C SEE "ROUNDOFF IN POLYNOMIAL EVALUATION", W. KAHAN, 1986 |
||
C POLY: A(1)+A(2)*X+...+A(N)*X**(N-1) |
C POLY: A(1) + A(2)*X + ... + A(N)*X**(N-1) |
||
C Y: VALUE, Z: DERIVATIVE |
C Y: VALUE, Z: DERIVATIVE |
||
IMPLICIT NONE |
IMPLICIT NONE |
||
INTEGER I,N |
INTEGER I,N |
||
DOUBLE PRECISION A(N),X,Y,Z |
DOUBLE PRECISION A(N),X,Y,Z |
||
Z=0.0D0 |
Z = 0.0D0 |
||
Y=A(N) |
Y = A(N) |
||
DO 10 I=N-1,1,-1 |
DO 10 I = N - 1,1,-1 |
||
Z=Z*X+Y |
Z = Z*X + Y |
||
10 Y=Y*X+A(I) |
10 Y = Y*X + A(I) |
||
END |
END |
||
</syntaxhighlight> |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic"> |
|||
Function AlgoritmoHorner(coeffs() As Integer, x As Integer) As Integer |
|||
Dim As Integer i, acumulador = 0 |
|||
For i = Ubound(coeffs, 1) To 0 Step -1 |
|||
acumulador = (acumulador * x) + coeffs(i) |
|||
Next i |
|||
Return acumulador |
|||
End Function |
|||
Dim As Integer x = 3 |
|||
Dim As Integer coeficientes(3) = {-19, 7, -4, 6} |
|||
Print "Algoritmo de Horner para el polinomio 6*x^3 - 4*x^2 + 7*x - 19 para x = 3: "; |
|||
Print AlgoritmoHorner(coeficientes(), x) |
|||
End |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Algoritmo de Horner para el polinomio 6*x^3 - 4*x^2 + 7*x - 19 para x = 3: 128 |
|||
</pre> |
|||
=={{header|FunL}}== |
|||
{{trans|Haskell}} |
|||
<syntaxhighlight lang="funl">import lists.foldr |
|||
def horner( poly, x ) = foldr( \a, b -> a + b*x, 0, poly ) |
|||
println( horner([-19, 7, -4, 6], 3) )</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|FutureBasic}}== |
|||
<syntaxhighlight lang="futurebasic">include "NSLog.incl" |
|||
local fn horner( coeffs as CFArrayRef, x as NSInteger ) as double |
|||
CFArrayRef reversedCoeffs |
|||
CFNumberRef num |
|||
double accumulator = 0.0 |
|||
// Reverse coeffs array |
|||
reversedCoeffs = fn EnumeratorAllObjects( fn ArrayReverseObjectEnumerator( coeffs ) ) |
|||
// Iterate over CFNumberRefs in reversed array, convert to double values, calculate and add to accumulator |
|||
for num in reversedCoeffs |
|||
accumulator = ( accumulator * x ) + fn NumberDoubleValue( num ) |
|||
next |
|||
end fn = accumulator |
|||
CFArrayRef coeffs |
|||
coeffs = @[@-19.0, @7.0, @-4.0, @6.0] |
|||
NSLog( @"%7.1f", fn horner( coeffs, 3 ) ) |
|||
coeffs = @[@4.0, @3.0, @2.0, @1.0] |
|||
NSLog( @"%7.1f", fn horner( coeffs, 10 ) ) |
|||
coeffs = @[@1, @1, @0, @0, @1] |
|||
NSLog( @"%7.1f", fn horner( coeffs, 2 ) ) |
|||
coeffs = @[@1.2, @2.3, @3.4, @4.5, @5.6] |
|||
NSLog( @"%7.1f", fn horner( coeffs, 8 ) ) |
|||
coeffs = @[@1, @0, @1, @1, @1, @0, @0, @1] |
|||
NSLog( @"%7.1f", fn horner( coeffs, 2 ) ) |
|||
HandleEvents</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128.0 |
|||
1234.0 |
|||
19.0 |
|||
25478.8 |
|||
157.0 |
|||
</pre> |
|||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
< |
<syntaxhighlight lang="gap"># The idiomatic way to compute with polynomials |
||
x := Indeterminate(Rationals, "x"); |
x := Indeterminate(Rationals, "x"); |
||
Line 453: | Line 1,187: | ||
Horner(u, 3); |
Horner(u, 3); |
||
# 128</ |
# 128</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 469: | Line 1,203: | ||
func main() { |
func main() { |
||
fmt.Println(horner(3, []int64{-19, 7, -4, 6})) |
fmt.Println(horner(3, []int64{-19, 7, -4, 6})) |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 477: | Line 1,211: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Solution: |
Solution: |
||
< |
<syntaxhighlight lang="groovy">def hornersRule = { coeff, x -> coeff.reverse().inject(0) { accum, c -> (accum * x) + c } }</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang="groovy">def coefficients = [-19g, 7g, -4g, 6g] |
||
println (["p coefficients":coefficients]) |
println (["p coefficients":coefficients]) |
||
Line 502: | Line 1,236: | ||
def root = newtonRaphson(3g, testPoly, testDeriv) |
def root = newtonRaphson(3g, testPoly, testDeriv) |
||
println ([root:root.toString()[0..5], "p(root)":testPoly(root).toString()[0..5], "p'(root)":testDeriv(root).toString()[0..5]])</ |
println ([root:root.toString()[0..5], "p(root)":testPoly(root).toString()[0..5], "p'(root)":testDeriv(root).toString()[0..5]])</syntaxhighlight> |
||
Output: |
Output: |
||
Line 514: | Line 1,248: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">horner :: (Num a) => a -> [a] -> a |
||
horner x = foldr (\a b -> a + b*x) 0 |
horner x = foldr (\a b -> a + b*x) 0 |
||
main = print $ horner 3 [-19, 7, -4, 6]</ |
main = print $ horner 3 [-19, 7, -4, 6]</syntaxhighlight> |
||
=={{header|HicEst}}== |
=={{header|HicEst}}== |
||
< |
<syntaxhighlight lang="hicest">REAL :: x=3, coeffs(4) |
||
DATA coeffs/-19.0, 7.0, -4.0, 6.0/ |
DATA coeffs/-19.0, 7.0, -4.0, 6.0/ |
||
Line 531: | Line 1,265: | ||
Horner = x*Horner + c(i) |
Horner = x*Horner + c(i) |
||
ENDDO |
ENDDO |
||
END</ |
END</syntaxhighlight> |
||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
<syntaxhighlight lang="icon"> |
|||
<lang Icon> |
|||
procedure poly_eval (x, coeffs) |
procedure poly_eval (x, coeffs) |
||
accumulator := 0 |
accumulator := 0 |
||
Line 546: | Line 1,280: | ||
write (poly_eval (3, [-19, 7, -4, 6])) |
write (poly_eval (3, [-19, 7, -4, 6])) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
'''Solution''':< |
'''Solution''':<syntaxhighlight lang="j"> |
||
horner =: (#."0 _ |.)~ NB. Tacit |
|||
horner =: |
horner =: [: +`*/ [: }: ,@,. NB. Alternate tacit (equivalent) |
||
horner =: 4 : ' (+ *&y)/x' NB. Alternate explicit (equivalent) |
|||
</syntaxhighlight> |
|||
horner1 =: (#."0 _ |.)~ |
|||
'''Example''':<syntaxhighlight lang="j"> _19 7 _4 6 horner 3 |
|||
128</syntaxhighlight> |
|||
horner2=: [: +`*/ [: }: ,@,. NB. Alternate |
|||
</lang> |
|||
'''Example''':<lang j> _19 7 _4 6 horner 3 |
|||
128</lang> |
|||
'''Note:'''<br> |
'''Note:'''<br> |
||
The primitive verb <code>p.</code> would normally be used to evaluate polynomials. |
The primitive verb <code>p.</code> would normally be used to evaluate polynomials. |
||
< |
<syntaxhighlight lang="j"> _19 7 _4 6 p. 3 |
||
128</ |
128</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
< |
<syntaxhighlight lang="java5">import java.util.ArrayList; |
||
import java.util.Collections; |
import java.util.Collections; |
||
import java.util.List; |
import java.util.List; |
||
Line 588: | Line 1,319: | ||
return accumulator; |
return accumulator; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>128.0</pre> |
<pre>128.0</pre> |
||
Line 596: | Line 1,327: | ||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">function horner(coeffs, x) { |
||
return coeffs.reduceRight(function(acc, coeff) {return(acc * x + coeff)}, 0); |
return coeffs.reduceRight( function(acc, coeff) { return(acc * x + coeff) }, 0); |
||
} |
} |
||
console.log(horner([-19,7,-4,6],3)); // ==> 128 |
|||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|jq}}== |
|||
<syntaxhighlight lang=jq> |
|||
# Input: an array of coefficients specifying the polynomial |
|||
# to be evaluated at $x, where .[0] is the constant |
|||
def horner($x): |
|||
. as $coefficients |
|||
| reduce range(length-1; -1; -1) as $i (0; . * $x + $coefficients[$i]); |
|||
# Example |
|||
[-19, 7, -4, 6] | horner(3) |
|||
</syntaxhighlight> |
|||
'''Invocation''': $JQ -n -f horner.jq |
|||
where $JQ is either jq or gojq |
|||
{{output}} |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
{{works with|Julia|1.x}} |
|||
'''Imperative''': |
|||
<syntaxhighlight lang="julia">function horner(coefs, x) |
|||
s = coefs[end] * one(x) |
|||
for k in length(coefs)-1:-1:1 |
|||
s = coefs[k] + x * s |
|||
end |
|||
return s |
|||
end |
|||
@show horner([-19, 7, -4, 6], 3)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>horner([-19, 7, -4, 6], 3) = 128</pre> |
|||
'''Functional''': |
|||
<syntaxhighlight lang="julia">horner2(coefs, x) = foldr((u, v) -> u + x * v, coefs, init=zero(promote_type(typeof(x),eltype(coefs)))) |
|||
@show horner2([-19, 7, -4, 6], 3)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>horner2([-19, 7, -4, 6], 3) = 128</pre> |
|||
'''Note''': |
|||
In Julia 1.4 or later one would normally use the built-in '''evalpoly''' function for this purpose: |
|||
<syntaxhighlight lang="julia"> |
|||
@show evalpoly(3, [-19, 7, -4, 6]) </syntaxhighlight> |
|||
{{out}} |
|||
<pre>evalpoly(3, [-19, 7, -4, 6]) = 128</pre> |
|||
=={{header|K}}== |
=={{header|K}}== |
||
<syntaxhighlight lang="k"> |
|||
<lang K> |
|||
horner:{y _sv|x} |
horner:{y _sv|x} |
||
horner[-19 7 -4 6;3] |
horner[-19 7 -4 6;3] |
||
128 |
128 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Kotlin}}== |
|||
<syntaxhighlight lang="scala">// version 1.1.2 |
|||
fun horner(coeffs: DoubleArray, x: Double): Double { |
|||
var sum = 0.0 |
|||
for (i in coeffs.size - 1 downTo 0) sum = sum * x + coeffs[i] |
|||
return sum |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val coeffs = doubleArrayOf(-19.0, 7.0, -4.0, 6.0) |
|||
println(horner(coeffs, 3.0)) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128.0 |
|||
</pre> |
|||
=={{header|Lambdatalk}}== |
|||
<syntaxhighlight lang="scheme"> |
|||
{def horner |
|||
{def horner.r |
|||
{lambda {:p :x :r} |
|||
{if {A.empty? :p} |
|||
then :r |
|||
else {horner.r {A.rest :p} :x {+ {A.first :p} {* :x :r}}}}}} |
|||
{lambda {:p :x} |
|||
{horner.r {A.reverse :p} :x 0}}} |
|||
{horner {A.new -19 7 -4 6} 3} |
|||
-> 128 |
|||
{def φ {/ {+ 1 {sqrt 5}} 2}} = 1.618033988749895 |
|||
{horner {A.new -1 -1 1} φ} |
|||
-> 2.220446049250313e-16 ~ 0 |
|||
</syntaxhighlight> |
|||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
< |
<syntaxhighlight lang="lb">src$ = "Hello" |
||
coefficients$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in order |
coefficients$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in order |
||
x = 3 |
x = 3 |
||
Line 629: | Line 1,453: | ||
horner = accumulator |
horner = accumulator |
||
end function |
end function |
||
</ |
</syntaxhighlight> |
||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
< |
<syntaxhighlight lang="logo">to horner :x :coeffs |
||
if empty? :coeffs [output 0] |
if empty? :coeffs [output 0] |
||
output (first :coeffs) + (:x * horner :x bf :coeffs) |
output (first :coeffs) + (:x * horner :x bf :coeffs) |
||
end |
end |
||
show horner 3 [-19 7 -4 6] ; 128</ |
show horner 3 [-19 7 -4 6] ; 128</syntaxhighlight> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">function horners_rule( coeff, x ) |
||
local res = 0 |
local res = 0 |
||
for i = #coeff, 1, -1 do |
for i = #coeff, 1, -1 do |
||
Line 650: | Line 1,474: | ||
x = 3 |
x = 3 |
||
coefficients = { -19, 7, -4, 6 } |
coefficients = { -19, 7, -4, 6 } |
||
print( horners_rule( coefficients, x ) )</ |
print( horners_rule( coefficients, x ) )</syntaxhighlight> |
||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
<syntaxhighlight lang="maple"> |
|||
<lang Maple> |
|||
applyhorner:=(L::list,x)->foldl((s,t)->s*x+t,op(ListTools:-Reverse(L))): |
applyhorner:=(L::list,x)->foldl((s,t)->s*x+t,op(ListTools:-Reverse(L))): |
||
Line 660: | Line 1,483: | ||
applyhorner([-19,7,-4,6],3); |
applyhorner([-19,7,-4,6],3); |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 668: | Line 1,491: | ||
</pre> |
</pre> |
||
=={{header|Mathematica}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">Horner[l_List, x_] := Fold[x #1 + #2 &, 0, l] |
||
Horner[{6, -4, 7, -19}, x] |
Horner[{6, -4, 7, -19}, x] |
||
-> -19 + x (7 + x (-4 + 6 x)) |
-> -19 + x (7 + x (-4 + 6 x)) |
||
-19 + x (7 + x (-4 + 6 x)) /. x -> 3 |
-19 + x (7 + x (-4 + 6 x)) /. x -> 3 |
||
-> 128</ |
-> 128</syntaxhighlight> |
||
=={{header|MATLAB}}== |
=={{header|MATLAB}}== |
||
< |
<syntaxhighlight lang="matlab">function accumulator = hornersRule(x,coefficients) |
||
accumulator = 0; |
accumulator = 0; |
||
Line 685: | Line 1,508: | ||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
Output: |
Output: |
||
< |
<syntaxhighlight lang="matlab">>> hornersRule(3,[-19, 7, -4, 6]) |
||
ans = |
ans = |
||
128</ |
128</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang="matlab">>> polyval(fliplr([-19, 7, -4, 6]),3) |
||
ans = |
ans = |
||
128</ |
128</syntaxhighlight> |
||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
< |
<syntaxhighlight lang="maxima">/* Function horner already exists in Maxima, though it operates on expressions, not lists of coefficients */ |
||
horner(5*x^3+2*x+1); |
horner(5*x^3+2*x+1); |
||
x*(5*x^2+2)+1 |
x*(5*x^2+2)+1 |
||
Line 744: | Line 1,567: | ||
poleval([0, 0, 0, 0, 1], x); |
poleval([0, 0, 0, 0, 1], x); |
||
x^4</ |
x^4</syntaxhighlight> |
||
=={{header|Mercury}}== |
=={{header|Mercury}}== |
||
< |
<syntaxhighlight lang="mercury"> |
||
:- module horner. |
:- module horner. |
||
:- interface. |
:- interface. |
||
Line 761: | Line 1,584: | ||
horner(X, Cs) = list.foldr((func(C, Acc) = Acc * X + C), Cs, 0). |
horner(X, Cs) = list.foldr((func(C, Acc) = Acc * X + C), Cs, 0). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|МК-61/52}}== |
=={{header|МК-61/52}}== |
||
<lang>ИП0 1 + П0 |
<syntaxhighlight lang="text">ИП0 1 + П0 |
||
ИПE ИПD * КИП0 + ПE |
ИПE ИПD * КИП0 + ПE |
||
ИП0 1 - x=0 04 |
ИП0 1 - x=0 04 |
||
ИПE С/П</ |
ИПE С/П</syntaxhighlight> |
||
''Input:'' Р1:РС - coefficients, Р0 - number of the coefficients, РD - ''x''. |
''Input:'' Р1:РС - coefficients, Р0 - number of the coefficients, РD - ''x''. |
||
=={{header|Modula-2}}== |
|||
<syntaxhighlight lang="modula2">MODULE Horner; |
|||
FROM RealStr IMPORT RealToStr; |
|||
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
|||
PROCEDURE Horner(coeff : ARRAY OF REAL; x : REAL) : REAL; |
|||
VAR |
|||
ans : REAL; |
|||
i : CARDINAL; |
|||
BEGIN |
|||
ans := 0.0; |
|||
FOR i:=HIGH(coeff) TO 0 BY -1 DO |
|||
ans := (ans * x) + coeff[i]; |
|||
END; |
|||
RETURN ans |
|||
END Horner; |
|||
TYPE A = ARRAY[0..3] OF REAL; |
|||
VAR |
|||
buf : ARRAY[0..63] OF CHAR; |
|||
coeff : A; |
|||
ans : REAL; |
|||
BEGIN |
|||
coeff := A{-19.0, 7.0, -4.0, 6.0}; |
|||
ans := Horner(coeff, 3.0); |
|||
RealToStr(ans, buf); |
|||
WriteString(buf); |
|||
WriteLn; |
|||
ReadChar |
|||
END Horner.</syntaxhighlight> |
|||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
< |
<syntaxhighlight lang="netrexx">/* NetRexx */ |
||
options replace format comments java crossref savelog symbols nobinary |
options replace format comments java crossref savelog symbols nobinary |
||
Line 783: | Line 1,637: | ||
End |
End |
||
Say r |
Say r |
||
Say 6*x**3-4*x**2+7*x-19</ |
Say 6*x**3-4*x**2+7*x-19</syntaxhighlight> |
||
'''Output:''' |
'''Output:''' |
||
<pre>128 |
<pre>128 |
||
128</pre> |
128</pre> |
||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim"># You can also just use `reversed` proc from stdlib `algorithm` module |
|||
iterator reversed[T](x: openArray[T]): T = |
|||
for i in countdown(x.high, x.low): |
|||
yield x[i] |
|||
proc horner[T](coeffs: openArray[T], x: T): int = |
|||
for c in reversed(coeffs): |
|||
result = result * x + c |
|||
echo horner([-19, 7, -4, 6], 3)</syntaxhighlight> |
|||
=={{header|Oberon-2}}== |
|||
{{works with|oo2c}} |
|||
<syntaxhighlight lang="oberon2"> |
|||
MODULE HornerRule; |
|||
IMPORT |
|||
Out; |
|||
TYPE |
|||
Coefs = POINTER TO ARRAY OF LONGINT; |
|||
VAR |
|||
coefs: Coefs; |
|||
PROCEDURE Eval(coefs: ARRAY OF LONGINT;size,x: LONGINT): LONGINT; |
|||
VAR |
|||
i,acc: LONGINT; |
|||
BEGIN |
|||
acc := 0; |
|||
FOR i := LEN(coefs) - 1 TO 0 BY -1 DO |
|||
acc := acc * x + coefs[i] |
|||
END; |
|||
RETURN acc |
|||
END Eval; |
|||
BEGIN |
|||
NEW(coefs,4); |
|||
coefs[0] := -19; |
|||
coefs[1] := 7; |
|||
coefs[2] := -4; |
|||
coefs[3] := 6; |
|||
Out.Int(Eval(coefs^,4,3),0);Out.Ln |
|||
END HornerRule. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|Objeck}}== |
|||
<syntaxhighlight lang="objeck"> |
|||
class Horner { |
|||
function : Main(args : String[]) ~ Nil { |
|||
coeffs := Collection.FloatVector->New(); |
|||
coeffs->AddBack(-19.0); |
|||
coeffs->AddBack(7.0); |
|||
coeffs->AddBack(-4.0); |
|||
coeffs->AddBack(6.0); |
|||
PolyEval(coeffs, 3)->PrintLine(); |
|||
} |
|||
function : PolyEval(coefficients : Collection.FloatVector , x : Float) ~ Float { |
|||
accumulator := coefficients->Get(coefficients->Size() - 1); |
|||
for(i := coefficients->Size() - 2; i > -1; i -= 1;) { |
|||
accumulator := (accumulator * x) + coefficients->Get(i); |
|||
}; |
|||
return accumulator; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|Objective-C}}== |
=={{header|Objective-C}}== |
||
{{works with|Mac OS X|10.6+}} Using blocks |
{{works with|Mac OS X|10.6+}} Using blocks |
||
< |
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h> |
||
typedef double (^mfunc)(double, double); |
typedef double (^mfunc)(double, double); |
||
Line 831: | Line 1,757: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Objeck}}== |
|||
<lang objeck> |
|||
class Horner { |
|||
function : Main(args : String[]) ~ Nil { |
|||
coeffs := Collection.FloatVector->New(); |
|||
coeffs->AddBack(-19.0); |
|||
coeffs->AddBack(7.0); |
|||
coeffs->AddBack(-4.0); |
|||
coeffs->AddBack(6.0); |
|||
PolyEval(coeffs, 3)->PrintLine(); |
|||
} |
|||
function : PolyEval(coefficients : Collection.FloatVector , x : Float) ~ Float { |
|||
accumulator := coefficients->Get(coefficients->Size() - 1); |
|||
for(i := coefficients->Size() - 2; i > -1; i -= 1;) { |
|||
accumulator := (accumulator * x) + coefficients->Get(i); |
|||
}; |
|||
return accumulator; |
|||
} |
|||
} |
|||
</lang> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang="ocaml"># let horner coeffs x = |
||
List.fold_left (fun acc coef -> acc * x + coef) 0 (List.rev coeffs) ;; |
List.fold_left (fun acc coef -> acc * x + coef) 0 (List.rev coeffs) ;; |
||
val horner : int list -> int -> int = <fun> |
val horner : int list -> int -> int = <fun> |
||
Line 864: | Line 1,767: | ||
# let coeffs = [-19; 7; -4; 6] in |
# let coeffs = [-19; 7; -4; 6] in |
||
horner coeffs 3 ;; |
horner coeffs 3 ;; |
||
- : int = 128</ |
- : int = 128</syntaxhighlight> |
||
It's also possible to do fold_right instead of reversing and doing fold_left; but fold_right is not tail-recursive. |
It's also possible to do fold_right instead of reversing and doing fold_left; but fold_right is not tail-recursive. |
||
=={{header|Octave}}== |
=={{header|Octave}}== |
||
< |
<syntaxhighlight lang="octave">function r = horner(a, x) |
||
r = 0.0; |
r = 0.0; |
||
for i = length(a):-1:1 |
for i = length(a):-1:1 |
||
Line 875: | Line 1,778: | ||
endfunction |
endfunction |
||
horner([-19, 7, -4, 6], 3)</ |
horner([-19, 7, -4, 6], 3)</syntaxhighlight> |
||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
< |
<syntaxhighlight lang="oorexx">/* Rexx --------------------------------------------------------------- |
||
* 04.03.2014 Walter Pachl |
* 04.03.2014 Walter Pachl |
||
*--------------------------------------------------------------------*/ |
*--------------------------------------------------------------------*/ |
||
Line 889: | Line 1,792: | ||
End |
End |
||
Say r |
Say r |
||
Say 6*x**3-4*x**2+7*x-19</ |
Say 6*x**3-4*x**2+7*x-19</syntaxhighlight> |
||
'''Output:''' |
'''Output:''' |
||
<pre>128 |
<pre>128 |
||
128</pre> |
128</pre> |
||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
< |
<syntaxhighlight lang="oz">declare |
||
fun {Horner Coeffs X} |
fun {Horner Coeffs X} |
||
{FoldL1 {Reverse Coeffs} |
{FoldL1 {Reverse Coeffs} |
||
Line 907: | Line 1,810: | ||
end |
end |
||
in |
in |
||
{Show {Horner [~19 7 ~4 6] 3}}</ |
{Show {Horner [~19 7 ~4 6] 3}}</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
Also note that Pari has a polynomial type. Evaluating these is as simple as <code>subst(P,variable(P),x)</code>. |
Also note that Pari has a polynomial type. Evaluating these is as simple as <code>subst(P,variable(P),x)</code>. |
||
< |
<syntaxhighlight lang="parigp">horner(v,x)={ |
||
my(s=0); |
my(s=0); |
||
forstep(i=#v,1,-1,s=s*x+v[i]); |
forstep(i=#v,1,-1,s=s*x+v[i]); |
||
s |
s |
||
};</ |
};</syntaxhighlight> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang="pascal">Program HornerDemo(output); |
||
function horner(a: array of double; x: double): double; |
function horner(a: array of double; x: double): double; |
||
Line 935: | Line 1,838: | ||
write ('Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: '); |
write ('Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: '); |
||
writeln (horner (poly, 3.0):8:4); |
writeln (horner (poly, 3.0):8:4); |
||
end.</ |
end.</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: 128.0000 |
<pre>Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: 128.0000 |
||
</pre> |
|||
=={{header|PascalABC.NET}}== |
|||
<syntaxhighlight lang="delphi"> |
|||
function Horner(coeffs: array of real; x: real): real; |
|||
begin |
|||
Result := 0; |
|||
foreach var coeff in coeffs.Reverse do |
|||
Result := Result * x + coeff |
|||
end; |
|||
begin |
|||
Print(Horner(|-19.0, 7, -4, 6|, 3)) |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
</pre> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use 5.10.0; |
||
use strict; |
use strict; |
||
use warnings; |
use warnings; |
||
Line 954: | Line 1,875: | ||
my @coeff = (-19.0, 7, -4, 6); |
my @coeff = (-19.0, 7, -4, 6); |
||
my $x = 3; |
my $x = 3; |
||
say horner @coeff, $x;</ |
say horner @coeff, $x;</syntaxhighlight> |
||
===<!-- Perl -->Functional version=== |
===<!-- Perl -->Functional version=== |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use List::Util qw(reduce); |
use List::Util qw(reduce); |
||
Line 967: | Line 1,888: | ||
my @coeff = (-19.0, 7, -4, 6); |
my @coeff = (-19.0, 7, -4, 6); |
||
my $x = 3; |
my $x = 3; |
||
print horner(\@coeff, $x), "\n";</ |
print horner(\@coeff, $x), "\n";</syntaxhighlight> |
||
===<!-- Perl -->Recursive version=== |
===<!-- Perl -->Recursive version=== |
||
< |
<syntaxhighlight lang="perl">sub horner { |
||
my ($coeff, $x) = @_; |
my ($coeff, $x) = @_; |
||
@$coeff and |
@$coeff and |
||
Line 976: | Line 1,897: | ||
} |
} |
||
print horner( [ -19, 7, -4, 6 ], 3 );</ |
print horner( [ -19, 7, -4, 6 ], 3 );</syntaxhighlight> |
||
=={{header|Perl 6}}== |
|||
<lang perl6>sub horner ( @coeffs, $x ) { |
|||
@coeffs.reverse.reduce: { $^a * $x + $^b }; |
|||
} |
|||
say horner( [ -19, 7, -4, 6 ], 3 );</lang> |
|||
A recursive version would spare us the need for reversing the list of coeffcients (and thus possibly allowing progressive evaluation with lazy lists?). However, special care must be taken in order to write it, because the way Perl 6 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.perl6.org/type/Pair Pairs] and the reduction meta-operator: |
|||
<lang perl6>multi horner(Numeric $c, $) { $c } |
|||
multi horner(Pair $c, $x) { |
|||
$c.key + $x * horner( $c.value, $x ) |
|||
} |
|||
print horner( [=>](-19, 7, -4, 6 ), 3 );</lang> |
|||
An other possibility would consist in creating a list of functions and chain them with a composition operator. |
|||
<math>\begin{align} |
|||
P(x) & = & c_0 + c_1 x + \ldots + c_n x^n\\ |
|||
& = & c_0 + x (c_1 + \ldots + c_n x^{n-1})\\ |
|||
& = & f_0(c_1 + \ldots + c_n x^{n-1})\\ |
|||
& = & f_0(f_1(c_2 + \ldots + c_n x^{n-2}))\\ |
|||
& = & (f_0 o f_1 o \ldots o f_n)(0) |
|||
\end{align}</math> |
|||
where <math>(f_n)</math> is a family of function such that: |
|||
<math>f_n(y) = c_n + x y</math> |
|||
The Horner rule can then be implemented without reversing the list of coefficients. It could then be applied to a potentially infinite list. |
|||
<lang perl6>sub infix:<o>(&f, &g) { -> $x { &f(&g($x)) } } |
|||
sub horner ( @c, $x ) { |
|||
[\o] map { -> $u { $_ + $x * $u } }, @c; |
|||
} |
|||
say map { .(0) }, horner( [ -19, 7, -4, 6 ], 3 ); |
|||
# compute progressive approximations of exp(2) |
|||
my @c := 1 X/ 1, [\*] 1 ... *; |
|||
say .(0) for horner( @c, 2 ); |
|||
</lang> |
|||
=={{header|Phix}}== |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<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: #004080;">atom</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coeff</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">coeff</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
128 |
|||
1 |
|||
</pre> |
|||
3 |
|||
5 |
|||
6.333333 |
|||
7 |
|||
7.266667 |
|||
7.355556 |
|||
7.380952 |
|||
7.387302 |
|||
^C</pre> |
|||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang="php"><?php |
||
function horner($coeff, $x) { |
function horner($coeff, $x) { |
||
$result = 0; |
$result = 0; |
||
Line 1,049: | Line 1,929: | ||
$x = 3; |
$x = 3; |
||
echo horner($coeff, $x), "\n"; |
echo horner($coeff, $x), "\n"; |
||
?></ |
?></syntaxhighlight> |
||
===Functional version=== |
===Functional version=== |
||
{{works with|PHP|5.3+}} |
{{works with|PHP|5.3+}} |
||
< |
<syntaxhighlight lang="php"><?php |
||
function horner($coeff, $x) { |
function horner($coeff, $x) { |
||
return array_reduce(array_reverse($coeff), function ($a, $b) use ($x) { return $a * $x + $b; }, 0); |
return array_reduce(array_reverse($coeff), function ($a, $b) use ($x) { return $a * $x + $b; }, 0); |
||
Line 1,061: | Line 1,941: | ||
$x = 3; |
$x = 3; |
||
echo horner($coeff, $x), "\n"; |
echo horner($coeff, $x), "\n"; |
||
?></ |
?></syntaxhighlight> |
||
=={{header|Picat}}== |
|||
===Recursion=== |
|||
<syntaxhighlight lang="picat">horner([],_X,0). |
|||
horner([H|T],X,V) :- |
|||
horner(T,X,V1), |
|||
V = V1 * X + H.</syntaxhighlight> |
|||
===Iterative=== |
|||
<syntaxhighlight lang="picat">horner2(Coeff, X, V) => |
|||
Acc = 0, |
|||
foreach(I in Coeff.length..-1..1) |
|||
Acc := Acc*X + Coeff[I] |
|||
end, |
|||
V = Acc.</syntaxhighlight> |
|||
===Functional approach=== |
|||
<syntaxhighlight lang="picat">h3(X,A,B) = A+B*X. |
|||
horner3(Coeff, X) = fold($h3(X),0,Coeff.reverse()).</syntaxhighlight> |
|||
===Test=== |
|||
<syntaxhighlight lang="picat">go => |
|||
horner([-19, 7, -4, 6], 3, V), |
|||
println(V), |
|||
horner2([-19, 7, -4, 6], 3, V2), |
|||
println(V2), |
|||
V3 = horner3([-19, 7, -4, 6], 3), |
|||
println(V3), |
|||
nl.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>128 |
|||
128 |
|||
128</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de horner (Coeffs X) |
||
(let Res 0 |
(let Res 0 |
||
(for C (reverse Coeffs) |
(for C (reverse Coeffs) |
||
(setq Res (+ C (* X Res))) ) ) )</ |
(setq Res (+ C (* X Res))) ) ) )</syntaxhighlight> |
||
< |
<syntaxhighlight lang="picolisp">: (horner (-19.0 7.0 -4.0 6.0) 3.0) |
||
-> 128</ |
-> 128</syntaxhighlight> |
||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
<syntaxhighlight lang="pl/i"> |
|||
<lang PL/I> |
|||
declare (i, n) fixed binary, (x, value) float; /* 11 May 2010 */ |
declare (i, n) fixed binary, (x, value) float; /* 11 May 2010 */ |
||
get (x); |
get (x); |
||
Line 1,085: | Line 2,001: | ||
put (value); |
put (value); |
||
end; |
end; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Potion}}== |
|||
<syntaxhighlight lang="potion">horner = (x, coef) : |
|||
result = 0 |
|||
coef reverse each (a) : |
|||
result = (result * x) + a |
|||
. |
|||
result |
|||
. |
|||
horner(3, (-19, 7, -4, 6)) print</syntaxhighlight> |
|||
=={{header|PowerShell}}== |
|||
{{works with|PowerShell|4.0}} |
|||
<syntaxhighlight lang="powershell"> |
|||
function horner($coefficients, $x) { |
|||
$accumulator = 0 |
|||
foreach($i in ($coefficients.Count-1)..0){ |
|||
$accumulator = ( $accumulator * $x ) + $coefficients[$i] |
|||
} |
|||
$accumulator |
|||
} |
|||
$coefficients = @(-19, 7, -4, 6) |
|||
$x = 3 |
|||
horner $coefficients $x |
|||
</syntaxhighlight> |
|||
<b>Output:</b> |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Tested with SWI-Prolog. Works with other dialects. |
Tested with SWI-Prolog. Works with other dialects. |
||
< |
<syntaxhighlight lang="prolog">horner([], _X, 0). |
||
horner([H|T], X, V) :- |
horner([H|T], X, V) :- |
||
horner(T, X, V1), |
horner(T, X, V1), |
||
V is V1 * X + H. |
V is V1 * X + H. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output : |
Output : |
||
< |
<syntaxhighlight lang="prolog"> ?- horner([-19, 7, -4, 6], 3, V). |
||
V = 128.</ |
V = 128.</syntaxhighlight> |
||
=== |
===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 |
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 |
||
< |
<syntaxhighlight lang="prolog">:- use_module(library(lambda)). |
||
Line 1,113: | Line 2,059: | ||
f_horner(L, V, R) :- |
f_horner(L, V, R) :- |
||
foldr(\X^Y^Z^(Z is X * V + Y), 0, L, R). |
foldr(\X^Y^Z^(Z is X * V + Y), 0, L, R). |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Functional syntax (Ciao)=== |
|||
Works with Ciao (https://github.com/ciao-lang/ciao) and the fsyntax package: |
|||
<syntaxhighlight lang="prolog"> |
|||
:- module(_, [horner/3], [fsyntax, hiord]). |
|||
:- use_module(library(hiordlib)). |
|||
horner(L, X) := ~foldr((''(H,V0,V) :- V is V0*X + H), L, 0). |
|||
</syntaxhighlight> |
|||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">Procedure Horner(List Coefficients(), b) |
||
Define result |
Define result |
||
ForEach Coefficients() |
ForEach Coefficients() |
||
Line 1,122: | Line 2,076: | ||
Next |
Next |
||
ProcedureReturn result |
ProcedureReturn result |
||
EndProcedure</ |
EndProcedure</syntaxhighlight> |
||
'''Implemented as |
'''Implemented as |
||
< |
<syntaxhighlight lang="purebasic">NewList a() |
||
AddElement(a()): a()= 6 |
AddElement(a()): a()= 6 |
||
AddElement(a()): a()= -4 |
AddElement(a()): a()= -4 |
||
AddElement(a()): a()= 7 |
AddElement(a()): a()= 7 |
||
AddElement(a()): a()=-19 |
AddElement(a()): a()=-19 |
||
Debug Horner(a(),3)</ |
Debug Horner(a(),3)</syntaxhighlight> |
||
'''Outputs |
'''Outputs |
||
128 |
128 |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">>>> def horner(coeffs, x): |
||
acc = 0 |
acc = 0 |
||
for c in reversed(coeffs): |
for c in reversed(coeffs): |
||
Line 1,142: | Line 2,096: | ||
>>> horner( (-19, 7, -4, 6), 3) |
>>> horner( (-19, 7, -4, 6), 3) |
||
128</ |
128</syntaxhighlight> |
||
===Functional version=== |
===Functional version=== |
||
< |
<syntaxhighlight lang="python">>>> try: from functools import reduce |
||
except: pass |
except: pass |
||
Line 1,152: | Line 2,106: | ||
>>> horner( (-19, 7, -4, 6), 3) |
>>> horner( (-19, 7, -4, 6), 3) |
||
128</ |
128</syntaxhighlight> |
||
==={{libheader|NumPy}}=== |
|||
<syntaxhighlight lang="python">>>> import numpy |
|||
>>> numpy.polynomial.polynomial.polyval(3, (-19, 7, -4, 6)) |
|||
128.0</syntaxhighlight> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
Procedural style: |
|||
<lang r>horner <- function(a, x) { |
|||
<syntaxhighlight lang="r">horner <- function(a, x) { |
|||
iv <- 0 |
|||
y <- 0 |
|||
for(i in length(a):1) { |
|||
for(c in rev(a)) { |
|||
iv <- iv * x + a[i] |
|||
y <- y * x + c |
|||
} |
} |
||
y |
|||
} |
} |
||
cat(horner(c(-19, 7, -4, 6), 3), "\n")</ |
cat(horner(c(-19, 7, -4, 6), 3), "\n")</syntaxhighlight> |
||
Functional style: |
|||
<syntaxhighlight lang="r">horner <- function(x, v) { |
|||
Reduce(v, right=T, f=function(a, b) { |
|||
b * x + a |
|||
}) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
> v <- c(-19, 7, -4, 6) |
|||
> horner(3, v) |
|||
[1] 128 |
|||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Translated from Haskell |
Translated from Haskell |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
(define (horner x l) |
(define (horner x l) |
||
Line 1,175: | Line 2,147: | ||
(horner 3 '(-19 7 -4 6)) |
(horner 3 '(-19 7 -4 6)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
<syntaxhighlight lang="raku" line>sub horner ( @coeffs, $x ) { |
|||
@coeffs.reverse.reduce: { $^a * $x + $^b }; |
|||
} |
|||
say horner( [ -19, 7, -4, 6 ], 3 );</syntaxhighlight> |
|||
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: |
|||
<syntaxhighlight lang="raku" line>multi horner(Numeric $c, $) { $c } |
|||
multi horner(Pair $c, $x) { |
|||
$c.key + $x * horner( $c.value, $x ) |
|||
} |
|||
say horner( [=>](-19, 7, -4, 6 ), 3 );</syntaxhighlight> |
|||
We can also use the composition operator: |
|||
<syntaxhighlight lang="raku" line>sub horner ( @coeffs, $x ) { |
|||
([o] map { $_ + $x * * }, @coeffs)(0); |
|||
} |
|||
say horner( [ -19, 7, -4, 6 ], 3 );</syntaxhighlight> |
|||
{{out}} |
|||
<pre>128</pre> |
|||
One advantage of using the composition operator is that it allows for the use of an infinite list of coefficients. |
|||
<syntaxhighlight lang="raku" line>sub horner ( @coeffs, $x ) { |
|||
map { .(0) }, [\o] map { $_ + $x * * }, @coeffs; |
|||
} |
|||
say horner( [ 1 X/ (1, |[\*] 1 .. *) ], i*pi )[20]; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>-0.999999999924349-5.28918515954219e-10i</pre> |
|||
=={{header|Rascal}}== |
=={{header|Rascal}}== |
||
< |
<syntaxhighlight lang="rascal">import List; |
||
public int horners_rule(list[int] coefficients, int x){ |
public int horners_rule(list[int] coefficients, int x){ |
||
Line 1,185: | Line 2,194: | ||
acc = acc * x + i;} |
acc = acc * x + i;} |
||
return acc; |
return acc; |
||
}</ |
}</syntaxhighlight> |
||
A neater and shorter solution using a reducer: |
A neater and shorter solution using a reducer: |
||
< |
<syntaxhighlight lang="rascal">public int horners_rule2(list[int] coefficients, int x) = (0 | it * x + c | c <- reverse(coefficients));</syntaxhighlight> |
||
Output: |
Output: |
||
< |
<syntaxhighlight lang="rascal">rascal>horners_rule([-19, 7, -4, 6], 3) |
||
int: 128 |
int: 128 |
||
rascal>horners_rule2([-19, 7, -4, 6], 3) |
rascal>horners_rule2([-19, 7, -4, 6], 3) |
||
int: 128</ |
int: 128</syntaxhighlight> |
||
=={{header|REBOL}}== |
|||
<syntaxhighlight lang="rebol">REBOL [] |
|||
=={{header|REXX}}== |
|||
<lang rexx>/*REXX program shows using Horner's rule for polynomial evaluation.*/ |
|||
numeric digits 30 /*use extra numeric precision. */ |
|||
parse arg x poly /*get value of X and coefficients*/ |
|||
equ= /*start with equation clean slate*/ |
|||
/*works for any degree equation. */ |
|||
do deg=0 until poly=='' /*get the equation's coefficients*/ |
|||
parse var poly c.deg poly /*get a equation coefficient.*/ |
|||
c.deg = (c.deg+0) / 1 /*normalize it (add 0, div by 1)*/ |
|||
if c.deg>=0 then c.deg = '+'c.deg /*if ¬ neg, then prefix a + sign.*/ |
|||
equ=equ c.deg /*concatenate it to the equation.*/ |
|||
if deg\==0 & c.deg\=0 then /*if not the first coefficient & */ |
|||
equ = equ'∙x^'deg /* not 0, append power (^) of X.*/ |
|||
equ = equ ' ' /*insert some blanks, look pretty*/ |
|||
end /*deg*/ |
|||
horner: func [coeffs x] [ |
|||
say ' x = ' x |
|||
result: 0 |
|||
say ' degree = ' deg |
|||
foreach i reverse coeffs [ |
|||
say ' equation = ' equ |
|||
result: (result * x) + i |
|||
a=c.deg |
|||
] |
|||
do j=deg by -1 for deg /*apply Horner's rule.*/ |
|||
return result |
|||
_ = j-1 |
|||
] |
|||
a = a*x + c._ |
|||
end /*j*/ |
|||
print horner [-19 7 -4 6] 3</syntaxhighlight> |
|||
say |
|||
say ' answer = ' a |
|||
=={{header|REXX}}== |
|||
/*stick a fork in it, we're done.*/</lang> |
|||
===version 1=== |
|||
'''output''' when the following is used for input: <tt> 3 -19 7 -4 6 </tt> |
|||
<syntaxhighlight lang="rexx">/*REXX program demonstrates using Horner's rule for polynomial evaluation. */ |
|||
numeric digits 30 /*use extra numeric precision. */ |
|||
parse arg x poly /*get value of X and the coefficients. */ |
|||
$= /*start with a clean slate equation. */ |
|||
do deg=0 until poly=='' /*get the equation's coefficients. */ |
|||
parse var poly c.deg poly; c.deg=c.deg/1 /*get equation coefficient & normalize.*/ |
|||
if c.deg>=0 then c.deg= '+'c.deg /*if ¬ negative, then prefix with a + */ |
|||
$=$ c.deg /*concatenate it to the equation. */ |
|||
if deg\==0 & c.deg\=0 then $=$'∙x^'deg /*¬1st coefficient & ¬0? Append X pow.*/ |
|||
$=$ ' ' /*insert some blanks, make it look nice*/ |
|||
end /*deg*/ |
|||
say ' x = ' x |
|||
say ' degree = ' deg |
|||
say ' equation = ' $ |
|||
a=c.deg /*A: is the accumulator (or answer). */ |
|||
do j=deg-1 by -1 for deg; a=a*x+c.j /*apply Horner's rule to the equations.*/ |
|||
end /*j*/ |
|||
say /*display a blank line for readability.*/ |
|||
say ' answer = ' a /*stick a fork in it, we're all done. */</syntaxhighlight> |
|||
'''output''' when the following is used for input: <tt> 3 -19 7 -4 6 </tt> |
|||
<pre> |
<pre> |
||
x = 3 |
x = 3 |
||
Line 1,230: | Line 2,246: | ||
answer = 128 |
answer = 128 |
||
</pre> |
|||
===version 2=== |
|||
<syntaxhighlight lang="rexx">/* REXX --------------------------------------------------------------- |
|||
* 27.07.2012 Walter Pachl |
|||
* coefficients reversed to descending order of power |
|||
* I'm used to x**2+x-3 |
|||
* equation formatting prettified (coefficients 1 and 0) |
|||
*--------------------------------------------------------------------*/ |
|||
Numeric Digits 30 /* use extra numeric precision. */ |
|||
Parse Arg x poly /* get value of x and coefficients*/ |
|||
rpoly='' |
|||
Do p=0 To words(poly)-1 |
|||
rpoly=rpoly word(poly,words(poly)-p) |
|||
End |
|||
poly=rpoly |
|||
equ='' /* start with equation clean slate*/ |
|||
deg=words(poly)-1 |
|||
pdeg=deg |
|||
Do Until deg<0 /* get the equation's coefficients*/ |
|||
Parse Var poly c.deg poly /* in descending order of powers */ |
|||
c.deg=c.deg+0 /* normalize it */ |
|||
If c.deg>0 & deg<pdeg Then /* positive and not first term */ |
|||
prefix='+' /* prefix a + sign. */ |
|||
Else prefix='' |
|||
Select |
|||
When deg=0 Then term=c.deg |
|||
When deg=1 Then |
|||
If c.deg=1 Then term='x' |
|||
Else term=c.deg'*x' |
|||
Otherwise |
|||
If c.deg=1 Then term='x^'deg |
|||
Else term=c.deg'*x^'deg |
|||
End |
|||
If c.deg<>0 Then /* build up the equation */ |
|||
equ=equ||prefix||term |
|||
deg=deg-1 |
|||
End |
|||
a=c.pdeg |
|||
Do p=pdeg To 1 By -1 /* apply Horner's rule. */ |
|||
pm1=p-1 |
|||
a=a*x+c.pm1 |
|||
End |
|||
Say ' x = ' x |
|||
Say ' degree = ' pdeg |
|||
Say ' equation = ' equ |
|||
Say ' ' |
|||
Say ' result = ' a</syntaxhighlight> |
|||
{{out}} |
|||
<pre> x = 3 |
|||
degree = 3 |
|||
equation = 6*x^3-4*x^2+7*x-19 |
|||
result = 128</pre> |
|||
=={{header|Ring}}== |
|||
<syntaxhighlight lang="ring"> |
|||
coefficients = [-19, 7, -4, 6] |
|||
see "x = 3" + nl + |
|||
"degree = 3" + nl + |
|||
"equation = 6*x^3-4*x^2+7*x-19" + nl + |
|||
"result = " + horner(coefficients, 3) + nl |
|||
func horner coeffs, x |
|||
w = 0 |
|||
for n = len(coeffs) to 1 step -1 |
|||
w = w * x + coeffs[n] |
|||
next |
|||
return w |
|||
</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
x = 3 |
|||
degree = 3 |
|||
equation = 6*x^3-4*x^2+7*x-19 |
|||
result = 128 |
|||
</pre> |
</pre> |
||
Line 1,239: | Line 2,331: | ||
This said, solution to the problem is |
This said, solution to the problem is |
||
<syntaxhighlight lang="rlab"> |
|||
<lang RLaB> |
|||
>> a = [6, -4, 7, -19] |
>> a = [6, -4, 7, -19] |
||
6 -4 7 -19 |
6 -4 7 -19 |
||
Line 1,247: | Line 2,339: | ||
128 |
128 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|RPL}}== |
|||
===Translation of the algorithm=== |
|||
Following the pseudocode given [https://web.physics.utah.edu/~detar/lessons/c++/array/node2.html here] to the letter: |
|||
≪ OVER DUP SIZE GET → a x0 p |
|||
≪ a SIZE 1 - 1 '''FOR''' j |
|||
'a(j)+x0*p' EVAL 'p' STO -1 '''STEP''' |
|||
p |
|||
≫ ≫ ‘'''HORNR'''’ STO |
|||
===Idiomatic one-liner=== |
|||
Reducing the loop to its simplest form: one memory call, one multiplication and one addition. |
|||
≪ → x0 ≪ LIST→ 2 SWAP '''START''' x0 * + '''NEXT''' ≫ ≫ ‘'''HORNR'''’ STO |
|||
{{in}} |
|||
<pre> |
|||
{ -19 7 -4 6 } 3 HORNR |
|||
</pre> |
|||
{{out}} |
|||
<pre> |
|||
1: 128 |
|||
</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">def horner(coeffs, x) |
||
coeffs.reverse.inject(0) {|acc, coeff| acc * x + coeff} |
coeffs.reverse.inject(0) {|acc, coeff| acc * x + coeff} |
||
end |
end |
||
p horner([-19, 7, -4, 6], 3) # ==> 128</ |
p horner([-19, 7, -4, 6], 3) # ==> 128</syntaxhighlight> |
||
=={{header|Rust}}== |
|||
<lang Rust>// rust 0.9-pre |
|||
fn horner(v: ~[f64], x: f64) -> f64 { |
|||
let mut accum = 0.0; |
|||
let vlen = v.len(); |
|||
for idx in range(0, vlen) { |
|||
accum = accum*x + v[vlen - idx - 1]; |
|||
}; |
|||
accum |
|||
} |
|||
fn main() { |
|||
let v : ~[f64] = ~[-19., 7., -4., 6.]; |
|||
println!("result: {}", horner(v, 3.0)); |
|||
}</lang> |
|||
Works with any number type. It uses a reversed left fold to accumulate the result, similar to the Haskell solution. |
|||
<lang Rust>// rust 0.9-pre |
|||
fn horner<T:Num>(cs:&[T], x:T) -> T { |
|||
cs.rev_iter().fold(std::num::zero::<T>(), |acc, c| (acc*x) + (*c)) |
|||
} |
|||
fn main() { |
|||
println!("{}", horner([-19, 7, -4, 6], 3)); |
|||
}</lang> |
|||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang="runbasic">coef$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in order |
||
x = 3 |
x = 3 |
||
print horner(coef$,x) '128 |
print horner(coef$,x) '128 |
||
Line 1,302: | Line 2,385: | ||
next |
next |
||
horner = accum |
horner = accum |
||
end function</ |
end function</syntaxhighlight> |
||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust">fn horner(v: &[f64], x: f64) -> f64 { |
|||
v.iter().rev().fold(0.0, |acc, coeff| acc*x + coeff) |
|||
} |
|||
fn main() { |
|||
let v = [-19., 7., -4., 6.]; |
|||
println!("result: {}", horner(&v, 3.0)); |
|||
}</syntaxhighlight> |
|||
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. |
|||
<syntaxhighlight lang="rust">extern crate num; // 0.2.0 |
|||
use num::Zero; |
|||
use std::ops::{Add, Mul}; |
|||
fn horner<Arr, Arg, Out>(v: &[Arr], x: Arg) -> Out |
|||
where |
|||
Arr: Clone, |
|||
Arg: Clone, |
|||
Out: Zero + Mul<Arg, Output = Out> + Add<Arr, Output = Out>, |
|||
{ |
|||
v.iter() |
|||
.rev() |
|||
.fold(Zero::zero(), |acc, coeff| acc * x.clone() + coeff.clone()) |
|||
} |
|||
fn main() { |
|||
let v = [-19., 7., -4., 6.]; |
|||
let output: f64 = horner(&v, 3.0); |
|||
println!("result: {}", output); |
|||
}</syntaxhighlight> |
|||
=={{header|Sather}}== |
=={{header|Sather}}== |
||
< |
<syntaxhighlight lang="sather">class MAIN is |
||
action(s, e, x:FLT):FLT is |
action(s, e, x:FLT):FLT is |
||
Line 1,319: | Line 2,434: | ||
#OUT + horner(|-19.0, 7.0, -4.0, 6.0|, 3.0) + "\n"; |
#OUT + horner(|-19.0, 7.0, -4.0, 6.0|, 3.0) + "\n"; |
||
end; |
end; |
||
end;</ |
end;</syntaxhighlight> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">def horner(coeffs:List[Double], x:Double)= |
||
coeffs.reverse.foldLeft(0.0){(a,c)=> a*x+c} |
coeffs.reverse.foldLeft(0.0){(a,c)=> a*x+c} |
||
</syntaxhighlight> |
|||
</lang> |
|||
< |
<syntaxhighlight lang="scala">val coeffs=List(-19.0, 7.0, -4.0, 6.0) |
||
println(horner(coeffs, 3)) |
println(horner(coeffs, 3)) |
||
-> 128.0 |
-> 128.0 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{Works with|Scheme|R<math>^5</math>RS}} |
{{Works with|Scheme|R<math>^5</math>RS}} |
||
< |
<syntaxhighlight lang="scheme">(define (horner lst x) |
||
(define (*horner lst x acc) |
(define (*horner lst x acc) |
||
(if (null? lst) |
(if (null? lst) |
||
Line 1,340: | Line 2,455: | ||
(display (horner (list -19 7 -4 6) 3)) |
(display (horner (list -19 7 -4 6) 3)) |
||
(newline)</ |
(newline)</syntaxhighlight> |
||
Output: |
Output: |
||
<lang>128</ |
<syntaxhighlight lang="text">128</syntaxhighlight> |
||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
include "float.s7i"; |
include "float.s7i"; |
||
Line 1,366: | Line 2,481: | ||
begin |
begin |
||
writeln(horner(coeffs, 3.0) digits 1); |
writeln(horner(coeffs, 3.0) digits 1); |
||
end func;</ |
end func;</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,372: | Line 2,487: | ||
128.0 |
128.0 |
||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
|||
Functional: |
|||
<syntaxhighlight lang="ruby">func horner(coeff, x) { |
|||
coeff.reverse.reduce { |a,b| a*x + b }; |
|||
} |
|||
say horner([-19, 7, -4, 6], 3); # => 128</syntaxhighlight> |
|||
Recursive: |
|||
<syntaxhighlight lang="ruby">func horner(coeff, x) { |
|||
(coeff.len > 0) \ |
|||
? (coeff[0] + x*horner(coeff.last(-1), x)) |
|||
: 0 |
|||
} |
|||
say horner([-19, 7, -4, 6], 3) # => 128</syntaxhighlight> |
|||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
{{works with|GNU Smalltalk}} |
{{works with|GNU Smalltalk}} |
||
< |
<syntaxhighlight lang="smalltalk">OrderedCollection extend [ |
||
horner: aValue [ |
horner: aValue [ |
||
^ self reverse inject: 0 into: [:acc :c | acc * aValue + c]. |
^ self reverse inject: 0 into: [:acc :c | acc * aValue + c]. |
||
Line 1,381: | Line 2,513: | ||
]. |
]. |
||
(#(-19 7 -4 6) asOrderedCollection horner: 3) displayNl.</ |
(#(-19 7 -4 6) asOrderedCollection horner: 3) displayNl.</syntaxhighlight> |
||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
< |
<syntaxhighlight lang="sml">(* Assuming real type for coefficients and x *) |
||
fun horner coeffList x = foldr (fn (a, b) => a + b * x) (0.0) coeffList</ |
fun horner coeffList x = foldr (fn (a, b) => a + b * x) (0.0) coeffList</syntaxhighlight> |
||
=={{header|Swift}}== |
|||
<syntaxhighlight lang="swift">func horner(coefs: [Double], x: Double) -> Double { |
|||
return reduce(lazy(coefs).reverse(), 0) { $0 * x + $1 } |
|||
} |
|||
println(horner([-19, 7, -4, 6], 3))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>128.0</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
proc horner {coeffs x} { |
proc horner {coeffs x} { |
||
set y 0 |
set y 0 |
||
Line 1,395: | Line 2,536: | ||
} |
} |
||
return $y |
return $y |
||
}</ |
}</syntaxhighlight> |
||
Demonstrating: |
Demonstrating: |
||
< |
<syntaxhighlight lang="tcl">puts [horner {-19 7 -4 6} 3]</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>128</pre> |
<pre>128</pre> |
||
Line 1,405: | Line 2,546: | ||
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. |
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. |
||
<syntaxhighlight lang="vba"> |
|||
<lang VBA> |
|||
Public Function Horner(x, ParamArray coeff()) |
Public Function Horner(x, ParamArray coeff()) |
||
Dim result As Double |
Dim result As Double |
||
Line 1,418: | Line 2,559: | ||
Horner = result |
Horner = result |
||
End Function |
End Function |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 1,424: | Line 2,565: | ||
print Horner(3, -19, 7, -4, 6) |
print Horner(3, -19, 7, -4, 6) |
||
128 |
128 |
||
</pre> |
|||
=={{header|VBScript}}== |
|||
<syntaxhighlight lang="vb"> |
|||
Function horners_rule(coefficients,x) |
|||
accumulator = 0 |
|||
For i = UBound(coefficients) To 0 Step -1 |
|||
accumulator = (accumulator * x) + coefficients(i) |
|||
Next |
|||
horners_rule = accumulator |
|||
End Function |
|||
WScript.StdOut.WriteLine horners_rule(Array(-19,7,-4,6),3) |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>128</pre> |
|||
=={{header|Visual Basic .NET}}== |
|||
{{trans|C#}} |
|||
<syntaxhighlight lang="vbnet">Module Module1 |
|||
Function Horner(coefficients As Double(), variable As Double) As Double |
|||
Return coefficients.Reverse().Aggregate(Function(acc, coeff) acc * variable + coeff) |
|||
End Function |
|||
Sub Main() |
|||
Console.WriteLine(Horner({-19.0, 7.0, -4.0, 6.0}, 3.0)) |
|||
End Sub |
|||
End Module</syntaxhighlight> |
|||
{{out}} |
|||
<pre>128</pre> |
|||
=={{header|Visual FoxPro}}== |
|||
===Coefficients in ascending order.=== |
|||
<syntaxhighlight lang="vfp"> |
|||
LOCAL x As Double |
|||
LOCAL ARRAY aCoeffs[1] |
|||
CLEAR |
|||
CREATE CURSOR coeffs (c1 I, c2 I, c3 I, c4 I) |
|||
INSERT INTO coeffs VALUES (-19,7,-4,6) |
|||
SCATTER TO aCoeffs |
|||
x = VAL(INPUTBOX("Value of x:", "Value")) |
|||
? EvalPoly(@aCoeffs, x) |
|||
USE IN coeffs |
|||
FUNCTION EvalPoly(c, x As Double) As Double |
|||
LOCAL s As Double, k As Integer, n As Integer |
|||
n = ALEN(c) |
|||
s = 0 |
|||
FOR k = n TO 1 STEP -1 |
|||
s = s*x + c[k] |
|||
ENDFOR |
|||
RETURN s |
|||
ENDFUNC |
|||
</syntaxhighlight> |
|||
===Coefficients in descending order.=== |
|||
<syntaxhighlight lang="vfp"> |
|||
LOCAL x As Double |
|||
LOCAL ARRAY aCoeffs[1] |
|||
CLEAR |
|||
CREATE CURSOR tmp (c1 I, c2 I, c3 I, c4 I) |
|||
INSERT INTO tmp VALUES (6,-4,7,-19) |
|||
SCATTER TO aCoeffs |
|||
x = VAL(INPUTBOX("Value of x:", "Value")) |
|||
? EvalPolyDesc(@aCoeffs, x) |
|||
USE IN tmp |
|||
FUNCTION EvalPolyDesc(c, x As Double) As Double |
|||
LOCAL s As Double, e |
|||
s = 0 |
|||
FOR EACH e IN c FOXOBJECT |
|||
s = s*x + e |
|||
ENDFOR |
|||
RETURN s |
|||
ENDFUNC |
|||
</syntaxhighlight> |
|||
=={{header|V (Vlang)}}== |
|||
<syntaxhighlight lang="v (vlang)">fn horner(x i64, c []i64) i64 { |
|||
mut acc := i64(0) |
|||
for i := c.len - 1; i >= 0; i-- { |
|||
acc = acc*x + c[i] |
|||
} |
|||
return acc |
|||
} |
|||
fn main() { |
|||
println(horner(3, [i64(-19), 7, -4, 6])) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
<syntaxhighlight lang="wren">var horner = Fn.new { |x, c| |
|||
var count = c.count |
|||
if (count == 0) return 0 |
|||
return (count-1..0).reduce(0) { |acc, index| acc*x + c[index] } |
|||
} |
|||
System.print(horner.call(3, [-19, 7, -4, 6]))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
128 |
|||
</pre> |
</pre> |
||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">code IntOut=11; |
||
func Horner(X, N, C); \Return value of polynomial in X |
func Horner(X, N, C); \Return value of polynomial in X |
||
Line 1,438: | Line 2,689: | ||
]; |
]; |
||
IntOut(0, Horner(3, 4, [-19, 7, -4, 6]));</ |
IntOut(0, Horner(3, 4, [-19, 7, -4, 6]));</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
128 |
|||
</pre> |
|||
=={{header|zkl}}== |
|||
<syntaxhighlight lang="zkl">fcn horner(coeffs,x) |
|||
{ coeffs.reverse().reduce('wrap(a,coeff){ a*x + coeff },0.0) }</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
horner(T(-19,7,-4,6), 3).println(); |
|||
128 |
128 |
||
</pre> |
</pre> |
Latest revision as of 06:10, 12 August 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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.
11l
F horner(coeffs, x)
V acc = 0
L(c) reversed(coeffs)
acc = acc * x + c
R acc
print(horner([-19, 7, -4, 6], 3))
- Output:
128
360 Assembly
* Horner's rule for polynomial evaluation - 07/10/2015
HORNER CSECT
USING HORNER,R15 set base register
SR R5,R5 accumulator=0
LA R2,N i=number_of_coeff
LOOP M R4,X accumulator=accumulator*x
LR R1,R2 i
SLA R1,2 i*4
L R3,COEF-4(R1) coef(i)
AR R5,R3 accumulator=accumulator+coef(i)
BCT R2,LOOP i=i-1; loop n times
XDECO R5,PG edit accumulator
XPRNT PG,12 print buffer
XR R15,R15 set return code
BR R14 return to caller
COEF DC F'-19',F'7',F'-4',F'6' <== input values
X DC F'3' <== input value
N EQU (X-COEF)/4 number of coefficients
PG DS CL12 buffer
YREGS
END HORNER
- Output:
128
ACL2
(defun horner (ps x)
(if (endp ps)
0
(+ (first ps)
(* x (horner (rest ps) x)))))
Action!
INT FUNC Horner(INT ARRAY coeffs INT count,x)
INT v,i
v=0 i=count-1
WHILE i>=0
DO
v=v*x+coeffs(i)
i==-1
OD
RETURN (v)
PROC Main()
INT ARRAY coeffs=[65517 7 65532 6]
INT res,x=[3],i,count=[4]
PrintF("x=%I%E",x)
FOR i=0 TO count-1
DO
PrintI(coeffs(i))
IF i=1 THEN
Print("x")
ELSEIF i>1 THEN
PrintF("x^%I",i)
FI
IF i<count-1 AND coeffs(i+1)>=0 THEN
Print("+")
FI
OD
res=Horner(coeffs,4,x)
PrintF("=%I%E",res)
RETURN
- Output:
Screenshot from Atari 8-bit computer
x=3 -19+7x-4x^2+6x^3=128
Ada
with Ada.Float_Text_IO; use Ada.Float_Text_IO;
procedure Horners_Rule is
type Coef is array(Positive range <>) of Float;
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(Coeffs => (-19.0, 7.0, -4.0, 6.0), Val => 3.0), Aft=>1, Exp=>0);
end Horners_Rule;
Output:
128.0
Aime
real
horner(list coeffs, real x)
{
real c, z;
z = 0;
for (, c of coeffs) {
z *= x;
z += c;
}
z;
}
integer
main(void)
{
o_(horner(list(-19r, 7.0, -4r, 6r), 3), "\n");
0;
}
ALGOL 68
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) )
)
ALGOL W
begin
% Horner's rule for polynominal evaluation %
% returns the value of the polynominal defined by coefficients, %
% at the point x. The number of coefficients must be in ub %
% the coefficients should be in order with x^0 first, x^n last %
real procedure Horner( real array coefficients ( * )
; integer value ub
; real value x
) ;
begin
real xValue;
xValue := 0;
for i := ub step -1 until 1 do xValue := ( xValue * x ) + coefficients( i );
xValue
end Horner ;
% task test case %
begin
real array coefficients ( 1 :: 4 );
integer cPos;
cPos := 1;
for i := -19, 7, -4, 6 do begin
coefficients( cPos ) := i;
cPos := cPos + 1
end for_i ;
write( r_format := "A", r_w := 8, r_d := 2, Horner( coefficients, 4, 3 ) )
end test_cases
end.
- Output:
128.00
APL
Works in Dyalog APL
h←⊥∘⌽
- Output:
3 h ¯19 7 ¯4 6 128
ATS
#include
"share/atspre_staload.hats"
fun
horner
(
x: int, cs: List int
) : int = let
//
implement
list_foldright$fopr<int><int> (a, b) = a + b * x
//
in
list_foldright<int><int> (cs, 0)
end // end of [horner]
implement
main0 () = let
val x = 3
val cs = $list{int}(~19, 7, ~4, 6)
val res = horner (x, cs)
in
println! (res)
end // end of [main0]
Arturo
horner: function [coeffs, x][
result: 0
loop reverse coeffs 'c ->
result: c + result * x
return result
]
print horner @[neg 19, 7, neg 4, 6] 3
- Output:
128
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
}
Message box shows:
128
AWK
#!/usr/bin/awk -f
function horner(x, A) {
acc = 0;
for (i = length(A); 0<i; i--) {
acc = acc*x + A[i];
}
return acc;
}
BEGIN {
split(p,P);
print horner(x,P);
}
- Output:
awk -v X=3 -v p="-19 7 -4 6" -f horner.awk 128
BASIC
Applesoft BASIC
100 HOME : REM 100 CLS for Chipmunk Basic and GW-BASIC
100 CLS : REM 100 HOME for Applesoft BASIC
110 X = 3
120 DIM COEFFS(3)
130 COEFFS(0) = -19
140 COEFFS(1) = 7
150 COEFFS(2) = -4
160 COEFFS(3) = 6
170 PRINT "Horner's algorithm for the polynomial "
180 PRINT "6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: ";
190 ACCUM = 0
200 FOR I = 3 TO 0 STEP -1
210 ACCUM = (ACCUM*X)+COEFFS(I)
220 NEXT I
230 PRINT ACCUM
240 END
BASIC256
x = 3
dim coeficientes = {-19, 7, -4, 6}
print "Horner's algorithm for the polynomial ";
print "6*x^3 - 4*x^2 + 7*x - 19 when x = 3: ";
print AlgoritmoHorner(coeficientes, x)
end
function AlgoritmoHorner(coeffs, x)
acumulador = 0
for i = coeffs[?]-1 to 0 step -1
acumulador = (acumulador * x) + coeffs[i]
next i
return acumulador
end function
- Output:
Same as FreeBASIC entry.
Chipmunk Basic
100 CLS
110 x = 3
120 DIM coeffs(3)
130 coeffs(0) = -19
140 coeffs(1) = 7
150 coeffs(2) = -4
160 coeffs(3) = 6
170 PRINT "Horner's algorithm for the polynomial "
180 PRINT "6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: ";
190 accum = 0
200 FOR i = UBOUND(coeffs,1) TO 0 STEP -1
210 accum = (accum*x)+coeffs(i)
220 NEXT i
230 PRINT accum
240 END
- Output:
Horner's algorithm for the polynomial 6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: 128
Gambas
Public coeficientes As New Integer[4]
Public Function AlgoritmoHorner(coeficientes As Integer[], x As Integer) As Integer
coeficientes[0] = -19
coeficientes[1] = 7
coeficientes[2] = -4
coeficientes[3] = 6
Dim i As Integer, acumulador As Integer = 0
For i = coeficientes.Count - 1 To 0 Step -1
acumulador = (acumulador * x) + coeficientes[i]
Next
Return acumulador
End Function
Public Sub Main()
Dim x As Integer = 3
Print "Horner's algorithm for the polynomial 6*x^3 - 4*x^2 + 7*x - 19 when x = 3: ";
Print AlgoritmoHorner(coeficientes, x)
End
- Output:
Same as FreeBASIC entry.
GW-BASIC
100 CLS : REM 100 HOME for Applesoft BASIC
110 X = 3
120 DIM COEFFS(3)
130 COEFFS(0) = -19
140 COEFFS(1) = 7
150 COEFFS(2) = -4
160 COEFFS(3) = 6
170 PRINT "Horner's algorithm for the polynomial "
180 PRINT "6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: ";
190 ACCUM = 0
200 FOR I = 3 TO 0 STEP -1
210 ACCUM = (ACCUM*X)+COEFFS(I)
220 NEXT I
230 PRINT ACCUM
240 END
- Output:
Same as Chipmunk Basic entry.
Minimal BASIC
20 LET X = 3
30 DIM C(3)
40 LET C(0) = -19
50 LET C(1) = 7
60 LET C(2) = -4
70 LET C(3) = 6
80 PRINT "HORNER'S ALGORITHM FOR THE POLYNOMIAL"
90 PRINT "6*X^3 - 4*X^2 + 7*X - 19 WHEN X = 3 : ";
100 LET A = 0
110 FOR I = 3 TO 0 STEP -1
120 LET A = (A*X)+C(I)
130 NEXT I
140 PRINT A
150 END
- Output:
Same as Chipmunk Basic entry.
MSX Basic
The Minimal BASIC solution works without any changes.
QBasic
FUNCTION Horner (coeffs(), x)
acumulador = 0
FOR i = UBOUND(coeffs) TO LBOUND(coeffs) STEP -1
acumulador = (acumulador * x) + coeffs(i)
NEXT i
Horner = acumulador
END FUNCTION
x = 3
DIM coeffs(3)
DATA -19, 7, -4, 6
FOR a = LBOUND(coeffs) TO UBOUND(coeffs)
READ coeffs(a)
NEXT a
PRINT "Horner's algorithm for the polynomial 6*x^3 - 4*x^2 + 7*x - 19 when x = 3 is: ";
PRINT Horner(coeffs(), x)
END
Quite BASIC
The Minimal BASIC solution works without any changes.
Yabasic
x = 3
dim coeffs(4)
coeffs(0) = -19
coeffs(1) = 7
coeffs(2) = -4
coeffs(3) = 6
print "Horner's algorithm for the polynomial ";
print "6*x^3 - 4*x^2 + 7*x - 19 when x = 3: ";
print AlgoritmoHorner(coeffs, x)
end
sub AlgoritmoHorner(coeffs, x)
local acumulador, i
acumulador = 0
for i = arraysize(coeffs(),1) to 0 step -1
acumulador = (acumulador * x) + coeffs(i)
next i
return acumulador
end sub
- Output:
Same as FreeBASIC entry.
Batch File
@echo off
call:horners a:-19 b:7 c:-4 d:6 x:3
call:horners x:3 a:-19 c:-4 d:6 b:7
pause>nul
exit /b
:horners
setlocal enabledelayedexpansion
set a=0
set b=0
set c=0
set d=0
set x=0
for %%i in (%*) do (
for /f "tokens=1,2 delims=:" %%j in ("%%i") do (
set %%j=%%k
)
)
set /a return=((((0)*%x%+%d%)*%x%+(%c%))*%x%+%b%)*%x%+(%a%)
echo %return%
exit /b
- Output:
>a:-19 b:7 c:-4 d:6 x:3 128 >x:3 a:-19 c:-4 d:6 b:7 128
BBC BASIC
DIM coefficients(3)
coefficients() = -19, 7, -4, 6
PRINT FNhorner(coefficients(), 3)
END
DEF FNhorner(coeffs(), x)
LOCAL i%, v
FOR i% = DIM(coeffs(), 1) TO 0 STEP -1
v = v * x + coeffs(i%)
NEXT
= v
Bracmat
( ( Horner
= accumulator coefficients x coeff
. !arg:(?coefficients.?x)
& 0:?accumulator
& whl
' ( !coefficients:?coefficients #%@?coeff
& !accumulator*!x+!coeff:?accumulator
)
& !accumulator
)
& Horner$(-19 7 -4 6.3)
);
Output:
128
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;
}
C#
using System;
using System.Linq;
class Program
{
static double Horner(double[] coefficients, double variable)
{
return coefficients.Reverse().Aggregate(
(accumulator, coefficient) => accumulator * variable + coefficient);
}
static void Main()
{
Console.WriteLine(Horner(new[] { -19.0, 7.0, -4.0, 6.0 }, 3.0));
}
}
Output:
128
C++
The same C function works too, but another solution could be:
#include <iostream>
#include <vector>
using namespace std;
double horner(vector<double> v, double x)
{
double s = 0;
for( vector<double>::const_reverse_iterator i = v.rbegin(); i != v.rend(); i++ )
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;
}
Yet another solution, which is more idiomatic in C++ and works on any bidirectional sequence:
#include <iostream>
template<typename BidirIter>
double horner(BidirIter begin, BidirIter end, double x)
{
double result = 0;
while (end != begin)
result = result*x + *--end;
return result;
}
int main()
{
double c[] = { -19, 7, -4, 6 };
std::cout << horner(c, c + 4, 3) << std::endl;
}
Clojure
(defn horner [coeffs x]
(reduce #(-> %1 (* x) (+ %2)) (reverse coeffs)))
(println (horner [-19 7 -4 6] 3))
CoffeeScript
eval_poly = (x, coefficients) ->
# coefficients are for ascending powers
return 0 if coefficients.length == 0
ones_place = coefficients.shift()
x * eval_poly(x, coefficients) + ones_place
console.log eval_poly 3, [-19, 7, -4, 6] # 128
console.log eval_poly 10, [4, 3, 2, 1] # 1234
console.log eval_poly 2, [1, 1, 0, 0, 1] # 19
Common Lisp
(defun horner (coeffs x)
(reduce #'(lambda (coef acc) (+ (* acc x) coef))
coeffs :from-end t :initial-value 0))
Alternate version using LOOP. Coefficients are passed in a vector.
(defun horner (x a)
(loop :with y = 0
:for i :from (1- (length a)) :downto 0
:do (setf y (+ (aref a i) (* y x)))
:finally (return y)))
(horner 1.414 #(-2 0 1))
D
The poly() function of the standard library std.math module uses Horner's rule:
void main() {
void main() {
import std.stdio, std.math;
double x = 3.0;
static real[] pp = [-19,7,-4,6];
poly(x,pp).writeln;
}
}
Basic implementation:
import std.stdio, std.traits;
CommonType!(U, V) horner(U, V)(U[] p, V x) pure nothrow @nogc {
typeof(return) accumulator = 0;
foreach_reverse (c; p)
accumulator = accumulator * x + c;
return accumulator;
}
void main() {
[-19, 7, -4, 6].horner(3.0).writeln;
}
More functional style:
import std.stdio, std.algorithm, std.range;
auto horner(T, U)(in T[] p, in U x) pure nothrow @nogc {
return reduce!((a, b) => a * x + b)(U(0), p.retro);
}
void main() {
[-19, 7, -4, 6].horner(3.0).writeln;
}
Delphi
function EvaluatePolynomial(Args: array of double; X: double): double;
{Evaluate polynomial using Horner's rule }
var I: integer;
begin
Result:=0;
for I:=High(Args) downto 0 do
Result:=(Result * X ) + Args[I];
end;
function GetPolynomialStr(Args: array of double; VarName: string): string;
{Return a string display the polynomial in normal format}
{for example: 6.0 X^3 - 4.0 X^2 + 7.0 X - 19.0}
var I: integer;
begin
Result:='';
for I:=High(Args) downto 0 do
begin
if Args[I]>0 then
begin
if I<>High(Args) then Result:=Result+' + ';
end
else Result:=Result+' - ';
Result:=Result+FloatToStrF(Abs(Args[I]),ffFixed,18,1);
if I>0 then Result:=Result+' '+VarName;
if I>1 then Result:=Result+'^'+IntToStr(I);
end;
end;
procedure ShowHornerPoly(Memo: TMemo; Args: array of double; X: double);
{Evaluate polynomial, show formated polynomal and the result}
var R: double;
begin
R:=EvaluatePolynomial(Args,X);
Memo.Lines.Add(FloatToStrF(R,ffFixed, 18,1));
Memo.Lines.Add(GetPolynomialStr(Args,'X'));
end;
procedure DoHornerPoly(Memo: TMemo);
begin
ShowHornerPoly(Memo,[-19, 7, -4, 6],3)
end;
- Output:
128.0 6.0 X^3 - 4.0 X^2 + 7.0 X - 19.0
E
def makeHornerPolynomial(coefficients :List) {
def indexing := (0..!coefficients.size()).descending()
return def hornerPolynomial(x) {
var acc := 0
for i in indexing {
acc := acc * x + coefficients[i]
}
return acc
}
}
? makeHornerPolynomial([-19, 7, -4, 6])(3)
# value: 128
EasyLang
func horner coeffs[] x .
for i = len coeffs[] downto 1
res = res * x + coeffs[i]
.
return res
.
print horner [ -19 7 -4 6 ] 3
- Output:
128
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.
(define P '(-19 7 -4 6))
(poly->string 'x P) → 6x^3 -4x^2 +7x -19
(poly 3 P) → 128
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"),
to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.]
[Horner's rule for polynomial evaluation on EDSAC by Erik Sargsyan]
[EDSAC program, Initial Orders 2]
T 56 K
GK
[0] A 3 F
[1] T 9 F
[2] A 4 F [loading the address of the 1st array element into the accumulator]
[3] A 14 @ [add an instruction code with a zero address field]
[4] T 14 @ [writing the generated instruction, zeroing the accumulator]
[5 loop] A 1 F [load the counter of unprocessed array elements into the accumulator]
[6] S 21 @ [Subtract the constant = 1]
[7] E 10 @ [if (acc >= 0) goto 10 else end]
[8] T 300 F [zeroing the accumulator]
[9] E 0 F [breakpoint, end of program]
[10] T 1 F [update the counter value and reset the accumulator]
[11] V 2 F [multiplying the number in cell 2 by the number in the multiplier register]
[12] L 1024 F [shift the number in the accumulator 12 bits to the left]
[13] L 4 F [shift the number in the accumulator 4 bits to the left]
[14 r1] A 0 F [loading the value from cell 0 into the accumulator]
[15] T 2 F [writing this value to the working cell, zeroing the accumulator]
[16] A 21 @ [loading into accumulator constant value = 1]
[17] L 0 D [shift the number in the accumulator 1 bit to the left]
[18] A 14 @ [add the code of the instruction executed in the previous step]
[19] T 14 @ [write the generated instruction into memory]
[20] E 5 @ [repeat all operations; accumulator zeroed]
[21 const 1] P 0 D [1]
GK
[0] H 10 @ [writing X0 to the multiplier register]
[1] A 11 @ [loading into the accumulator of the degree of the polynomial]
[2] T 1 F [writing the degree of a polynomial in cell 1]
[3] A 13 @ [loading the leading coefficient into the accumulator]
[4] T 2 F [writing the senior coefficient to the working cell 2]
[5] A 12 @ [loading the address of the 1st array element into the accumulator]
[6] T 4 F [writing the address of the 1st element of the array]
[7] A 7 @ [\ call]
[8] G 56 F
[9] Z 0 F
[10] P 3 F [X0 is a fixed value of X, by which we calculate the value of the polynomial]
[11 power] P 2 F [polynomial degree times 2]
[12 addr] P 14 @ [address of the 1st element of the array]
[13] P 3 F [a4 = 6]
[14] P 8 D [a3 = 17]
[15] P 9 F [a2 = 18]
[16] P 12 D [a1 = 25]
[17] P 316 F [a0 = 632]
EZPF
- Output:
Cell 2 will contain the number 12878
Elena
ELENA 5.0 :
import extensions;
import system'routines;
horner(coefficients,variable)
{
^ coefficients.clone().sequenceReverse().accumulate(new Real(),(accumulator,coefficient => accumulator * variable + coefficient))
}
public program()
{
console.printLine(horner(new real[]{-19.0r, 7.0r, -4.0r, 6.0r}, 3.0r))
}
- Output:
128.0
Elixir
horner = fn(list, x)-> List.foldr(list, 0, fn(c,acc)-> x*acc+c end) end
IO.puts horner.([-19,7,-4,6], 3)
- Output:
128
Emacs Lisp
(require 'cl-lib)
(defun horner (coeffs x)
(cl-reduce #'(lambda (coef acc) (+ (* acc x) coef))
coeffs :from-end t :initial-value 0))
(horner '(-19 7 -4 6) 3)
- Output:
128
Erlang
horner(L,X) ->
lists:foldl(fun(C, Acc) -> X*Acc+C end,0, lists:reverse(L)).
t() ->
horner([-19,7,-4,6], 3).
ERRE
PROGRAM HORNER
! 2 3
! polynomial is -19+7x-4x +6x
!
DIM C[3]
PROCEDURE HORNER(C[],X->RES)
LOCAL I%,V
FOR I%=UBOUND(C,1) TO 0 STEP -1 DO
V=V*X+C[I%]
END FOR
RES=V
END PROCEDURE
BEGIN
C[]=(-19,7,-4,6)
HORNER(C[],3->RES)
PRINT(RES)
END PROGRAM
Euler Math Toolbox
>function horner (x,v) ...
$ n=cols(v); res=v{n};
$ loop 1 to n-1; res=res*x+v{n-#}; end;
$ return res
$endfunction
>v=[-19,7,-4,6]
[ -19 7 -4 6 ]
>horner(2,v) // test Horner
27
>evalpoly(2,v) // built-in Horner
27
>horner(I,v) // complex values
-15+1i
>horner(1±0.05,v) // interval values
~-10.9,-9.11~
>function p(x) &= sum(@v[k]*x^(k-1),k,1,4) // Symbolic Polynomial
3 2
6 x - 4 x + 7 x - 19
F#
let horner l x =
List.rev l |> List.fold ( fun acc c -> x*acc+c) 0
horner [-19;7;-4;6] 3
Factor
: horner ( coeff x -- res )
[ <reversed> 0 ] dip '[ [ _ * ] dip + ] reduce ;
( scratchpad ) { -19 7 -4 6 } 3 horner . 128
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.
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 (0:), intent (in) :: coeffs
real, intent (in) :: x
real :: res
integer :: i
res = coeffs(ubound(coeffs,1))
do i = ubound(coeffs,1)-1, 0, -1
res = res * x + coeffs (i)
end do
end function horner
end program test_horner
Output:
128.0
Fortran 77
FUNCTION HORNER(N,A,X)
IMPLICIT NONE
INTEGER I,N
DOUBLE PRECISION A(N),X,Y,HORNER
Y = A(N)
DO I = N - 1,1,-1
Y = Y*X + A(I)
END DO
HORNER=Y
END
As a matter of fact, computing the derivative is not much more difficult (see Roundoff in Polynomial Evaluation, W. Kahan, 1986). The following subroutine computes both polynomial value and derivative for argument x.
SUBROUTINE HORNER2(N,A,X,Y,Z)
C COMPUTE POLYNOMIAL VALUE AND DERIVATIVE
C SEE "ROUNDOFF IN POLYNOMIAL EVALUATION", W. KAHAN, 1986
C POLY: A(1) + A(2)*X + ... + A(N)*X**(N-1)
C Y: VALUE, Z: DERIVATIVE
IMPLICIT NONE
INTEGER I,N
DOUBLE PRECISION A(N),X,Y,Z
Z = 0.0D0
Y = A(N)
DO 10 I = N - 1,1,-1
Z = Z*X + Y
10 Y = Y*X + A(I)
END
FreeBASIC
Function AlgoritmoHorner(coeffs() As Integer, x As Integer) As Integer
Dim As Integer i, acumulador = 0
For i = Ubound(coeffs, 1) To 0 Step -1
acumulador = (acumulador * x) + coeffs(i)
Next i
Return acumulador
End Function
Dim As Integer x = 3
Dim As Integer coeficientes(3) = {-19, 7, -4, 6}
Print "Algoritmo de Horner para el polinomio 6*x^3 - 4*x^2 + 7*x - 19 para x = 3: ";
Print AlgoritmoHorner(coeficientes(), x)
End
- Output:
Algoritmo de Horner para el polinomio 6*x^3 - 4*x^2 + 7*x - 19 para x = 3: 128
FunL
import lists.foldr
def horner( poly, x ) = foldr( \a, b -> a + b*x, 0, poly )
println( horner([-19, 7, -4, 6], 3) )
- Output:
128
FutureBasic
include "NSLog.incl"
local fn horner( coeffs as CFArrayRef, x as NSInteger ) as double
CFArrayRef reversedCoeffs
CFNumberRef num
double accumulator = 0.0
// Reverse coeffs array
reversedCoeffs = fn EnumeratorAllObjects( fn ArrayReverseObjectEnumerator( coeffs ) )
// Iterate over CFNumberRefs in reversed array, convert to double values, calculate and add to accumulator
for num in reversedCoeffs
accumulator = ( accumulator * x ) + fn NumberDoubleValue( num )
next
end fn = accumulator
CFArrayRef coeffs
coeffs = @[@-19.0, @7.0, @-4.0, @6.0]
NSLog( @"%7.1f", fn horner( coeffs, 3 ) )
coeffs = @[@4.0, @3.0, @2.0, @1.0]
NSLog( @"%7.1f", fn horner( coeffs, 10 ) )
coeffs = @[@1, @1, @0, @0, @1]
NSLog( @"%7.1f", fn horner( coeffs, 2 ) )
coeffs = @[@1.2, @2.3, @3.4, @4.5, @5.6]
NSLog( @"%7.1f", fn horner( coeffs, 8 ) )
coeffs = @[@1, @0, @1, @1, @1, @0, @0, @1]
NSLog( @"%7.1f", fn horner( coeffs, 2 ) )
HandleEvents
- Output:
128.0 1234.0 19.0 25478.8 157.0
GAP
# The idiomatic way to compute with polynomials
x := Indeterminate(Rationals, "x");
# This is a value in a polynomial ring, not a function
p := 6*x^3 - 4*x^2 + 7*x - 19;
Value(p, 3);
# 128
u := CoefficientsOfUnivariatePolynomial(p);
# [ -19, 7, -4, 6 ]
# One may also create the polynomial from coefficients
q := UnivariatePolynomial(Rationals, [-19, 7, -4, 6], x);
# 6*x^3-4*x^2+7*x-19
p = q;
# true
# Now a Horner implementation
Horner := function(coef, x)
local v, c;
v := 0;
for c in Reversed(coef) do
v := x*v + c;
od;
return v;
end;
Horner(u, 3);
# 128
Go
package main
import "fmt"
func horner(x int64, c []int64) (acc int64) {
for i := len(c) - 1; i >= 0; i-- {
acc = acc*x + c[i]
}
return
}
func main() {
fmt.Println(horner(3, []int64{-19, 7, -4, 6}))
}
Output:
128
Groovy
Solution:
def hornersRule = { coeff, x -> coeff.reverse().inject(0) { accum, c -> (accum * x) + c } }
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.
def coefficients = [-19g, 7g, -4g, 6g]
println (["p coefficients":coefficients])
def testPoly = hornersRule.curry(coefficients)
println (["p(3)":testPoly(3g)])
println (["p(0)":testPoly(0g)])
def derivativeCoefficients = { coeff -> (1..<(coeff.size())).collect { coeff[it] * it } }
println (["p' coefficients":derivativeCoefficients(coefficients)])
def testDeriv = hornersRule.curry(derivativeCoefficients(coefficients))
println (["p'(3)":testDeriv(3g)])
println (["p'(0)":testDeriv(0g)])
def newtonRaphson = { x, f, fPrime ->
while (f(x).abs() > 0.0001) {
x -= f(x)/fPrime(x)
}
x
}
def root = newtonRaphson(3g, testPoly, testDeriv)
println ([root:root.toString()[0..5], "p(root)":testPoly(root).toString()[0..5], "p'(root)":testDeriv(root).toString()[0..5]])
Output:
[p coefficients:[-19, 7, -4, 6]] [p(3):128] [p(0):-19] [p' coefficients:[7, -8, 18]] [p'(3):145] [p'(0):7] [root:1.4183, p(root):0.0000, p'(root):31.862]
Haskell
horner :: (Num a) => a -> [a] -> a
horner x = foldr (\a b -> a + b*x) 0
main = print $ horner 3 [-19, 7, -4, 6]
HicEst
REAL :: x=3, coeffs(4)
DATA coeffs/-19.0, 7.0, -4.0, 6.0/
WRITE(Messagebox) Horner(coeffs, x) ! shows 128
FUNCTION Horner(c, x)
DIMENSION c(1)
Horner = 0
DO i = LEN(c), 1, -1
Horner = x*Horner + c(i)
ENDDO
END
Icon and Unicon
J
Solution:
horner =: (#."0 _ |.)~ NB. Tacit
horner =: [: +`*/ [: }: ,@,. NB. Alternate tacit (equivalent)
horner =: 4 : ' (+ *&y)/x' NB. Alternate explicit (equivalent)
Example:
_19 7 _4 6 horner 3
128
Note:
The primitive verb p.
would normally be used to evaluate polynomials.
_19 7 _4 6 p. 3
128
Java
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;
}
}
Output:
128.0
JavaScript
which includes
function horner(coeffs, x) {
return coeffs.reduceRight( function(acc, coeff) { return(acc * x + coeff) }, 0);
}
console.log(horner([-19,7,-4,6],3)); // ==> 128
jq
# Input: an array of coefficients specifying the polynomial
# to be evaluated at $x, where .[0] is the constant
def horner($x):
. as $coefficients
| reduce range(length-1; -1; -1) as $i (0; . * $x + $coefficients[$i]);
# Example
[-19, 7, -4, 6] | horner(3)
Invocation: $JQ -n -f horner.jq
where $JQ is either jq or gojq
- Output:
128
Julia
Imperative:
function horner(coefs, x)
s = coefs[end] * one(x)
for k in length(coefs)-1:-1:1
s = coefs[k] + x * s
end
return s
end
@show horner([-19, 7, -4, 6], 3)
- Output:
horner([-19, 7, -4, 6], 3) = 128
Functional:
horner2(coefs, x) = foldr((u, v) -> u + x * v, coefs, init=zero(promote_type(typeof(x),eltype(coefs))))
@show horner2([-19, 7, -4, 6], 3)
- Output:
horner2([-19, 7, -4, 6], 3) = 128
Note: In Julia 1.4 or later one would normally use the built-in evalpoly function for this purpose:
@show evalpoly(3, [-19, 7, -4, 6])
- Output:
evalpoly(3, [-19, 7, -4, 6]) = 128
K
horner:{y _sv|x}
horner[-19 7 -4 6;3]
128
Kotlin
// version 1.1.2
fun horner(coeffs: DoubleArray, x: Double): Double {
var sum = 0.0
for (i in coeffs.size - 1 downTo 0) sum = sum * x + coeffs[i]
return sum
}
fun main(args: Array<String>) {
val coeffs = doubleArrayOf(-19.0, 7.0, -4.0, 6.0)
println(horner(coeffs, 3.0))
}
- Output:
128.0
Lambdatalk
{def horner
{def horner.r
{lambda {:p :x :r}
{if {A.empty? :p}
then :r
else {horner.r {A.rest :p} :x {+ {A.first :p} {* :x :r}}}}}}
{lambda {:p :x}
{horner.r {A.reverse :p} :x 0}}}
{horner {A.new -19 7 -4 6} 3}
-> 128
{def φ {/ {+ 1 {sqrt 5}} 2}} = 1.618033988749895
{horner {A.new -1 -1 1} φ}
-> 2.220446049250313e-16 ~ 0
Liberty BASIC
src$ = "Hello"
coefficients$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in order
x = 3
print horner(coefficients$, x) '128
print horner("4 3 2 1", 10) '1234
print horner("1 1 0 0 1", 2) '19
end
function horner(coefficients$, x)
accumulator = 0
'getting length of a list requires extra pass with WORD$.
'So we just started from high above
for index = 100 to 1 step -1
cft$ = word$(coefficients$, index)
if cft$<>"" then accumulator = ( accumulator * x ) + val(cft$)
next
horner = accumulator
end function
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
Lua
function horners_rule( coeff, x )
local res = 0
for i = #coeff, 1, -1 do
res = res * x + coeff[i]
end
return res
end
x = 3
coefficients = { -19, 7, -4, 6 }
print( horners_rule( coefficients, x ) )
Maple
applyhorner:=(L::list,x)->foldl((s,t)->s*x+t,op(ListTools:-Reverse(L))):
applyhorner([-19,7,-4,6],x);
applyhorner([-19,7,-4,6],3);
Output:
((6 x - 4) x + 7) x - 19 128
Mathematica / Wolfram Language
Horner[l_List, x_] := Fold[x #1 + #2 &, 0, l]
Horner[{6, -4, 7, -19}, x]
-> -19 + x (7 + x (-4 + 6 x))
-19 + x (7 + x (-4 + 6 x)) /. x -> 3
-> 128
MATLAB
function accumulator = hornersRule(x,coefficients)
accumulator = 0;
for i = (numel(coefficients):-1:1)
accumulator = (accumulator * x) + coefficients(i);
end
end
Output:
>> hornersRule(3,[-19, 7, -4, 6])
ans =
128
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.
>> polyval(fliplr([-19, 7, -4, 6]),3)
ans =
128
Maxima
/* Function horner already exists in Maxima, though it operates on expressions, not lists of coefficients */
horner(5*x^3+2*x+1);
x*(5*x^2+2)+1
/* Here is an implementation */
horner2(p, x) := block([n, y, i],
n: length(p),
y: p[n],
for i: n - 1 step -1 thru 1 do y: y*x + p[i],
y
)$
horner2([-19, 7, -4, 6], 3);
128
/* Another with rreduce */
horner3(p,x):=rreduce(lambda([a,y],x*y+a),p);
horner3([a,b,c,d,e,f],x);
x*(x*(x*(x*(f*x+e)+d)+c)+b)+a
/* Extension to compute also derivatives up to a specified order.
See William Kahan, Roundoff in Polynomial Evaluation, 1986
http://www.cs.berkeley.edu/~wkahan/Math128/Poly.pdf */
poleval(a, x, [m]) := block(
[n: length(a), v, k: 1],
if emptyp(m) then m: 1 else m: 1 + first(m),
v: makelist(0, m),
v[1]: a[n],
for i from n - 1 thru 1 step -1 do (
for j from m thru 2 step -1 do v[j]: v[j] * x + v[j - 1],
v[1]: v[1] * x + a[i]
),
for i from 2 thru m do (
v[i]: v[i] * k,
k: k * i
),
if m = 1 then first(v) else v
)$
poleval([0, 0, 0, 0, 1], x, 4);
[x^4, 4 * x^3, 12 * x^2, 24 * x, 24]
poleval([0, 0, 0, 0, 1], x);
x^4
Mercury
:- module horner.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module int, list, string.
main(!IO) :-
io.format("%i\n", [i(horner(3, [-19, 7, -4, 6]))], !IO).
:- func horner(int, list(int)) = int.
horner(X, Cs) = list.foldr((func(C, Acc) = Acc * X + C), Cs, 0).
МК-61/52
ИП0 1 + П0
ИПE ИПD * КИП0 + ПE
ИП0 1 - x=0 04
ИПE С/П
Input: Р1:РС - coefficients, Р0 - number of the coefficients, РD - x.
Modula-2
MODULE Horner;
FROM RealStr IMPORT RealToStr;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
PROCEDURE Horner(coeff : ARRAY OF REAL; x : REAL) : REAL;
VAR
ans : REAL;
i : CARDINAL;
BEGIN
ans := 0.0;
FOR i:=HIGH(coeff) TO 0 BY -1 DO
ans := (ans * x) + coeff[i];
END;
RETURN ans
END Horner;
TYPE A = ARRAY[0..3] OF REAL;
VAR
buf : ARRAY[0..63] OF CHAR;
coeff : A;
ans : REAL;
BEGIN
coeff := A{-19.0, 7.0, -4.0, 6.0};
ans := Horner(coeff, 3.0);
RealToStr(ans, buf);
WriteString(buf);
WriteLn;
ReadChar
END Horner.
NetRexx
/* NetRexx */
options replace format comments java crossref savelog symbols nobinary
c = [-19, 7, -4, 6] -- # list coefficients of all x^0..x^n in order
n=3
x=3
r=0
loop i=n to 0 by -1
r=r*x+c[i]
End
Say r
Say 6*x**3-4*x**2+7*x-19
Output:
128 128
Nim
# You can also just use `reversed` proc from stdlib `algorithm` module
iterator reversed[T](x: openArray[T]): T =
for i in countdown(x.high, x.low):
yield x[i]
proc horner[T](coeffs: openArray[T], x: T): int =
for c in reversed(coeffs):
result = result * x + c
echo horner([-19, 7, -4, 6], 3)
Oberon-2
MODULE HornerRule;
IMPORT
Out;
TYPE
Coefs = POINTER TO ARRAY OF LONGINT;
VAR
coefs: Coefs;
PROCEDURE Eval(coefs: ARRAY OF LONGINT;size,x: LONGINT): LONGINT;
VAR
i,acc: LONGINT;
BEGIN
acc := 0;
FOR i := LEN(coefs) - 1 TO 0 BY -1 DO
acc := acc * x + coefs[i]
END;
RETURN acc
END Eval;
BEGIN
NEW(coefs,4);
coefs[0] := -19;
coefs[1] := 7;
coefs[2] := -4;
coefs[3] := 6;
Out.Int(Eval(coefs^,4,3),0);Out.Ln
END HornerRule.
- Output:
128
Objeck
class Horner {
function : Main(args : String[]) ~ Nil {
coeffs := Collection.FloatVector->New();
coeffs->AddBack(-19.0);
coeffs->AddBack(7.0);
coeffs->AddBack(-4.0);
coeffs->AddBack(6.0);
PolyEval(coeffs, 3)->PrintLine();
}
function : PolyEval(coefficients : Collection.FloatVector , x : Float) ~ Float {
accumulator := coefficients->Get(coefficients->Size() - 1);
for(i := coefficients->Size() - 2; i > -1; i -= 1;) {
accumulator := (accumulator * x) + coefficients->Get(i);
};
return accumulator;
}
}
Objective-C
Using blocks
#import <Foundation/Foundation.h>
typedef double (^mfunc)(double, double);
@interface NSArray (HornerRule)
- (double)horner: (double)x;
- (NSArray *)reversedArray;
- (double)injectDouble: (double)s with: (mfunc)op;
@end
@implementation NSArray (HornerRule)
- (NSArray *)reversedArray
{
return [[self reverseObjectEnumerator] allObjects];
}
- (double)injectDouble: (double)s with: (mfunc)op
{
double sum = s;
for(NSNumber* el in self) {
sum = op(sum, [el doubleValue]);
}
return sum;
}
- (double)horner: (double)x
{
return [[self reversedArray] injectDouble: 0.0 with: ^(double s, double a) { return s * x + a; } ];
}
@end
int main()
{
@autoreleasepool {
NSArray *coeff = @[@-19.0, @7.0, @-4.0, @6.0];
printf("%f\n", [coeff horner: 3.0]);
}
return 0;
}
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
It's also possible to do fold_right instead of reversing and doing fold_left; but fold_right is not tail-recursive.
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)
ooRexx
/* Rexx ---------------------------------------------------------------
* 04.03.2014 Walter Pachl
*--------------------------------------------------------------------*/
c = .array~of(-19,7,-4,6) -- coefficients of all x^0..x^n in order
n=3
x=3
r=0
loop i=n+1 to 1 by -1
r=r*x+c[i]
End
Say r
Say 6*x**3-4*x**2+7*x-19
Output:
128 128
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}}
PARI/GP
Also note that Pari has a polynomial type. Evaluating these is as simple as subst(P,variable(P),x)
.
horner(v,x)={
my(s=0);
forstep(i=#v,1,-1,s=s*x+v[i]);
s
};
Pascal
Program HornerDemo(output);
function horner(a: array of double; x: double): double;
var
i: integer;
begin
horner := a[high(a)];
for i := high(a) - 1 downto low(a) do
horner := horner * x + a[i];
end;
const
poly: array [1..4] of double = (-19.0, 7.0, -4.0, 6.0);
begin
write ('Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: ');
writeln (horner (poly, 3.0):8:4);
end.
Output:
Horner calculated polynomial of 6*x^3 - 4*x^2 + 7*x - 19 for x = 3: 128.0000
PascalABC.NET
function Horner(coeffs: array of real; x: real): real;
begin
Result := 0;
foreach var coeff in coeffs.Reverse do
Result := Result * x + coeff
end;
begin
Print(Horner(|-19.0, 7, -4, 6|, 3))
end.
- Output:
128
Perl
use 5.10.0;
use strict;
use warnings;
sub horner(\@$){
my ($coef, $x) = @_;
my $result = 0;
$result = $result * $x + $_ for reverse @$coef;
return $result;
}
my @coeff = (-19.0, 7, -4, 6);
my $x = 3;
say horner @coeff, $x;
Functional version
use strict;
use List::Util qw(reduce);
sub horner($$){
my ($coeff_ref, $x) = @_;
reduce { $a * $x + $b } reverse @$coeff_ref;
}
my @coeff = (-19.0, 7, -4, 6);
my $x = 3;
print horner(\@coeff, $x), "\n";
Recursive version
sub horner {
my ($coeff, $x) = @_;
@$coeff and
$$coeff[0] + $x * horner( [@$coeff[1 .. $#$coeff]], $x )
}
print horner( [ -19, 7, -4, 6 ], 3 );
Phix
with javascript_semantics function horner(atom x, sequence coeff) atom res = 0 for i=length(coeff) to 1 by -1 do res = res*x + coeff[i] end for return res end function ?horner(3,{-19, 7, -4, 6})
- Output:
128
PHP
<?php
function horner($coeff, $x) {
$result = 0;
foreach (array_reverse($coeff) as $c)
$result = $result * $x + $c;
return $result;
}
$coeff = array(-19.0, 7, -4, 6);
$x = 3;
echo horner($coeff, $x), "\n";
?>
Functional version
<?php
function horner($coeff, $x) {
return array_reduce(array_reverse($coeff), function ($a, $b) use ($x) { return $a * $x + $b; }, 0);
}
$coeff = array(-19.0, 7, -4, 6);
$x = 3;
echo horner($coeff, $x), "\n";
?>
Picat
Recursion
horner([],_X,0).
horner([H|T],X,V) :-
horner(T,X,V1),
V = V1 * X + H.
Iterative
horner2(Coeff, X, V) =>
Acc = 0,
foreach(I in Coeff.length..-1..1)
Acc := Acc*X + Coeff[I]
end,
V = Acc.
Functional approach
h3(X,A,B) = A+B*X.
horner3(Coeff, X) = fold($h3(X),0,Coeff.reverse()).
Test
go =>
horner([-19, 7, -4, 6], 3, V),
println(V),
horner2([-19, 7, -4, 6], 3, V2),
println(V2),
V3 = horner3([-19, 7, -4, 6], 3),
println(V3),
nl.
- Output:
128 128 128
PicoLisp
(de horner (Coeffs X)
(let Res 0
(for C (reverse Coeffs)
(setq Res (+ C (* X Res))) ) ) )
: (horner (-19.0 7.0 -4.0 6.0) 3.0)
-> 128
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;
Potion
horner = (x, coef) :
result = 0
coef reverse each (a) :
result = (result * x) + a
.
result
.
horner(3, (-19, 7, -4, 6)) print
PowerShell
function horner($coefficients, $x) {
$accumulator = 0
foreach($i in ($coefficients.Count-1)..0){
$accumulator = ( $accumulator * $x ) + $coefficients[$i]
}
$accumulator
}
$coefficients = @(-19, 7, -4, 6)
$x = 3
horner $coefficients $x
Output:
128
Prolog
Tested with SWI-Prolog. Works with other dialects.
horner([], _X, 0).
horner([H|T], X, V) :-
horner(T, X, V1),
V is V1 * X + H.
Output :
?- horner([-19, 7, -4, 6], 3, V).
V = 128.
Functional approach
Works with SWI-Prolog and module lambda, written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl
:- use_module(library(lambda)).
% foldr(Pred, Init, List, R).
%
foldr(_Pred, Val, [], Val).
foldr(Pred, Val, [H | T], Res) :-
foldr(Pred, Val, T, Res1),
call(Pred, Res1, H, Res).
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).
PureBasic
Procedure Horner(List Coefficients(), b)
Define result
ForEach Coefficients()
result*b+Coefficients()
Next
ProcedureReturn result
EndProcedure
Implemented as
NewList a()
AddElement(a()): a()= 6
AddElement(a()): a()= -4
AddElement(a()): a()= 7
AddElement(a()): a()=-19
Debug Horner(a(),3)
Outputs
128
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
Functional version
>>> 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
>>> import numpy
>>> numpy.polynomial.polynomial.polyval(3, (-19, 7, -4, 6))
128.0
R
Procedural style:
horner <- function(a, x) {
y <- 0
for(c in rev(a)) {
y <- y * x + c
}
y
}
cat(horner(c(-19, 7, -4, 6), 3), "\n")
Functional style:
horner <- function(x, v) {
Reduce(v, right=T, f=function(a, b) {
b * x + a
})
}
- Output:
> v <- c(-19, 7, -4, 6) > horner(3, v) [1] 128
Racket
Translated from Haskell
#lang racket
(define (horner x l)
(foldr (lambda (a b) (+ a (* b x))) 0 l))
(horner 3 '(-19 7 -4 6))
Raku
(formerly Perl 6)
sub horner ( @coeffs, $x ) {
@coeffs.reverse.reduce: { $^a * $x + $^b };
}
say horner( [ -19, 7, -4, 6 ], 3 );
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 Pairs and the reduction meta-operator:
multi horner(Numeric $c, $) { $c }
multi horner(Pair $c, $x) {
$c.key + $x * horner( $c.value, $x )
}
say horner( [=>](-19, 7, -4, 6 ), 3 );
We can also use the composition operator:
sub horner ( @coeffs, $x ) {
([o] map { $_ + $x * * }, @coeffs)(0);
}
say horner( [ -19, 7, -4, 6 ], 3 );
- Output:
128
One advantage of using the composition operator is that it allows for the use of an infinite list of coefficients.
sub horner ( @coeffs, $x ) {
map { .(0) }, [\o] map { $_ + $x * * }, @coeffs;
}
say horner( [ 1 X/ (1, |[\*] 1 .. *) ], i*pi )[20];
- Output:
-0.999999999924349-5.28918515954219e-10i
Rascal
import List;
public int horners_rule(list[int] coefficients, int x){
acc = 0;
for( i <- reverse(coefficients)){
acc = acc * x + i;}
return acc;
}
A neater and shorter solution using a reducer:
public int horners_rule2(list[int] coefficients, int x) = (0 | it * x + c | c <- reverse(coefficients));
Output:
rascal>horners_rule([-19, 7, -4, 6], 3)
int: 128
rascal>horners_rule2([-19, 7, -4, 6], 3)
int: 128
REBOL
REBOL []
horner: func [coeffs x] [
result: 0
foreach i reverse coeffs [
result: (result * x) + i
]
return result
]
print horner [-19 7 -4 6] 3
REXX
version 1
/*REXX program demonstrates using Horner's rule for polynomial evaluation. */
numeric digits 30 /*use extra numeric precision. */
parse arg x poly /*get value of X and the coefficients. */
$= /*start with a clean slate equation. */
do deg=0 until poly=='' /*get the equation's coefficients. */
parse var poly c.deg poly; c.deg=c.deg/1 /*get equation coefficient & normalize.*/
if c.deg>=0 then c.deg= '+'c.deg /*if ¬ negative, then prefix with a + */
$=$ c.deg /*concatenate it to the equation. */
if deg\==0 & c.deg\=0 then $=$'∙x^'deg /*¬1st coefficient & ¬0? Append X pow.*/
$=$ ' ' /*insert some blanks, make it look nice*/
end /*deg*/
say ' x = ' x
say ' degree = ' deg
say ' equation = ' $
a=c.deg /*A: is the accumulator (or answer). */
do j=deg-1 by -1 for deg; a=a*x+c.j /*apply Horner's rule to the equations.*/
end /*j*/
say /*display a blank line for readability.*/
say ' answer = ' a /*stick a fork in it, we're all done. */
output when the following is used for input: 3 -19 7 -4 6
x = 3 degree = 3 equation = -19 +7∙x^1 -4∙x^2 +6∙x^3 answer = 128
version 2
/* REXX ---------------------------------------------------------------
* 27.07.2012 Walter Pachl
* coefficients reversed to descending order of power
* I'm used to x**2+x-3
* equation formatting prettified (coefficients 1 and 0)
*--------------------------------------------------------------------*/
Numeric Digits 30 /* use extra numeric precision. */
Parse Arg x poly /* get value of x and coefficients*/
rpoly=''
Do p=0 To words(poly)-1
rpoly=rpoly word(poly,words(poly)-p)
End
poly=rpoly
equ='' /* start with equation clean slate*/
deg=words(poly)-1
pdeg=deg
Do Until deg<0 /* get the equation's coefficients*/
Parse Var poly c.deg poly /* in descending order of powers */
c.deg=c.deg+0 /* normalize it */
If c.deg>0 & deg<pdeg Then /* positive and not first term */
prefix='+' /* prefix a + sign. */
Else prefix=''
Select
When deg=0 Then term=c.deg
When deg=1 Then
If c.deg=1 Then term='x'
Else term=c.deg'*x'
Otherwise
If c.deg=1 Then term='x^'deg
Else term=c.deg'*x^'deg
End
If c.deg<>0 Then /* build up the equation */
equ=equ||prefix||term
deg=deg-1
End
a=c.pdeg
Do p=pdeg To 1 By -1 /* apply Horner's rule. */
pm1=p-1
a=a*x+c.pm1
End
Say ' x = ' x
Say ' degree = ' pdeg
Say ' equation = ' equ
Say ' '
Say ' result = ' a
- Output:
x = 3 degree = 3 equation = 6*x^3-4*x^2+7*x-19 result = 128
Ring
coefficients = [-19, 7, -4, 6]
see "x = 3" + nl +
"degree = 3" + nl +
"equation = 6*x^3-4*x^2+7*x-19" + nl +
"result = " + horner(coefficients, 3) + nl
func horner coeffs, x
w = 0
for n = len(coeffs) to 1 step -1
w = w * x + coeffs[n]
next
return w
Output:
x = 3 degree = 3 equation = 6*x^3-4*x^2+7*x-19 result = 128
RLaB
RLaB implements horner's scheme for polynomial evaluation in its built-in function polyval. What is important is that RLaB stores the polynomials as row vectors starting from the highest power just as matlab and octave do.
This said, solution to the problem is
>> a = [6, -4, 7, -19]
6 -4 7 -19
>> x=3
3
>> polyval(x, a)
128
RPL
Translation of the algorithm
Following the pseudocode given here to the letter:
≪ OVER DUP SIZE GET → a x0 p ≪ a SIZE 1 - 1 FOR j 'a(j)+x0*p' EVAL 'p' STO -1 STEP p ≫ ≫ ‘HORNR’ STO
Idiomatic one-liner
Reducing the loop to its simplest form: one memory call, one multiplication and one addition.
≪ → x0 ≪ LIST→ 2 SWAP START x0 * + NEXT ≫ ≫ ‘HORNR’ STO
- Input:
{ -19 7 -4 6 } 3 HORNR
- Output:
1: 128
Ruby
def horner(coeffs, x)
coeffs.reverse.inject(0) {|acc, coeff| acc * x + coeff}
end
p horner([-19, 7, -4, 6], 3) # ==> 128
Run BASIC
coef$ = "-19 7 -4 6" ' list coefficients of all x^0..x^n in order
x = 3
print horner(coef$,x) '128
print horner("1.2 2.3 3.4 4.5 5.6", 8) '25478.8
print horner("5 4 3 2 1", 10) '12345
print horner("1 0 1 1 1 0 0 1", 2) '157
end
function horner(coef$,x)
while word$(coef$, i + 1) <> ""
i = i + 1 ' count the num of values
wend
for j = i to 1 step -1
accum = ( accum * x ) + val(word$(coef$, j))
next
horner = accum
end function
Rust
fn horner(v: &[f64], x: f64) -> f64 {
v.iter().rev().fold(0.0, |acc, coeff| acc*x + coeff)
}
fn main() {
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.
extern crate num; // 0.2.0
use num::Zero;
use std::ops::{Add, Mul};
fn horner<Arr, Arg, Out>(v: &[Arr], x: Arg) -> Out
where
Arr: Clone,
Arg: Clone,
Out: Zero + Mul<Arg, Output = Out> + Add<Arr, Output = Out>,
{
v.iter()
.rev()
.fold(Zero::zero(), |acc, coeff| acc * x.clone() + coeff.clone())
}
fn main() {
let v = [-19., 7., -4., 6.];
let output: f64 = horner(&v, 3.0);
println!("result: {}", output);
}
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;
Scala
def horner(coeffs:List[Double], x:Double)=
coeffs.reverse.foldLeft(0.0){(a,c)=> a*x+c}
val coeffs=List(-19.0, 7.0, -4.0, 6.0)
println(horner(coeffs, 3))
-> 128.0
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)
Output:
128
Seed7
$ include "seed7_05.s7i";
include "float.s7i";
const type: coeffType is array float;
const func float: horner (in coeffType: coeffs, in float: x) is func
result
var float: res is 0.0;
local
var integer: i is 0;
begin
for i range length(coeffs) downto 1 do
res := res * x + coeffs[i];
end for;
end func;
const proc: main is func
local
const coeffType: coeffs is [] (-19.0, 7.0, -4.0, 6.0);
begin
writeln(horner(coeffs, 3.0) digits 1);
end func;
Output:
128.0
Sidef
Functional:
func horner(coeff, x) {
coeff.reverse.reduce { |a,b| a*x + b };
}
say horner([-19, 7, -4, 6], 3); # => 128
Recursive:
func horner(coeff, x) {
(coeff.len > 0) \
? (coeff[0] + x*horner(coeff.last(-1), x))
: 0
}
say horner([-19, 7, -4, 6], 3) # => 128
Smalltalk
OrderedCollection extend [
horner: aValue [
^ self reverse inject: 0 into: [:acc :c | acc * aValue + c].
]
].
(#(-19 7 -4 6) asOrderedCollection horner: 3) displayNl.
Standard ML
(* Assuming real type for coefficients and x *)
fun horner coeffList x = foldr (fn (a, b) => a + b * x) (0.0) coeffList
Swift
func horner(coefs: [Double], x: Double) -> Double {
return reduce(lazy(coefs).reverse(), 0) { $0 * x + $1 }
}
println(horner([-19, 7, -4, 6], 3))
- Output:
128.0
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
}
Demonstrating:
puts [horner {-19 7 -4 6} 3]
Output:
128
VBA
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
Dim ncoeff As Integer
result = 0
ncoeff = UBound(coeff())
For i = ncoeff To 0 Step -1
result = (result * x) + coeff(i)
Next i
Horner = result
End Function
Output:
print Horner(3, -19, 7, -4, 6) 128
VBScript
Function horners_rule(coefficients,x)
accumulator = 0
For i = UBound(coefficients) To 0 Step -1
accumulator = (accumulator * x) + coefficients(i)
Next
horners_rule = accumulator
End Function
WScript.StdOut.WriteLine horners_rule(Array(-19,7,-4,6),3)
- Output:
128
Visual Basic .NET
Module Module1
Function Horner(coefficients As Double(), variable As Double) As Double
Return coefficients.Reverse().Aggregate(Function(acc, coeff) acc * variable + coeff)
End Function
Sub Main()
Console.WriteLine(Horner({-19.0, 7.0, -4.0, 6.0}, 3.0))
End Sub
End Module
- Output:
128
Visual FoxPro
Coefficients in ascending order.
LOCAL x As Double
LOCAL ARRAY aCoeffs[1]
CLEAR
CREATE CURSOR coeffs (c1 I, c2 I, c3 I, c4 I)
INSERT INTO coeffs VALUES (-19,7,-4,6)
SCATTER TO aCoeffs
x = VAL(INPUTBOX("Value of x:", "Value"))
? EvalPoly(@aCoeffs, x)
USE IN coeffs
FUNCTION EvalPoly(c, x As Double) As Double
LOCAL s As Double, k As Integer, n As Integer
n = ALEN(c)
s = 0
FOR k = n TO 1 STEP -1
s = s*x + c[k]
ENDFOR
RETURN s
ENDFUNC
Coefficients in descending order.
LOCAL x As Double
LOCAL ARRAY aCoeffs[1]
CLEAR
CREATE CURSOR tmp (c1 I, c2 I, c3 I, c4 I)
INSERT INTO tmp VALUES (6,-4,7,-19)
SCATTER TO aCoeffs
x = VAL(INPUTBOX("Value of x:", "Value"))
? EvalPolyDesc(@aCoeffs, x)
USE IN tmp
FUNCTION EvalPolyDesc(c, x As Double) As Double
LOCAL s As Double, e
s = 0
FOR EACH e IN c FOXOBJECT
s = s*x + e
ENDFOR
RETURN s
ENDFUNC
V (Vlang)
fn horner(x i64, c []i64) i64 {
mut acc := i64(0)
for i := c.len - 1; i >= 0; i-- {
acc = acc*x + c[i]
}
return acc
}
fn main() {
println(horner(3, [i64(-19), 7, -4, 6]))
}
- Output:
128
Wren
var horner = Fn.new { |x, c|
var count = c.count
if (count == 0) return 0
return (count-1..0).reduce(0) { |acc, index| acc*x + c[index] }
}
System.print(horner.call(3, [-19, 7, -4, 6]))
- Output:
128
XPL0
code IntOut=11;
func Horner(X, N, C); \Return value of polynomial in X
int X, N, C; \variable, number of terms, coefficient list
int A, I;
[A:= 0;
for I:= N-1 downto 0 do
A:= A*X + C(I);
return A;
];
IntOut(0, Horner(3, 4, [-19, 7, -4, 6]));
Output:
128
zkl
fcn horner(coeffs,x)
{ coeffs.reverse().reduce('wrap(a,coeff){ a*x + coeff },0.0) }
- Output:
horner(T(-19,7,-4,6), 3).println(); 128
- Programming Tasks
- Solutions by Programming Task
- 11l
- 360 Assembly
- ACL2
- Action!
- Ada
- Aime
- ALGOL 68
- ALGOL W
- APL
- ATS
- Arturo
- AutoHotkey
- AWK
- BASIC
- Applesoft BASIC
- BASIC256
- Chipmunk Basic
- Gambas
- GW-BASIC
- Minimal BASIC
- MSX Basic
- QBasic
- Quite BASIC
- Yabasic
- Batch File
- BBC BASIC
- Bracmat
- C
- C sharp
- C++
- Clojure
- CoffeeScript
- Common Lisp
- D
- Delphi
- Classes,SysUtils,StdCtrls
- E
- EasyLang
- EchoLisp
- EDSAC order code
- Elena
- Elixir
- Emacs Lisp
- Erlang
- ERRE
- Euler Math Toolbox
- F Sharp
- Factor
- Forth
- Fortran
- FreeBASIC
- FunL
- FutureBasic
- GAP
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Kotlin
- Lambdatalk
- Liberty BASIC
- Logo
- Lua
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Maxima
- Mercury
- МК-61/52
- Modula-2
- NetRexx
- Nim
- Oberon-2
- Objeck
- Objective-C
- OCaml
- Octave
- OoRexx
- Oz
- PARI/GP
- Pascal
- PascalABC.NET
- Perl
- Phix
- PHP
- Picat
- PicoLisp
- PL/I
- Potion
- PowerShell
- Prolog
- PureBasic
- Python
- NumPy
- R
- Racket
- Raku
- Rascal
- REBOL
- REXX
- Ring
- RLaB
- RPL
- Ruby
- Run BASIC
- Rust
- Sather
- Scala
- Scheme
- Seed7
- Sidef
- Smalltalk
- Standard ML
- Swift
- Tcl
- VBA
- VBScript
- Visual Basic .NET
- Visual FoxPro
- V (Vlang)
- Wren
- XPL0
- Zkl
- Pages with too many expensive parser function calls