Initial population.

1 files changed, 173 insertions, 0 deletions

diff --git a/src/algebra/galutil.spad.pamphlet b/src/algebra/galutil.spad.pamphlet
new file mode 100644
index 00000000..8873a5eb
--- /dev/null
+++ b/src/algebra/galutil.spad.pamphlet
@@ -0,0 +1,173 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra galutil.spad}
+\author{Frederic Lehobey}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package GALUTIL GaloisGroupUtilities}
+<<package GALUTIL GaloisGroupUtilities>>=
+)abbrev package GALUTIL GaloisGroupUtilities
+++ Author: Frederic Lehobey
+++ Date Created: 29 June 1994
+++ Date Last Updated: 30 June 1994 
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description: 
+++ \spadtype{GaloisGroupUtilities} provides several useful functions.
+
+GaloisGroupUtilities(R): Exports == Implementation where
+  N ==> NonNegativeInteger
+  Z ==> Integer
+  R : Ring
+
+  Exports ==> with
+    pascalTriangle: (N,Z) -> R
+      ++ pascalTriangle(n,r) returns the binomial coefficient
+      ++ \spad{C(n,r)=n!/(r! (n-r)!)}
+      ++ and stores it in a table to prevent recomputation.
+    rangePascalTriangle: N -> N
+      ++ rangePascalTriangle(n) sets the maximal number of lines which
+      ++ are stored and returns the previous value.
+    rangePascalTriangle: () -> N
+      ++ rangePascalTriangle() returns the maximal number of lines stored.
+    sizePascalTriangle: () -> N
+      ++ sizePascalTriangle() returns the number of entries currently stored
+      ++ in the table.
+    fillPascalTriangle: () -> Void
+      ++ fillPascalTriangle() fills the stored table.
+
+    if R has FloatingPointSystem then
+      safeCeiling: R -> Z
+        ++ safeCeiling(x) returns the integer which is greater than any integer
+        ++ with the same floating point number representation.
+      safeFloor: R -> Z
+        ++ safeFloor(x) returns the integer which is lower or equal to the
+        ++ largest integer which has the same floating point number
+        ++ representation.
+      safetyMargin: N -> N
+        ++ safetyMargin(n) sets to n the number of low weight digits we do not
+        ++ trust in the floating point representation and returns the previous
+        ++ value (for use by \spadfun{safeCeiling}).
+      safetyMargin: () -> N
+        ++ safetyMargin() returns the number of low weight digits we do not
+        ++ trust in the floating point representation (used by 
+        ++ \spadfun{safeCeiling}).
+
+  Implementation ==> add
+
+    if R has FloatingPointSystem then
+      safetymargin : N := 6
+      
+      safeFloor(x:R):Z ==
+        if (shift := order(x)-precision()$R+safetymargin) >= 0 then
+          x := x+float(1,shift)
+        retract(floor(x))@Z
+
+      safeCeiling(x:R):Z ==
+        if (shift := order(x)-precision()$R+safetymargin) >= 0 then
+          x := x+float(1,shift)
+        retract(ceiling(x))@Z
+
+      safetyMargin(n:N):N == 
+        (safetymargin,n) := (n,safetymargin)
+        n
+
+      safetyMargin():N == safetymargin
+
+    pascaltriangle : FlexibleArray(R) := empty()
+    ncomputed : N := 3
+    rangepascaltriangle : N := 216
+
+    pascalTriangle(n:N, r:Z):R ==
+      negative? r => 0
+      (d := n-r) < r => pascalTriangle(n,d)
+      zero? r => 1$R
+--      one? r => n :: R
+      (r = 1) => n :: R
+      n > rangepascaltriangle => 
+       binomial(n,r)$IntegerCombinatoricFunctions(Z) :: R
+      n <= ncomputed =>
+        m := divide(n-4,2)
+        mq := m.quotient
+        pascaltriangle((mq+1)*(mq+m.remainder)+r-1)
+      -- compute the missing lines
+      for i in (ncomputed+1)..n repeat
+        for j in 2..(i quo 2) repeat
+          pascaltriangle := concat!(pascaltriangle,pascalTriangle((i-1) 
+           :: N, j-1)+pascalTriangle((i-1) :: N,j))
+        ncomputed := i
+      pascalTriangle(n,r)
+
+    rangePascalTriangle(n:N):N ==
+      if n<ncomputed then
+        if n<3 then
+          pascaltriangle := delete!(pascaltriangle,1..#pascaltriangle)
+          ncomputed := 3
+        else
+          d := divide(n-3,2)
+          dq := d.quotient
+          pascaltriangle := delete!(pascaltriangle,((dq+1)*(dq+d.remainder)
+           +1)..#pascaltriangle)
+          ncomputed := n
+      (rangepascaltriangle,n) := (n,rangepascaltriangle)
+      n
+
+    rangePascalTriangle():N == rangepascaltriangle
+
+    sizePascalTriangle():N == #pascaltriangle
+
+    fillPascalTriangle():Void == pascalTriangle(rangepascaltriangle,2)
+
+@
+\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 GALUTIL GaloisGroupUtilities>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}