\documentclass{article}
\usepackage{open-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
      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}