\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra si.spad}
\author{Stephen M. Watt, Michael Monagan, James Davenport, Barry Trager}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{category INS IntegerNumberSystem}
<<category INS IntegerNumberSystem>>=
)abbrev category INS IntegerNumberSystem
++ Author: Stephen M. Watt
++ Date Created:
++   January 1988
++ Change History:
++ Basic Operations:
++   addmod, base, bit?, copy, dec, even?, hash, inc, invmod, length, mask,
++   positiveRemainder, symmetricRemainder, multiplicativeValuation, mulmod,
++   odd?, powmod, random, rational, rational?, rationalIfCan, shift, submod
++ Description:  An \spad{IntegerNumberSystem} is a model for the integers.
IntegerNumberSystem(): Category ==
  Join(UniqueFactorizationDomain, EuclideanDomain, OrderedIntegralDomain,
         DifferentialRing, ConvertibleTo Integer, RetractableTo Integer,
           LinearlyExplicitRingOver Integer, ConvertibleTo InputForm,
             ConvertibleTo Pattern Integer, PatternMatchable Integer,
               CombinatorialFunctionCategory, RealConstant,
                 CharacteristicZero, StepThrough) with
   odd?     : % -> Boolean
      ++ odd?(n) returns true if and only if n is odd.
   even?    : % -> Boolean
      ++ even?(n) returns true if and only if n is even.
   multiplicativeValuation
      ++ euclideanSize(a*b) returns \spad{euclideanSize(a)*euclideanSize(b)}.
   base     : () -> %
      ++ base() returns the base for the operations of \spad{IntegerNumberSystem}.
   length   : % -> %
      ++ length(a) length of \spad{a} in digits.
   shift    : (%, %) -> %
      ++ shift(a,i) shift \spad{a} by i digits.
   bit?     : (%, %) -> Boolean
      ++ bit?(n,i) returns true if and only if i-th bit of n is a 1.
   positiveRemainder     : (%, %) -> %
      ++ positiveRemainder(a,b) (where \spad{b > 1}) yields r
      ++ where \spad{0 <= r < b} and \spad{r == a rem b}.
   symmetricRemainder     : (%, %) -> %
      ++ symmetricRemainder(a,b) (where \spad{b > 1}) yields r
      ++ where \spad{ -b/2 <= r < b/2 }.
   rational?: % -> Boolean
      ++ rational?(n) tests if n is a rational number
      ++ (see \spadtype{Fraction Integer}).
   rational : % -> Fraction Integer
      ++ rational(n) creates a rational number (see \spadtype{Fraction Integer})..
   rationalIfCan: % -> Union(Fraction Integer, "failed")
      ++ rationalIfCan(n) creates a rational number, or returns "failed" if this is not possible.
   random   : () -> %
      ++ random() creates a random element.
   random   : % -> %
      ++ random(a) creates a random element from 0 to \spad{n-1}.
   copy     : % -> %
      ++ copy(n) gives a copy of n.
   inc      : % -> %
      ++ inc(x) returns \spad{x + 1}.
   dec      : % -> %
      ++ dec(x) returns \spad{x - 1}.
   mask     : % -> %
      ++ mask(n) returns \spad{2**n-1} (an n bit mask).
   addmod   : (%,%,%) -> %
      ++ addmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a+b mod p}.
   submod   : (%,%,%) -> %
      ++ submod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a-b mod p}.
   mulmod   : (%,%,%) -> %
      ++ mulmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a*b mod p}.
   powmod   : (%,%,%) -> %
      ++ powmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a**b mod p}.
   invmod   : (%,%) -> %
      ++ invmod(a,b), \spad{0<=a<b>1}, \spad{(a,b)=1} means \spad{1/a mod b}.
   canonicalUnitNormal
--   commutative("*")    -- follows from the above

 add
   characteristic()         == 0
   differentiate x          == 0
   even? x                  == not odd? x
   positive? x              == x > 0
   copy x                   == x
   bit?(x, i)               == odd? shift(x, -i)
   mask n                   == dec shift(1, n)
   rational? x              == true
   euclideanSize(x)         ==
        x=0 => error "euclideanSize called on zero"
        x<0 => (-convert(x)@Integer)::NonNegativeInteger
        convert(x)@Integer::NonNegativeInteger
   convert(x:%):Float       == (convert(x)@Integer)::Float
   convert(x:%):DoubleFloat  == (convert(x)@Integer)::DoubleFloat
   convert(x:%):InputForm   == convert(convert(x)@Integer)
   retract(x:%):Integer     == convert(x)@Integer
   convert(x:%):Pattern(Integer)== convert(x)@Integer ::Pattern(Integer)
   factor x          == factor(x)$IntegerFactorizationPackage(%)
   squareFree x      == squareFree(x)$IntegerFactorizationPackage(%)
   prime? x          == prime?(x)$IntegerPrimesPackage(%)
   factorial x       == factorial(x)$IntegerCombinatoricFunctions(%)
   binomial(n, m)    == binomial(n, m)$IntegerCombinatoricFunctions(%)
   permutation(n, m) == permutation(n,m)$IntegerCombinatoricFunctions(%)
   retractIfCan(x:%):Union(Integer, "failed") == convert(x)@Integer

   init() == 0

   -- iterates in order 0,1,-1,2,-2,3,-3,...
   nextItem(n) ==
     zero? n => 1
     n>0 => -n
     1-n

   patternMatch(x, p, l) ==
     patternMatch(x, p, l)$PatternMatchIntegerNumberSystem(%)

   rational(x:%):Fraction(Integer) ==
     (convert(x)@Integer)::Fraction(Integer)

   rationalIfCan(x:%):Union(Fraction Integer, "failed") ==
     (convert(x)@Integer)::Fraction(Integer)

   symmetricRemainder(x, n) ==
      r := x rem n
      r = 0 => r
      if n < 0 then n:=-n
      r > 0 =>
         2 * r > n => r - n
         r
      2*r + n <= 0 => r + n
      r

   invmod(a, b) ==
      if negative? a then a := positiveRemainder(a, b)
      c := a; c1:% := 1
      d := b; d1:% := 0
      while not zero? d repeat
         q := c quo d
         r := c-q*d
         r1 := c1-q*d1
         c := d; c1 := d1
         d := r; d1 := r1
