[Axiom-developer] 20070812.03.tpd.patch applied to silver

[daly]

diff --git a/changelog b/changelog
index c74b102..8b9969f 100644
--- a/changelog
+++ b/changelog
@@ -1,3 +1,5 @@
+20070812 tpd src/algebra/Makefile newton.spad added
+20070812 tpd src/algebra/newton.spad added
 20070812 acr src/algebra/mathml.spad license change
 20070812 tpd re-merge input branch
 20070811 tpd src/input/Makefile add classtalk, calcprob
diff --git a/src/algebra/Makefile.pamphlet b/src/algebra/Makefile.pamphlet
index 9172e69..6a281bc 100644
--- a/src/algebra/Makefile.pamphlet
+++ b/src/algebra/Makefile.pamphlet
@@ -346,7 +346,8 @@ LAYER8=\
   ${OUT}/BSTREE.o  ${OUT}/BTOURN.o   ${OUT}/CARD.o    ${OUT}/DRAWHACK.o \
   ${OUT}/DQAGG.o   ${OUT}/FACTFUNC.o ${OUT}/FMTC.o    ${OUT}/FR2.o      \
   ${OUT}/FRAC2.o   ${OUT}/FRUTIL.o   ${OUT}/ITAYLOR.o ${OUT}/MLO.o      \
-  ${OUT}/NAALG.o   ${OUT}/NAALG-.o   ${OUT}/OAGROUP.o ${OUT}/OAMONS.o   \
+  ${OUT}/NAALG.o   ${OUT}/NAALG-.o   ${OUT}/NEWTON.o  \
+  ${OUT}/OAGROUP.o ${OUT}/OAMONS.o   \
   ${OUT}/OP.o      ${OUT}/ORDCOMP2.o ${OUT}/PID.o     ${OUT}/RANDSRC.o  \
   ${OUT}/UNISEG2.o ${OUT}/XALG.o  \
   layer8done
@@ -1260,7 +1261,7 @@ SPADFILES= \
  ${OUTSRC}/mts.spad ${OUTSRC}/multfact.spad ${OUTSRC}/multpoly.spad \
  ${OUTSRC}/multsqfr.spad \
  ${OUTSRC}/naalgc.spad ${OUTSRC}/naalg.spad \
- ${OUTSRC}/newdata.spad ${OUTSRC}/newpoint.spad \
+ ${OUTSRC}/newdata.spad ${OUTSRC}/newpoint.spad ${OUTSRC}/newton.spad \
  ${OUTSRC}/newpoly.spad ${OUTSRC}/nlinsol.spad ${OUTSRC}/nlode.spad \
  ${OUTSRC}/npcoef.spad \
  ${OUTSRC}/nregset.spad \
@@ -1422,6 +1423,7 @@ DOCFILES= \
  ${DOC}/multsqfr.spad.dvi \
  ${DOC}/naalgc.spad.dvi ${DOC}/naalg.spad.dvi ${DOC}/ndftip.as.dvi \
  ${DOC}/nepip.as.dvi ${DOC}/newdata.spad.dvi ${DOC}/newpoint.spad.dvi \
+ ${DOC}/newton.spad.dvi \
  ${DOC}/newpoly.spad.dvi ${DOC}/nlinsol.spad.dvi ${DOC}/nlode.spad.dvi \
  ${DOC}/noptip.as.dvi ${DOC}/npcoef.spad.dvi ${DOC}/nqip.as.dvi \
  ${DOC}/nrc.as.dvi ${DOC}/nregset.spad.dvi ${DOC}/nsfip.as.dvi \
diff --git a/src/algebra/newton.spad.pamphlet b/src/algebra/newton.spad.pamphlet
new file mode 100644
index 0000000..6f588bc
--- /dev/null
+++ b/src/algebra/newton.spad.pamphlet
@@ -0,0 +1,46 @@
+\documentclass{article}
+\usepackage{amsthm,amsmath,axiom}
+\begin{document}
+\title{newton.spad}
+\author{Martin Rubey}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\tableofcontents
+\section{package NEWTON NewtonInterpolation}
+<<package NEWTON NewtonInterpolation>>=
+)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
+NewtonInterpolation F: Exports == Implementation where
+    F: IntegralDomain
+    Exports == with
+      newton: List F -> SparseUnivariatePolynomial F
+
+    Implementation == 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)
+@
+<<*>>=
+<<package NEWTON NewtonInterpolation>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}