/usr/share/axiom-20170501/src/algebra/NEWTON.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | )abbrev package NEWTON NewtonInterpolation
++ Description:
++ This package exports Newton interpolation for the special case where the
++ result is known to be in the original integral domain
++ The packages defined in this file provide fast fraction free rational
++ interpolation algorithms. (see FAMR2, FFFG, FFFGF, NEWTON)
NewtonInterpolation(F) : SIG == CODE where
F : IntegralDomain
SIG ==> with
newton : List F -> SparseUnivariatePolynomial F
++ \spad{newton}(l) returns the interpolating polynomial for the values
++ l, where the x-coordinates are assumed to be [1,2,3,...,n] and the
++ coefficients of the interpolating polynomial are known to be in the
++ domain F., it is a very streamlined version for a special case of
++ interpolation.
CODE ==> add
differences(yl: List F): List F ==
[y2-y1 for y1 in yl for y2 in rest yl]
z: SparseUnivariatePolynomial(F) := monomial(1,1)
-- we assume x=[1,2,3,...,n]
newtonAux(k: F, fact: F, yl: List F): SparseUnivariatePolynomial(F) ==
if empty? rest yl
then ((yl.1) exquo fact)::F::SparseUnivariatePolynomial(F)
else ((yl.1) exquo fact)::F::SparseUnivariatePolynomial(F)
+ (z-k::SparseUnivariatePolynomial(F)) _
* newtonAux(k+1$F, fact*k, differences yl)
newton yl == newtonAux(1$F, 1$F, yl)
|