/*
Horner's rule in Picat.
From http://rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation#K
"""
A fast scheme for evaluating a polynomial such as:
-19+7x-4x^2+6x^3\,
when
x = 3
is to arrange the computation as follows:
((((0) x + 6) x + (-4)) x + 7) x + (-19);
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.
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import util.
% import cp.
main => go.
% V = 128.
go =>
horner([-19, 7, -4, 6], 3, V),
writeln(V),
horner2([-19, 7, -4, 6], 3, V2),
writeln(V2),
V3 = horner3([-19, 7, -4, 6], 3),
writeln(V3),
nl.
% From the Prolog solution
horner([], _X, V) => V = 0.
horner([H|T], X, V) =>
horner(T, X, V1),
V is V1 * X + H.
horner2(Coeff, X, V) =>
Acc = 0,
foreach(I in Coeff.length..-1..1)
Acc := Acc*X + Coeff[I]
end,
V = Acc.
h3(X,A,B) = A+B*X.
horner3(Coeff, X) = fold($h3(X),0,Coeff.reverse()).