diff options
Diffstat (limited to 'src/algebra/cra.spad.pamphlet')
| -rw-r--r-- | src/algebra/cra.spad.pamphlet | 131 |
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} |