--      not one? c => error "inverse does not exist"
      not (c = 1) => error "inverse does not exist"
      negative? c1 => c1 + b
      c1

   powmod(x, n, p) ==
      if negative? x then x := positiveRemainder(x, p)
      zero? x => 0
      zero? n => 1
      y:% := 1
      z := x
      repeat
         if odd? n then y := mulmod(y, z, p)
         zero?(n := shift(n, -1)) => return y
         z := mulmod(z, z, p)

@

\section{domain SINT SingleInteger}

The definition of {\bf one?} has been rewritten 
as it relies on calling {\bf ONEP} which is a function specific
to Codemist Common Lisp but is not defined in Common Lisp.

<<domain SINT SingleInteger>>=
)abbrev domain SINT SingleInteger

-- following patch needed to deal with *:(I,%) -> %
-- affects behavior of SourceLevelSubset
--)bo $noSubsets := true
-- No longer - JHD !! still needed 5/3/91 BMT

++ Author:  Michael Monagan
++ Date Created:
++    January 1988
++ Change History:
++ Basic Operations: max, min,
++    not, and, or, xor, Not, And, Or
++ Related Constructors:
++ Keywords: single integer
++ Description: SingleInteger is intended to support machine integer
++ arithmetic.

-- MAXINT, BASE (machine integer constants)
-- MODULUS, MULTIPLIER (random number generator constants)


-- Lisp dependencies
-- EQ, ABSVAL, TIMES, INTEGER-LENGTH, HASHEQ, REMAINDER
-- QSLESSP, QSGREATERP, QSADD1, QSSUB1, QSMINUS, QSPLUS, QSDIFFERENCE
-- QSTIMES, QSREMAINDER, QSODDP, QSZEROP, QSMAX, QSMIN, QSNOT, QSAND
-- QSOR, QSXOR, QSLEFTSHIFT, QSADDMOD, QSDIFMOD, QSMULTMOD


