Initial population.

1 files changed, 143 insertions, 0 deletions

diff --git a/src/input/pdecomp0.as.pamphlet b/src/input/pdecomp0.as.pamphlet
new file mode 100644
index 00000000..267a59bf
--- /dev/null
+++ b/src/input/pdecomp0.as.pamphlet
@@ -0,0 +1,143 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/input pdecomp0.as}
+\author{The Axiom Team}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{License}
+<<license>>=
+-- Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+-- All rights reserved.
+--
+-- Redistribution and use in source and binary forms, with or without
+-- modification, are permitted provided that the following conditions are
+-- met:
+--
+--     - Redistributions of source code must retain the above copyright
+--       notice, this list of conditions and the following disclaimer.
+--
+--     - Redistributions in binary form must reproduce the above copyright
+--       notice, this list of conditions and the following disclaimer in
+--       the documentation and/or other materials provided with the
+--       distribution.
+--
+--     - Neither the name of The Numerical ALgorithms Group Ltd. nor the
+--       names of its contributors may be used to endorse or promote products
+--       derived from this software without specific prior written permission.
+--
+-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+-- IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+-- TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+-- PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+-- OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+-- EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+-- PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+-- PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+-- LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+-- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+-- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+@
+<<*>>=
+#pile
+#include "axiom.as"
+<<license>>
+
+--% Polynomial composition and decomposition functions
+--  If f = g o h then  g = leftFactor(f, h)  &  h = rightFactor(f, g)
+--  SMW Dec 86
+
+--% PolynomialComposition
+--)abbrev package PCOMP PolynomialComposition
+--)abbrev package PDECOMP PolynomialDecomposition
+
+PolynomialComposition(UP: UnivariatePolynomialCategory(R), R: Ring): with
+        compose: (UP, UP) -> UP
+
+    == add
+        compose(g:UP, h:UP):UP ==
+            r: UP := 0
+            while g ~= 0 repeat
+                r := leadingCoefficient(g)*h**degree(g) + r
+                g := reductum g
+            r
+
+
+--  Ref: Kozen and Landau, Cornell University  TR 86-773
+
+--% PolynomialDecomposition
+
+
+PolynomialDecomposition(UP:UPC F, F:Field): PDcat == PDdef where
+    UPC ==> UnivariatePolynomialCategory
+    NNI ==> NonNegativeInteger
+    LR  ==> Record(left: UP, right: UP)
+
+    PDcat ==> with
+        decompose: UP -> List UP
+        decompose: (UP, NNI, NNI) -> Union(value1:LR, failed:'failed')
+        leftFactor: (UP, UP) -> Union(value1:UP, failed:'failed')
+        rightFactorCandidate:  (UP, NNI) -> UP
+    PDdef ==> add
+
+        import from F
+        import from LR
+        import from Union(value1:UP, failed:'failed')
+        import from Float
+        import from NNI
+        import from UniversalSegment NNI
+        import from Record(quotient:UP, remainder:UP);
+
+        leftFactor(f:UP, h:UP):Union(value1:UP, failed:'failed')  == 
+             g: UP := 0
+             for i in 0.. while f ~= 0 repeat
+                 fr := divide(f, h)
+                 f := fr.quotient
+                 r := fr.remainder
+                 degree r > 0 => return [failed]
+                 g := g + r * monomial(1, i)
+             [g]
+
+        decompose(f:UP, dg:NNI, dh:NNI):Union(value1:LR, failed:'failed') ==
+            df := degree f
+            dg*dh ~= df => [failed]
+            h := rightFactorCandidate(f, dh)
+            g:Union(value1:UP, failed:'failed') := leftFactor(f, h)
+            g case failed => [failed]
+            [[g.value1, h]]
+
+        decompose(f:UP):List UP ==
+            df := degree f
+            for dh in 2..df-1 | df rem dh = 0 repeat
+                h := rightFactorCandidate(f, dh)
+                g := leftFactor(f, h)
+                g case value1 => return
+                    append(decompose(g.value1), decompose h)
+            [f]
+
+
+        rightFactorCandidate(f:UP, dh:NNI):UP ==
+            f  := f / leadingCoefficient f
+            df := degree f
+            dg := df quo dh
+            h  := monomial(1, dh)
+            for k in 1..dh repeat
+                hdg:= h**dg
+                c  := (coefficient(f,df-k)-coefficient(hdg,df-k))/
+                                                       (dg::Integer::F)
+                h  := h + monomial(c, dh-k)
+            h - monomial(coefficient(h, 0), 0) -- drop constant term
+
+
+
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}