Initial population.

1 files changed, 131 insertions, 0 deletions

diff --git a/src/algebra/cra.spad.pamphlet b/src/algebra/cra.spad.pamphlet
new file mode 100644
index 00000000..640170d9
--- /dev/null
+++ b/src/algebra/cra.spad.pamphlet
@@ -0,0 +1,131 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra cra.spad}
+\author{The Axiom Team}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package CRAPACK CRApackage}
+<<package CRAPACK CRApackage>>=
+)abbrev package CRAPACK CRApackage
+ 
+++ This package \undocumented{}
+CRApackage(R:EuclideanDomain): Exports == Implementation where
+  Exports == with
+    modTree: (R,List R) -> List R
+	++ modTree(r,l) \undocumented{}
+    chineseRemainder: (List R, List R) -> R
+    ++ chineseRemainder(lv,lm) returns a value \axiom{v} such that, if
+    ++ x is \axiom{lv.i} modulo \axiom{lm.i} for all \axiom{i}, then
+    ++ x is \axiom{v} modulo \axiom{lm(1)*lm(2)*...*lm(n)}.
+    chineseRemainder: (List List R, List R) -> List R
+    ++ chineseRemainder(llv,lm) returns a list of values, each of which
+    ++ corresponds to the Chinese remainder of the associated element of
+    ++ \axiom{llv} and axiom{lm}.  This is more efficient than applying
+    ++ chineseRemainder several times.
+    multiEuclideanTree: (List R, R) -> List R
+	++ multiEuclideanTree(l,r) \undocumented{}
+  Implementation == add
+
+    BB:=BalancedBinaryTree(R)
+    x:BB
+
+    -- Definition for modular reduction mapping with several moduli
+    modTree(a,lm) ==
+      t := balancedBinaryTree(#lm, 0$R)
+      setleaves_!(t,lm)
+      mapUp_!(t,"*")
+      leaves mapDown_!(t, a, "rem")
+
+    chineseRemainder(lv:List(R), lm:List(R)):R ==
+      #lm ^= #lv => error "lists of moduli and values not of same length"
+      x := balancedBinaryTree(#lm, 0$R)
+      x := setleaves_!(x, lm)
+      mapUp_!(x,"*")
+      y := balancedBinaryTree(#lm, 1$R)
+      y := mapUp_!(copy y,x,#1 * #4 + #2 * #3)
+      (u := extendedEuclidean(value y, value x,1)) case "failed" =>
+        error "moduli not relatively prime"
+      inv := u . coef1
+      linv := modTree(inv, lm)
+      l := [(u*v) rem m for v in lv for u in linv for m in lm]
+      y := setleaves_!(y,l)
+      value(mapUp_!(y, x, #1 * #4 + #2 * #3)) rem value(x)
+
+    chineseRemainder(llv:List List(R), lm:List(R)):List(R) ==
+      x := balancedBinaryTree(#lm, 0$R)
+      x := setleaves_!(x, lm)
+      mapUp_!(x,"*")
+      y := balancedBinaryTree(#lm, 1$R)
+      y := mapUp_!(copy y,x,#1 * #4 + #2 * #3)
+      (u := extendedEuclidean(value y, value x,1)) case "failed" =>
+        error "moduli not relatively prime"
+      inv := u . coef1
+      linv := modTree(inv, lm)
+      retVal:List(R) := []
+      for lv in llv repeat
+        l := [(u3*v) rem m for v in lv for u3 in linv for m in lm]
+        y := setleaves!(y,l)
+        retVal := cons(value(mapUp!(y, x, #1*#4+#2*#3)) rem value(x),retVal)
+      reverse retVal
+
+    extEuclidean: (R, R, R) -> List R
+    extEuclidean(a, b, c) ==
+      u := extendedEuclidean(a, b, c)
+      u case "failed" => error [c, " not spanned by ", a, " and ",b]
+      [u.coef2, u.coef1]
+
+    multiEuclideanTree(fl, rhs) ==
+      x := balancedBinaryTree(#fl, rhs)
+      x := setleaves_!(x, fl)
+      mapUp_!(x,"*")
+      leaves mapDown_!(x, rhs, extEuclidean)
+
+@
+\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.
+@
+<<*>>=
+<<license>>
+
+<<package CRAPACK CRApackage>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}