SingleInteger(): Join(IntegerNumberSystem,OrderedFinite,Logic,OpenMath) with
   canonical
      ++ \spad{canonical} means that mathematical equality is implied by data structure equality.
   canonicalsClosed
      ++ \spad{canonicalClosed} means two positives multiply to give positive.
   noetherian
      ++ \spad{noetherian} all ideals are finitely generated (in fact principal).

   -- bit operations
   "not":   % -> %
      ++ not(n) returns the bit-by-bit logical {\em not} of the single integer n.
   "xor": (%, %) -> %
      ++ xor(n,m)  returns the bit-by-bit logical {\em xor} of
      ++ the single integers n and m.
   Not  : % -> %
      ++ Not(n) returns the bit-by-bit logical {\em not} of the single integer n.
   And  : (%,%) -> %
      ++ And(n,m)  returns the bit-by-bit logical {\em and} of
      ++ the single integers n and m.
   Or   : (%,%) -> %
      ++ Or(n,m)  returns the bit-by-bit logical {\em or} of
      ++ the single integers n and m.

 == SubDomain(Integer, SMINTP(#1)$Lisp) add

   seed : % := 1$Lisp               -- for random()
   MAXINT ==> _$ShortMaximum$Lisp
   MININT ==> _$ShortMinimum$Lisp
   BASE ==> 67108864$Lisp           -- 2**26
   MULTIPLIER ==> 314159269$Lisp    -- from Knuth's table
   MODULUS ==> 2147483647$Lisp      -- 2**31-1

   writeOMSingleInt(dev: OpenMathDevice, x: %): Void ==
    if x < 0 then
      OMputApp(dev)
      OMputSymbol(dev, "arith1", "unary_minus")
      OMputInteger(dev, convert(-x))
      OMputEndApp(dev)
    else
      OMputInteger(dev, convert(x))

   OMwrite(x: %): String ==
    s: String := ""
    sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
    dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
    OMputObject(dev)
    writeOMSingleInt(dev, x)
    OMputEndObject(dev)
    OMclose(dev)
    s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
    s

   OMwrite(x: %, wholeObj: Boolean): String ==
    s: String := ""
    sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
    dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
    if wholeObj then
      OMputObject(dev)
    writeOMSingleInt(dev, x)
    if wholeObj then
      OMputEndObject(dev)
    OMclose(dev)
    s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
    s

   OMwrite(dev: OpenMathDevice, x: %): Void ==
    OMputObject(dev)
    writeOMSingleInt(dev, x)
    OMputEndObject(dev)

   OMwrite(dev: OpenMathDevice, x: %, wholeObj: Boolean): Void ==
    if wholeObj then
      OMputObject(dev)
    writeOMSingleInt(dev, x)
    if wholeObj then
      OMputEndObject(dev)

   reducedSystem m      == m pretend Matrix(Integer)
   coerce(x):OutputForm == rep(x)::OutputForm
   convert(x:%):Integer == rep x
   i:Integer * y:%      == i::% * y
   0         == 0$Lisp
   1         == 1$Lisp
   base()    == 2$Lisp
   max()     == MAXINT
   min()     == MININT
   x = y     == EQL(x,y)$Lisp
   ~ x       == LOGNOT(x)$Lisp
   not(x)    == LOGNOT(x)$Lisp
   _/_\(x,y) == LOGAND(x,y)$Lisp
   _\_/(x,y) == LOGIOR(x,y)$Lisp
   Not(x)    == LOGNOT(x)$Lisp
   And(x,y)  == LOGAND(x,y)$Lisp
   Or(x,y)   == LOGIOR(x,y)$Lisp
   xor(x,y)  == LOGXOR(x,y)$Lisp
   x < y     == QSLESSP(x,y)$Lisp
   inc x     == QSADD1(x)$Lisp
   dec x     == QSSUB1(x)$Lisp
   - x       == QSMINUS(x)$Lisp
   x + y     == QSPLUS(x,y)$Lisp
   x:% - y:% == QSDIFFERENCE(x,y)$Lisp
   x:% * y:% == QSTIMES(x,y)$Lisp
   x:% ** n:NonNegativeInteger == ((EXPT(x, n)$Lisp) pretend Integer)::%
   x quo y   == QSQUOTIENT(x,y)$Lisp
   x rem y   == QSREMAINDER(x,y)$Lisp
   divide(x, y)   == CONS(QSQUOTIENT(x,y)$Lisp,QSREMAINDER(x,y)$Lisp)$Lisp
   gcd(x,y)  == GCD(x,y)$Lisp
   abs(x)    == QSABSVAL(x)$Lisp
   odd?(x)   == QSODDP(x)$Lisp
   zero?(x)  == QSZEROP(x)$Lisp
--   one?(x)   == ONEP(x)$Lisp
   one?(x)   == x = 1
   max(x,y)  == QSMAX(x,y)$Lisp
   min(x,y)  == QSMIN(x,y)$Lisp
   hash(x)   == HASHEQ(x)$Lisp
   length(x) == INTEGER_-LENGTH(x)$Lisp
   shift(x,n)    == QSLEFTSHIFT(x,n)$Lisp
   mulmod(a,b,p) == QSMULTMOD(a,b,p)$Lisp
   addmod(a,b,p) == QSADDMOD(a,b,p)$Lisp
   submod(a,b,p) == QSDIFMOD(a,b,p)$Lisp
   negative?(x)  == QSMINUSP$Lisp x
   size() == (MAXINT -$Lisp MININT +$Lisp 1$Lisp)  pretend NonNegativeInteger
   index i ==
     i > size() => error ["index %1b out of range",i]
     per(i + MININT - 1$Lisp)
   lookup x ==
     (x -$Lisp MININT +$Lisp 1$Lisp) pretend PositiveInteger


   reducedSystem(m, v) ==
        [m pretend Matrix(Integer), v pretend Vector(Integer)]

   positiveRemainder(x,n) ==
      r := QSREMAINDER(x,n)$Lisp
      QSMINUSP(r)$Lisp =>
          QSMINUSP(n)$Lisp => QSDIFFERENCE(x, n)$Lisp
          QSPLUS(r, n)$Lisp
      r

   coerce(x:Integer):% ==
      (x <= rep max) and (x >= rep min) => per x
      error "integer too large to represent in a machine word"

   random() ==
      seed := REMAINDER(TIMES(MULTIPLIER,seed)$Lisp,MODULUS)$Lisp
      REMAINDER(seed,BASE)$Lisp

   random(n) == RANDOM(n)$Lisp

   UCA ==> Record(unit:%,canonical:%,associate:%)
   unitNormal x ==
      x < 0 => [-1,-x,-1]$UCA
      [1,x,1]$UCA

)bo $noSubsets := false

@


\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>>

<<category INS IntegerNumberSystem>>
<<domain SINT SingleInteger>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}