\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}.
   hash     : % -> %
      ++ hash(n) returns the hash code of n.
   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{INS.lsp BOOTSTRAP}
{\bf INS} depends on itself. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf INS}
category which we can write into the {\bf MID} directory. We compile 
the lisp code and copy the {\bf INS.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version. 
<<INS.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(SETQ |IntegerNumberSystem;AL| (QUOTE NIL)) 

(DEFUN |IntegerNumberSystem| NIL 
  (LET (#:G1068) 
    (COND 
      (|IntegerNumberSystem;AL|)
      (T (SETQ |IntegerNumberSystem;AL| (|IntegerNumberSystem;|)))))) 

(DEFUN |IntegerNumberSystem;| NIL (PROG (#0=#:G1066) 
  (RETURN 
    (PROG1 
      (LETT #0# 
        (|sublisV| 
          (PAIR 
            (QUOTE (#1=#:G1060 #2=#:G1061 #3=#:G1062 
                    #4=#:G1063 #5=#:G1064 #6=#:G1065))
            (LIST 
              (QUOTE (|Integer|))
              (QUOTE (|Integer|))
              (QUOTE (|Integer|))
              (QUOTE (|InputForm|))
              (QUOTE (|Pattern| (|Integer|)))
              (QUOTE (|Integer|))))
          (|Join| 
            (|UniqueFactorizationDomain|)
            (|EuclideanDomain|)
            (|OrderedIntegralDomain|)
            (|DifferentialRing|)
            (|ConvertibleTo| (QUOTE #1#))
            (|RetractableTo| (QUOTE #2#))
            (|LinearlyExplicitRingOver| (QUOTE #3#))
            (|ConvertibleTo| (QUOTE #4#))
            (|ConvertibleTo| (QUOTE #5#))
            (|PatternMatchable| (QUOTE #6#))
            (|CombinatorialFunctionCategory|)
            (|RealConstant|)
            (|CharacteristicZero|)
            (|StepThrough|)
            (|mkCategory| 
              (QUOTE |domain|)
              (QUOTE (
                ((|odd?| ((|Boolean|) $)) T)
                ((|even?| ((|Boolean|) $)) T)
                ((|base| ($)) T)
                ((|length| ($ $)) T)
                ((|shift| ($ $ $)) T)
                ((|bit?| ((|Boolean|) $ $)) T)
                ((|positiveRemainder| ($ $ $)) T)
                ((|symmetricRemainder| ($ $ $)) T)
                ((|rational?| ((|Boolean|) $)) T)
                ((|rational| ((|Fraction| (|Integer|)) $)) T)
                ((|rationalIfCan| 
                  ((|Union| (|Fraction| (|Integer|)) "failed") $)) T)
                ((|random| ($)) T)
                ((|random| ($ $)) T)
                ((|hash| ($ $)) T)
                ((|copy| ($ $)) T)
                ((|inc| ($ $)) T)
                ((|dec| ($ $)) T)
                ((|mask| ($ $)) T)
                ((|addmod| ($ $ $ $)) T)
                ((|submod| ($ $ $ $)) T)
                ((|mulmod| ($ $ $ $)) T)
                ((|powmod| ($ $ $ $)) T)
                ((|invmod| ($ $ $)) T)))
              (QUOTE ((|multiplicativeValuation| T) (|canonicalUnitNormal| T)))
              (QUOTE ((|Fraction| (|Integer|)) (|Boolean|))) NIL)))
         |IntegerNumberSystem|)
       (SETELT #0# 0 (QUOTE (|IntegerNumberSystem|))))))) 

(MAKEPROP (QUOTE |IntegerNumberSystem|) (QUOTE NILADIC) T) 

@
\section{INS-.lsp BOOTSTRAP}
{\bf INS-} depends on {\bf INS}. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf INS-}
category which we can write into the {\bf MID} directory. We compile 
the lisp code and copy the {\bf INS-.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version. 
<<INS-.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(PUT 
  (QUOTE |INS-;characteristic;Nni;1|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM NIL 0))) 

(DEFUN |INS-;characteristic;Nni;1| ($) 0) 

(DEFUN |INS-;differentiate;2S;2| (|x| $) 
  (|spadConstant| $ 9)) 

(DEFUN |INS-;even?;SB;3| (|x| $) 
 (COND 
   ((SPADCALL |x| (QREFELT $ 12)) (QUOTE NIL))
   ((QUOTE T) (QUOTE T)))) 

(DEFUN |INS-;positive?;SB;4| (|x| $) 
  (SPADCALL (|spadConstant| $ 9) |x| (QREFELT $ 14))) 

(PUT 
  (QUOTE |INS-;copy;2S;5|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM (|x|) |x|))) 

(DEFUN |INS-;copy;2S;5| (|x| $) |x|) 

(DEFUN |INS-;bit?;2SB;6| (|x| |i| $) 
  (SPADCALL 
    (SPADCALL |x| 
      (SPADCALL |i| (QREFELT $ 17))
      (QREFELT $ 18))
    (QREFELT $ 12))) 

(DEFUN |INS-;mask;2S;7| (|n| $) 
  (SPADCALL 
    (SPADCALL (|spadConstant| $ 20) |n| (QREFELT $ 18))
    (QREFELT $ 21))) 

(PUT 
  (QUOTE |INS-;rational?;SB;8|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM (|x|) (QUOTE T)))) 

(DEFUN |INS-;rational?;SB;8| (|x| $) 
  (QUOTE T)) 

(DEFUN |INS-;euclideanSize;SNni;9| (|x| $) 
  (PROG (#0=#:G1078 #1=#:G1079) 
    (RETURN 
      (COND 
        ((SPADCALL |x| (|spadConstant| $ 9) (QREFELT $ 24))
          (|error| "euclideanSize called on zero"))
        ((SPADCALL |x| (|spadConstant| $ 9) (QREFELT $ 14))
          (PROG1 
            (LETT #0# 
              (- (SPADCALL |x| (QREFELT $ 26)))
              |INS-;euclideanSize;SNni;9|)
            (|check-subtype| 
              (>= #0# 0)
              (QUOTE (|NonNegativeInteger|))
              #0#)))
        ((QUOTE T) 
          (PROG1 
            (LETT #1# 
              (SPADCALL |x| (QREFELT $ 26))
              |INS-;euclideanSize;SNni;9|)
            (|check-subtype| 
              (>= #1# 0)
              (QUOTE (|NonNegativeInteger|))
              #1#))))))) 

(DEFUN |INS-;convert;SF;10| (|x| $) 
  (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 29))) 

(DEFUN |INS-;convert;SDf;11| (|x| $) 
  (FLOAT (SPADCALL |x| (QREFELT $ 26)) MOST-POSITIVE-LONG-FLOAT)) 

(DEFUN |INS-;convert;SIf;12| (|x| $) 
  (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 34))) 

(DEFUN |INS-;retract;SI;13| (|x| $) 
  (SPADCALL |x| (QREFELT $ 26))) 

(DEFUN |INS-;convert;SP;14| (|x| $) 
  (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 38))) 

(DEFUN |INS-;factor;SF;15| (|x| $) 
  (SPADCALL |x| (QREFELT $ 42))) 

(DEFUN |INS-;squareFree;SF;16| (|x| $) 
  (SPADCALL |x| (QREFELT $ 45))) 

(DEFUN |INS-;prime?;SB;17| (|x| $) 
  (SPADCALL |x| (QREFELT $ 48))) 

(DEFUN |INS-;factorial;2S;18| (|x| $) 
  (SPADCALL |x| (QREFELT $ 51))) 

(DEFUN |INS-;binomial;3S;19| (|n| |m| $) 
  (SPADCALL |n| |m| (QREFELT $ 53))) 

(DEFUN |INS-;permutation;3S;20| (|n| |m| $) 
  (SPADCALL |n| |m| (QREFELT $ 55))) 

(DEFUN |INS-;retractIfCan;SU;21| (|x| $) 
  (CONS 0 (SPADCALL |x| (QREFELT $ 26)))) 

(DEFUN |INS-;init;S;22| ($) 
  (|spadConstant| $ 9)) 

(DEFUN |INS-;nextItem;SU;23| (|n| $) 
  (COND 
    ((SPADCALL |n| (QREFELT $ 60))
       (CONS 0 (|spadConstant| $ 20)))
    ((SPADCALL (|spadConstant| $ 9) |n| (QREFELT $ 14))
       (CONS 0 (SPADCALL |n| (QREFELT $ 17))))
    ((QUOTE T) 
       (CONS 0 (SPADCALL (|spadConstant| $ 20) |n| (QREFELT $ 61)))))) 

(DEFUN |INS-;patternMatch;SP2Pmr;24| (|x| |p| |l| $) 
  (SPADCALL |x| |p| |l| (QREFELT $ 66))) 

(DEFUN |INS-;rational;SF;25| (|x| $) 
  (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 70))) 

(DEFUN |INS-;rationalIfCan;SU;26| (|x| $) 
  (CONS 0 (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 70)))) 

(DEFUN |INS-;symmetricRemainder;3S;27| (|x| |n| $) 
  (PROG (|r|) 
    (RETURN 
      (SEQ 
        (LETT |r| 
          (SPADCALL |x| |n| (QREFELT $ 74))
          |INS-;symmetricRemainder;3S;27|)
        (EXIT 
          (COND 
            ((SPADCALL |r| (|spadConstant| $ 9) (QREFELT $ 24)) |r|)
            ((QUOTE T) 
              (SEQ 
                (COND 
                  ((SPADCALL |n| (|spadConstant| $ 9) (QREFELT $ 14))
                    (LETT |n| 
                      (SPADCALL |n| (QREFELT $ 17))
                      |INS-;symmetricRemainder;3S;27|))) 
                (EXIT 
                  (COND 
                    ((SPADCALL (|spadConstant| $ 9) |r| (QREFELT $ 14))
                      (COND 
                        ((SPADCALL |n| 
                            (SPADCALL 2 |r| (QREFELT $ 76))
                            (QREFELT $ 14))
                          (SPADCALL |r| |n| (QREFELT $ 61)))
                        ((QUOTE T) |r|)))
                    ((NULL 
                      (SPADCALL 
                         (|spadConstant| $ 9)
                         (SPADCALL 
                           (SPADCALL 2 |r| (QREFELT $ 76))
                           |n|
                           (QREFELT $ 77))
                         (QREFELT $ 14)))
                       (SPADCALL |r| |n| (QREFELT $ 77)))
                    ((QUOTE T) |r|))))))))))) 

(DEFUN |INS-;invmod;3S;28| (|a| |b| $) 
  (PROG (|q| |r| |r1| |c| |c1| |d| |d1|) 
    (RETURN 
      (SEQ 
        (COND 
          ((SPADCALL |a| (QREFELT $ 79))
            (LETT |a| (SPADCALL |a| |b| (QREFELT $ 80)) |INS-;invmod;3S;28|)))
        (LETT |c| |a| |INS-;invmod;3S;28|)
        (LETT |c1| (|spadConstant| $ 20) |INS-;invmod;3S;28|)
        (LETT |d| |b| |INS-;invmod;3S;28|)
        (LETT |d1| (|spadConstant| $ 9) |INS-;invmod;3S;28|)
        (SEQ G190 
          (COND 
            ((NULL 
              (COND 
                ((SPADCALL |d| (QREFELT $ 60)) (QUOTE NIL))
                ((QUOTE T) (QUOTE T))))
              (GO G191)))
          (SEQ 
            (LETT |q| (SPADCALL |c| |d| (QREFELT $ 81)) |INS-;invmod;3S;28|)
            (LETT |r| 
              (SPADCALL |c| (SPADCALL |q| |d| (QREFELT $ 82)) (QREFELT $ 61))
              |INS-;invmod;3S;28|)
            (LETT |r1| 
              (SPADCALL |c1| (SPADCALL |q| |d1| (QREFELT $ 82)) (QREFELT $ 61))
              |INS-;invmod;3S;28|)
            (LETT |c| |d| |INS-;invmod;3S;28|)
            (LETT |c1| |d1| |INS-;invmod;3S;28|)
            (LETT |d| |r| |INS-;invmod;3S;28|)
            (EXIT (LETT |d1| |r1| |INS-;invmod;3S;28|)))
          NIL
          (GO G190)
          G191
          (EXIT NIL))
        (COND 
          ((NULL (SPADCALL |c| (QREFELT $ 83)))
            (EXIT (|error| "inverse does not exist"))))
        (EXIT 
          (COND 
            ((SPADCALL |c1| (QREFELT $ 79)) (SPADCALL |c1| |b| (QREFELT $ 77)))
            ((QUOTE T) |c1|))))))) 

(DEFUN |INS-;powmod;4S;29| (|x| |n| |p| $) 
  (PROG (|y| #0=#:G1137 |z|) 
    (RETURN 
      (SEQ 
        (EXIT 
          (SEQ 
            (COND 
              ((SPADCALL |x| (QREFELT $ 79))
                (LETT |x| 
                  (SPADCALL |x| |p| (QREFELT $ 80))
                  |INS-;powmod;4S;29|)))
           (EXIT 
             (COND 
               ((SPADCALL |x| (QREFELT $ 60)) (|spadConstant| $ 9))
               ((SPADCALL |n| (QREFELT $ 60)) (|spadConstant| $ 20))
               ((QUOTE T) 
                 (SEQ 
                   (LETT |y| (|spadConstant| $ 20) |INS-;powmod;4S;29|)
                   (LETT |z| |x| |INS-;powmod;4S;29|)
                   (EXIT 
                     (SEQ G190 
                       NIL 
                       (SEQ 
                         (COND 
                           ((SPADCALL |n| (QREFELT $ 12))
                             (LETT |y| 
                               (SPADCALL |y| |z| |p| (QREFELT $ 85))
                               |INS-;powmod;4S;29|)))
                         (EXIT 
                           (COND 
                             ((SPADCALL 
                               (LETT |n| 
                                 (SPADCALL |n| 
                                   (SPADCALL 
                                     (|spadConstant| $ 20)
                                     (QREFELT $ 17))
                                   (QREFELT $ 18))
                                  |INS-;powmod;4S;29|)
                               (QREFELT $ 60))
                              (PROGN 
                                (LETT #0# |y| |INS-;powmod;4S;29|)
                                (GO #0#)))
                             ((QUOTE T) 
                               (LETT |z| 
                                 (SPADCALL |z| |z| |p| (QREFELT $ 85))
                                 |INS-;powmod;4S;29|)))))
                       NIL 
                       (GO G190)
                       G191
                       (EXIT NIL)))))))))
        #0# 
        (EXIT #0#))))) 

(DEFUN |IntegerNumberSystem&| (|#1|) 
  (PROG (DV$1 |dv$| $ |pv$|) 
    (RETURN 
      (PROGN 
        (LETT DV$1 (|devaluate| |#1|) . #0=(|IntegerNumberSystem&|))
        (LETT |dv$| (LIST (QUOTE |IntegerNumberSystem&|) DV$1) . #0#)
        (LETT $ (GETREFV 87) . #0#)
        (QSETREFV $ 0 |dv$|)
        (QSETREFV $ 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#))
        (|stuffDomainSlots| $)
        (QSETREFV $ 6 |#1|)
        $)))) 

(MAKEPROP 
  (QUOTE |IntegerNumberSystem&|)
  (QUOTE |infovec|)
  (LIST 
    (QUOTE 
      #(NIL NIL NIL NIL NIL NIL 
        (|local| |#1|)
        (|NonNegativeInteger|)
        |INS-;characteristic;Nni;1|
        (0 . |Zero|)
        |INS-;differentiate;2S;2|
        (|Boolean|)
        (4 . |odd?|)
        |INS-;even?;SB;3|
        (9 . <)
        |INS-;positive?;SB;4|
        |INS-;copy;2S;5|
        (15 . -)
        (20 . |shift|)
        |INS-;bit?;2SB;6|
        (26 . |One|)
        (30 . |dec|)
        |INS-;mask;2S;7|
        |INS-;rational?;SB;8|
        (35 . =)
        (|Integer|)
        (41 . |convert|)
        |INS-;euclideanSize;SNni;9|
        (|Float|)
        (46 . |coerce|)
        |INS-;convert;SF;10|
        (|DoubleFloat|)
        |INS-;convert;SDf;11|
        (|InputForm|)
        (51 . |convert|)
        |INS-;convert;SIf;12|
        |INS-;retract;SI;13|
        (|Pattern| 25)
        (56 . |coerce|)
        |INS-;convert;SP;14|
        (|Factored| 6)
        (|IntegerFactorizationPackage| 6)
        (61 . |factor|)
        (|Factored| $)
        |INS-;factor;SF;15|
        (66 . |squareFree|)
        |INS-;squareFree;SF;16|
        (|IntegerPrimesPackage| 6)
        (71 . |prime?|)
        |INS-;prime?;SB;17|
        (|IntegerCombinatoricFunctions| 6)
        (76 . |factorial|)
        |INS-;factorial;2S;18|
        (81 . |binomial|)
        |INS-;binomial;3S;19|
        (87 . |permutation|)
        |INS-;permutation;3S;20|
        (|Union| 25 (QUOTE "failed"))
        |INS-;retractIfCan;SU;21|
        |INS-;init;S;22|
        (93 . |zero?|)
        (98 . -)
        (|Union| $ (QUOTE "failed"))
        |INS-;nextItem;SU;23|
        (|PatternMatchResult| 25 6)
        (|PatternMatchIntegerNumberSystem| 6)
        (104 . |patternMatch|)
        (|PatternMatchResult| 25 $)
        |INS-;patternMatch;SP2Pmr;24|
        (|Fraction| 25)
        (111 . |coerce|)
        |INS-;rational;SF;25|
        (|Union| 69 (QUOTE "failed"))
        |INS-;rationalIfCan;SU;26|
        (116 . |rem|)
        (|PositiveInteger|)
        (122 . *)
        (128 . +)
        |INS-;symmetricRemainder;3S;27|
        (134 . |negative?|)
        (139 . |positiveRemainder|)
        (145 . |quo|)
        (151 . *)
        (157 . |one?|)
        |INS-;invmod;3S;28|
        (162 . |mulmod|)
        |INS-;powmod;4S;29|))
     (QUOTE 
       #(|symmetricRemainder| 169 |squareFree| 175 |retractIfCan| 180 
         |retract| 185 |rationalIfCan| 190 |rational?| 195 |rational| 200 
         |prime?| 205 |powmod| 210 |positive?| 217 |permutation| 222 
         |patternMatch| 228 |nextItem| 235 |mask| 240 |invmod| 245 |init| 251
         |factorial| 255 |factor| 260 |even?| 265 |euclideanSize| 270
         |differentiate| 275 |copy| 280 |convert| 285 |characteristic| 305
         |bit?| 309 |binomial| 315))
     (QUOTE NIL) 
     (CONS 
       (|makeByteWordVec2| 1 (QUOTE NIL))
       (CONS 
         (QUOTE #())
         (CONS 
           (QUOTE #())
           (|makeByteWordVec2| 86 
             (QUOTE 
               (0 6 0 9 1 6 11 0 12 2 6 11 0 0 14 1 6 0 0 17 2 6 0 0 0 18 0 6
                0 20 1 6 0 0 21 2 6 11 0 0 24 1 6 25 0 26 1 28 0 25 29 1 33 0
                25 34 1 37 0 25 38 1 41 40 6 42 1 41 40 6 45 1 47 11 6 48 1 50
                6 6 51 2 50 6 6 6 53 2 50 6 6 6 55 1 6 11 0 60 2 6 0 0 0 61 3
                65 64 6 37 64 66 1 69 0 25 70 2 6 0 0 0 74 2 6 0 75 0 76 2 6 0
                0 0 77 1 6 11 0 79 2 6 0 0 0 80 2 6 0 0 0 81 2 6 0 0 0 82 1 6
                11 0 83 3 6 0 0 0 0 85 2 0 0 0 0 78 1 0 43 0 46 1 0 57 0 58 1
                0 25 0 36 1 0 72 0 73 1 0 11 0 23 1 0 69 0 71 1 0 11 0 49 3 0
                0 0 0 0 86 1 0 11 0 15 2 0 0 0 0 56 3 0 67 0 37 67 68 1 0 62
                0 63 1 0 0 0 22 2 0 0 0 0 84 0 0 0 59 1 0 0 0 52 1 0 43 0 44
                1 0 11 0 13 1 0 7 0 27 1 0 0 0 10 1 0 0 0 16 1 0 31 0 32 1 0
                28 0 30 1 0 37 0 39 1 0 33 0 35 0 0 7 8 2 0 11 0 0 19 2 0 0
                0 0 54))))))
    (QUOTE |lookupComplete|))) 

@
\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,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).

   max      : () -> %
      ++ max() returns the largest single integer.
   min      : () -> %
      ++ min() returns the smallest single integer.

   -- bit operations
   "not":   % -> %
      ++ not(n) returns the bit-by-bit logical {\em not} of the single integer n.
   "~"  :   % -> %
      ++  ~ n returns the bit-by-bit logical {\em not } of the single integer n.
   "/\": (%, %) -> %
      ++ n /\ m  returns the bit-by-bit logical {\em and} of
      ++ the single integers n and m.
   "\/" : (%, %) -> %
      ++ n \/ m  returns the bit-by-bit logical {\em or} of
      ++ the single integers n and m.
   "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.

 == add

   seed : % := 1$Lisp               -- for random()
   MAXINT ==> MOST_-POSITIVE_-FIXNUM$Lisp
   MININT ==> MOST_-NEGATIVE_-FIXNUM$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 == (convert(x)@Integer)::OutputForm
   convert(x:%):Integer == x pretend Integer
   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


   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 <= max pretend Integer) and (x >= min pretend Integer) =>
        x pretend %
      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{SINT.lsp BOOTSTRAP}
<<SINT.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(DEFUN |SINT;writeOMSingleInt| (|dev| |x| $) 
  (SEQ 
    (COND 
      ((QSLESSP |x| 0)
        (SEQ 
          (SPADCALL |dev| (QREFELT $ 9))
          (SPADCALL |dev| "arith1" "unaryminus" (QREFELT $ 11))
          (SPADCALL |dev| (QSMINUS |x|) (QREFELT $ 13))
          (EXIT (SPADCALL |dev| (QREFELT $ 14)))))
      ((QUOTE T) (SPADCALL |dev| |x| (QREFELT $ 13)))))) 

(DEFUN |SINT;OMwrite;$S;2| (|x| $) 
  (PROG (|sp| |dev| |s|) 
    (RETURN 
      (SEQ 
        (LETT |s| "" |SINT;OMwrite;$S;2|)
        (LETT |sp| (OM-STRINGTOSTRINGPTR |s|) |SINT;OMwrite;$S;2|)
        (LETT |dev| 
          (SPADCALL |sp| (SPADCALL (QREFELT $ 16)) (QREFELT $ 17))
          |SINT;OMwrite;$S;2|)
        (SPADCALL |dev| (QREFELT $ 18))
        (|SINT;writeOMSingleInt| |dev| |x| $)
        (SPADCALL |dev| (QREFELT $ 19))
        (SPADCALL |dev| (QREFELT $ 20))
        (LETT |s| (OM-STRINGPTRTOSTRING |sp|) |SINT;OMwrite;$S;2|)
        (EXIT |s|))))) 

(DEFUN |SINT;OMwrite;$BS;3| (|x| |wholeObj| $) 
  (PROG (|sp| |dev| |s|) 
    (RETURN 
      (SEQ 
        (LETT |s| "" |SINT;OMwrite;$BS;3|)
        (LETT |sp| (OM-STRINGTOSTRINGPTR |s|) |SINT;OMwrite;$BS;3|)
        (LETT |dev| 
          (SPADCALL |sp| (SPADCALL (QREFELT $ 16)) (QREFELT $ 17))
          |SINT;OMwrite;$BS;3|)
        (COND (|wholeObj| (SPADCALL |dev| (QREFELT $ 18))))
        (|SINT;writeOMSingleInt| |dev| |x| $)
        (COND (|wholeObj| (SPADCALL |dev| (QREFELT $ 19))))
        (SPADCALL |dev| (QREFELT $ 20))
        (LETT |s| (OM-STRINGPTRTOSTRING |sp|) |SINT;OMwrite;$BS;3|)
        (EXIT |s|))))) 

(DEFUN |SINT;OMwrite;Omd$V;4| (|dev| |x| $) 
  (SEQ 
    (SPADCALL |dev| (QREFELT $ 18))
    (|SINT;writeOMSingleInt| |dev| |x| $)
    (EXIT (SPADCALL |dev| (QREFELT $ 19))))) 

(DEFUN |SINT;OMwrite;Omd$BV;5| (|dev| |x| |wholeObj| $) 
  (SEQ 
    (COND (|wholeObj| (SPADCALL |dev| (QREFELT $ 18))))
    (|SINT;writeOMSingleInt| |dev| |x| $)
    (EXIT (COND (|wholeObj| (SPADCALL |dev| (QREFELT $ 19))))))) 

(PUT 
  (QUOTE |SINT;reducedSystem;MM;6|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM (|m|) |m|))) 

(DEFUN |SINT;reducedSystem;MM;6| (|m| $) |m|) 

(DEFUN |SINT;coerce;$Of;7| (|x| $) 
  (SPADCALL |x| (QREFELT $ 30))) 

(PUT 
  (QUOTE |SINT;convert;$I;8|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM (|x|) |x|))) 

(DEFUN |SINT;convert;$I;8| (|x| $) |x|) 

(DEFUN |SINT;*;I2$;9| (|i| |y| $) 
  (QSTIMES (SPADCALL |i| (QREFELT $ 33)) |y|)) 

(PUT 
  (QUOTE |SINT;Zero;$;10|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM NIL 0))) 

(DEFUN |SINT;Zero;$;10| ($) 0) 

(PUT 
  (QUOTE |SINT;One;$;11|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM NIL 1))) 

(DEFUN |SINT;One;$;11| ($) 1) 

(PUT 
  (QUOTE |SINT;base;$;12|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM NIL 2))) 

(DEFUN |SINT;base;$;12| ($) 2) 

(PUT 
  (QUOTE |SINT;max;$;13|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM NIL MOST-POSITIVE-FIXNUM))) 

(DEFUN |SINT;max;$;13| ($) MOST-POSITIVE-FIXNUM) 

(PUT 
  (QUOTE |SINT;min;$;14|)
  (QUOTE |SPADreplace|)
  (QUOTE (XLAM NIL MOST-NEGATIVE-FIXNUM))) 

(DEFUN |SINT;min;$;14| ($) MOST-NEGATIVE-FIXNUM) 

(PUT 
  (QUOTE |SINT;=;2$B;15|)
  (QUOTE |SPADreplace|)
  (QUOTE EQL)) 

(DEFUN |SINT;=;2$B;15| (|x| |y| $) 
  (EQL |x| |y|)) 

(PUT 
  (QUOTE |SINT;~;2$;16|)
  (QUOTE |SPADreplace|)
  (QUOTE LOGNOT)) 

(DEFUN |SINT;~;2$;16| (|x| $) 
  (LOGNOT |x|)) 

(PUT 
  (QUOTE |SINT;not;2$;17|)
  (QUOTE |SPADreplace|)
  (QUOTE LOGNOT)) 

(DEFUN |SINT;not;2$;17| (|x| $) 
  (LOGNOT |x|)) 

(PUT 
  (QUOTE |SINT;/\\;3$;18|)
  (QUOTE |SPADreplace|)
  (QUOTE LOGAND)) 

(DEFUN |SINT;/\\;3$;18| (|x| |y| $) 
  (LOGAND |x| |y|)) 

(PUT 
  (QUOTE |SINT;\\/;3$;19|)
  (QUOTE |SPADreplace|)
  (QUOTE LOGIOR)) 

(DEFUN |SINT;\\/;3$;19| (|x| |y| $) 
  (LOGIOR |x| |y|)) 

(PUT 
  (QUOTE |SINT;Not;2$;20|)
  (QUOTE |SPADreplace|)
  (QUOTE LOGNOT)) 

(DEFUN |SINT;Not;2$;20| (|x| $) 
  (LOGNOT |x|)) 

(PUT
  (QUOTE |SINT;And;3$;21|)
  (QUOTE |SPADreplace|)
  (QUOTE LOGAND)) 

(DEFUN |SINT;And;3$;21| (|x| |y| $) 
  (LOGAND |x| |y|)) 

(PUT 
  (QUOTE |SINT;Or;3$;22|)
  (QUOTE |SPADreplace|)
  (QUOTE LOGIOR)) 

(DEFUN |SINT;Or;3$;22| (|x| |y| $) 
  (LOGIOR |x| |y|)) 

(PUT
  (QUOTE |SINT;xor;3$;23|)
  (QUOTE |SPADreplace|)
  (QUOTE LOGXOR)) 

(DEFUN |SINT;xor;3$;23| (|x| |y| $) 
  (LOGXOR |x| |y|)) 

(PUT
  (QUOTE |SINT;<;2$B;24|)
  (QUOTE |SPADreplace|)
  (QUOTE QSLESSP)) 

(DEFUN |SINT;<;2$B;24| (|x| |y| $) 
  (QSLESSP |x| |y|)) 

(PUT
  (QUOTE |SINT;inc;2$;25|)
  (QUOTE |SPADreplace|)
  (QUOTE QSADD1)) 

(DEFUN |SINT;inc;2$;25| (|x| $) 
  (QSADD1 |x|)) 

(PUT
  (QUOTE |SINT;dec;2$;26|)
  (QUOTE |SPADreplace|)
  (QUOTE QSSUB1)) 

(DEFUN |SINT;dec;2$;26| (|x| $) 
  (QSSUB1 |x|)) 

(PUT
  (QUOTE |SINT;-;2$;27|)
  (QUOTE |SPADreplace|)
  (QUOTE QSMINUS)) 

(DEFUN |SINT;-;2$;27| (|x| $) 
  (QSMINUS |x|)) 

(PUT 
  (QUOTE |SINT;+;3$;28|)
  (QUOTE |SPADreplace|)
  (QUOTE QSPLUS)) 

(DEFUN |SINT;+;3$;28| (|x| |y| $) 
  (QSPLUS |x| |y|)) 

(PUT 
  (QUOTE |SINT;-;3$;29|)
  (QUOTE |SPADreplace|)
  (QUOTE QSDIFFERENCE)) 

(DEFUN |SINT;-;3$;29| (|x| |y| $) 
  (QSDIFFERENCE |x| |y|)) 

(PUT 
  (QUOTE |SINT;*;3$;30|)
  (QUOTE |SPADreplace|)
  (QUOTE QSTIMES)) 

(DEFUN |SINT;*;3$;30| (|x| |y| $) 
  (QSTIMES |x| |y|)) 

(DEFUN |SINT;**;$Nni$;31| (|x| |n| $) 
  (SPADCALL (EXPT |x| |n|) (QREFELT $ 33))) 

(PUT 
  (QUOTE |SINT;quo;3$;32|)
  (QUOTE |SPADreplace|)
  (QUOTE QSQUOTIENT)) 

(DEFUN |SINT;quo;3$;32| (|x| |y| $) 
  (QSQUOTIENT |x| |y|)) 

(PUT 
  (QUOTE |SINT;rem;3$;33|)
  (QUOTE |SPADreplace|)
  (QUOTE QSREMAINDER)) 

(DEFUN |SINT;rem;3$;33| (|x| |y| $) 
  (QSREMAINDER |x| |y|)) 

(DEFUN |SINT;divide;2$R;34| (|x| |y| $) 
  (CONS (QSQUOTIENT |x| |y|) (QSREMAINDER |x| |y|))) 

(PUT (QUOTE |SINT;gcd;3$;35|) 
  (QUOTE |SPADreplace|) (QUOTE GCD)) 

(DEFUN |SINT;gcd;3$;35| (|x| |y| $) 
  (GCD |x| |y|)) 

(PUT 
  (QUOTE |SINT;abs;2$;36|)
  (QUOTE |SPADreplace|)
  (QUOTE QSABSVAL)) 

(DEFUN |SINT;abs;2$;36| (|x| $) 
  (QSABSVAL |x|)) 

(PUT 
  (QUOTE |SINT;odd?;$B;37|)
  (QUOTE |SPADreplace|)
  (QUOTE QSODDP)) 

(DEFUN |SINT;odd?;$B;37| (|x| $) 
  (QSODDP |x|)) 

(PUT 
  (QUOTE |SINT;zero?;$B;38|)
  (QUOTE |SPADreplace|)
  (QUOTE QSZEROP)) 

(DEFUN |SINT;zero?;$B;38| (|x| $) 
  (QSZEROP |x|)) 

(PUT 
  (QUOTE |SINT;max;3$;39|)
  (QUOTE |SPADreplace|)
  (QUOTE QSMAX)) 

(DEFUN |SINT;max;3$;39| (|x| |y| $) 
  (QSMAX |x| |y|)) 

(PUT 
  (QUOTE |SINT;min;3$;40|)
  (QUOTE |SPADreplace|)
  (QUOTE QSMIN)) 

(DEFUN |SINT;min;3$;40| (|x| |y| $) 
  (QSMIN |x| |y|)) 

(PUT 
  (QUOTE |SINT;hash;2$;41|) 
  (QUOTE |SPADreplace|)
  (QUOTE HASHEQ)) 

(DEFUN |SINT;hash;2$;41| (|x| $) 
  (HASHEQ |x|)) 

(PUT 
  (QUOTE |SINT;length;2$;42|)
  (QUOTE |SPADreplace|)
  (QUOTE INTEGER-LENGTH)) 

(DEFUN |SINT;length;2$;42| (|x| $) 
  (INTEGER-LENGTH |x|)) 

(PUT 
  (QUOTE |SINT;shift;3$;43|)
  (QUOTE |SPADreplace|)
  (QUOTE QSLEFTSHIFT)) 

(DEFUN |SINT;shift;3$;43| (|x| |n| $) 
  (QSLEFTSHIFT |x| |n|)) 

(PUT 
  (QUOTE |SINT;mulmod;4$;44|)
  (QUOTE |SPADreplace|)
  (QUOTE QSMULTMOD)) 

(DEFUN |SINT;mulmod;4$;44| (|a| |b| |p| $) 
  (QSMULTMOD |a| |b| |p|)) 

(PUT 
  (QUOTE |SINT;addmod;4$;45|)
  (QUOTE |SPADreplace|)
  (QUOTE QSADDMOD)) 

(DEFUN |SINT;addmod;4$;45| (|a| |b| |p| $) 
  (QSADDMOD |a| |b| |p|)) 

(PUT 
  (QUOTE |SINT;submod;4$;46|)
  (QUOTE |SPADreplace|)
  (QUOTE QSDIFMOD)) 

(DEFUN |SINT;submod;4$;46| (|a| |b| |p| $) 
  (QSDIFMOD |a| |b| |p|)) 

(PUT 
  (QUOTE |SINT;negative?;$B;47|)
  (QUOTE |SPADreplace|)
  (QUOTE QSMINUSP)) 

(DEFUN |SINT;negative?;$B;47| (|x| $) 
  (QSMINUSP |x|)) 

(PUT 
  (QUOTE |SINT;reducedSystem;MVR;48|)
  (QUOTE |SPADreplace|)
  (QUOTE CONS)) 

(DEFUN |SINT;reducedSystem;MVR;48| (|m| |v| $) 
  (CONS |m| |v|)) 

(DEFUN |SINT;positiveRemainder;3$;49| (|x| |n| $) 
  (PROG (|r|) 
    (RETURN 
      (SEQ 
        (LETT |r| (QSREMAINDER |x| |n|) |SINT;positiveRemainder;3$;49|)
        (EXIT 
          (COND 
            ((QSMINUSP |r|) 
              (COND 
                ((QSMINUSP |n|) (QSDIFFERENCE |x| |n|))
                ((QUOTE T) (QSPLUS |r| |n|))))
            ((QUOTE T) |r|))))))) 

(DEFUN |SINT;coerce;I$;50| (|x| $) 
  (SEQ 
    (COND 
      ((NULL (< MOST-POSITIVE-FIXNUM |x|))
        (COND ((NULL (< |x| MOST-NEGATIVE-FIXNUM)) (EXIT |x|)))))
     (EXIT (|error| "integer too large to represent in a machine word")))) 

(DEFUN |SINT;random;$;51| ($) 
  (SEQ 
    (SETELT $ 6 (REMAINDER (TIMES 314159269 (QREFELT $ 6)) 2147483647))
    (EXIT (REMAINDER (QREFELT $ 6) 67108864)))) 

(PUT 
  (QUOTE |SINT;random;2$;52|)
  (QUOTE |SPADreplace|)
  (QUOTE RANDOM)) 

(DEFUN |SINT;random;2$;52| (|n| $) 
  (RANDOM |n|)) 

(DEFUN |SINT;unitNormal;$R;53| (|x| $) 
  (COND 
    ((QSLESSP |x| 0) (VECTOR -1 (QSMINUS |x|) -1))
    ((QUOTE T) (VECTOR 1 |x| 1)))) 

(DEFUN |SingleInteger| NIL 
  (PROG NIL 
    (RETURN 
      (PROG (#0=#:G1358) 
        (RETURN 
          (COND 
            ((LETT #0# 
                (HGET |$ConstructorCache| (QUOTE |SingleInteger|))
                |SingleInteger|)
              (|CDRwithIncrement| (CDAR #0#)))
            ((QUOTE T) 
              (UNWIND-PROTECT 
                (PROG1 
                  (CDDAR 
                    (HPUT 
                      |$ConstructorCache| 
                      (QUOTE |SingleInteger|)
                      (LIST (CONS NIL (CONS 1 (|SingleInteger;|))))))
                  (LETT #0# T |SingleInteger|))
                (COND 
                  ((NOT #0#)
                     (HREM |$ConstructorCache| 
                       (QUOTE |SingleInteger|)))))))))))) 

(DEFUN |SingleInteger;| NIL 
  (PROG (|dv$| $ |pv$|) 
    (RETURN 
      (PROGN 
        (LETT |dv$| (QUOTE (|SingleInteger|)) . #0=(|SingleInteger|))
        (LETT $ (GETREFV 103) . #0#)
        (QSETREFV $ 0 |dv$|)
        (QSETREFV $ 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#))
        (|haddProp| |$ConstructorCache| (QUOTE |SingleInteger|) NIL (CONS 1 $))
        (|stuffDomainSlots| $) (QSETREFV $ 6 1) $)))) 

(MAKEPROP 
  (QUOTE |SingleInteger|)
  (QUOTE |infovec|)
  (LIST 
    (QUOTE 
      #(NIL NIL NIL NIL NIL NIL 
        (QUOTE |seed|)
        (|Void|)
        (|OpenMathDevice|)
        (0 . |OMputApp|)
        (|String|)
        (5 . |OMputSymbol|)
        (|Integer|)
        (12 . |OMputInteger|)
        (18 . |OMputEndApp|)
        (|OpenMathEncoding|)
        (23 . |OMencodingXML|)
        (27 . |OMopenString|)
        (33 . |OMputObject|)
        (38 . |OMputEndObject|)
        (43 . |OMclose|)
        |SINT;OMwrite;$S;2| 
        (|Boolean|)
        |SINT;OMwrite;$BS;3|
        |SINT;OMwrite;Omd$V;4|
        |SINT;OMwrite;Omd$BV;5|
        (|Matrix| 12)
        (|Matrix| $)
        |SINT;reducedSystem;MM;6|
        (|OutputForm|)
        (48 . |coerce|)
        |SINT;coerce;$Of;7|
        |SINT;convert;$I;8|
        (53 . |coerce|)
        |SINT;*;I2$;9|
        (CONS IDENTITY (FUNCALL (|dispatchFunction| |SINT;Zero;$;10|) $))
        (CONS IDENTITY (FUNCALL (|dispatchFunction| |SINT;One;$;11|) $))
        |SINT;base;$;12|
        |SINT;max;$;13|
        |SINT;min;$;14|
        |SINT;=;2$B;15|
        |SINT;~;2$;16|
        |SINT;not;2$;17|
        |SINT;/\\;3$;18|
        |SINT;\\/;3$;19|
        |SINT;Not;2$;20|
        |SINT;And;3$;21|
        |SINT;Or;3$;22|
        |SINT;xor;3$;23|
        |SINT;<;2$B;24|
        |SINT;inc;2$;25|
        |SINT;dec;2$;26|
        |SINT;-;2$;27|
        |SINT;+;3$;28|
        |SINT;-;3$;29|
        |SINT;*;3$;30|
        (|NonNegativeInteger|)
        |SINT;**;$Nni$;31|
        |SINT;quo;3$;32|
        |SINT;rem;3$;33|
        (|Record| (|:| |quotient| $) (|:| |remainder| $))
        |SINT;divide;2$R;34|
        |SINT;gcd;3$;35|
        |SINT;abs;2$;36|
        |SINT;odd?;$B;37|
        |SINT;zero?;$B;38|
        |SINT;max;3$;39|
        |SINT;min;3$;40|
        |SINT;hash;2$;41|
        |SINT;length;2$;42|
        |SINT;shift;3$;43|
        |SINT;mulmod;4$;44|
        |SINT;addmod;4$;45|
        |SINT;submod;4$;46|
        |SINT;negative?;$B;47|
        (|Record| (|:| |mat| 26) (|:| |vec| (|Vector| 12)))
        (|Vector| $)
        |SINT;reducedSystem;MVR;48|
        |SINT;positiveRemainder;3$;49|
        |SINT;coerce;I$;50|
        |SINT;random;$;51|
        |SINT;random;2$;52|
        (|Record| (|:| |unit| $) (|:| |canonical| $) (|:| |associate| $))
        |SINT;unitNormal;$R;53|
        (|Union| 85 (QUOTE "failed"))
        (|Fraction| 12)
        (|Union| $ (QUOTE "failed"))
        (|Float|)
        (|DoubleFloat|)
        (|Pattern| 12)
        (|PatternMatchResult| 12 $)
        (|InputForm|)
        (|Union| 12 (QUOTE "failed"))
        (|Record| (|:| |coef| 94) (|:| |generator| $))
        (|List| $)
        (|Union| 94 (QUOTE "failed"))
        (|Record| (|:| |coef1| $) (|:| |coef2| $) (|:| |generator| $))
        (|Record| (|:| |coef1| $) (|:| |coef2| $))
        (|Union| 97 (QUOTE "failed"))
        (|Factored| $)
        (|SparseUnivariatePolynomial| $)
        (|PositiveInteger|)
        (|SingleInteger|)))
     (QUOTE 
       #(~= 58 ~ 64 |zero?| 69 |xor| 74 |unitNormal| 80 |unitCanonical| 85 
         |unit?| 90 |symmetricRemainder| 95 |subtractIfCan| 101 |submod| 107 
         |squareFreePart| 114 |squareFree| 119 |sizeLess?| 124 |sign| 130 
         |shift| 135 |sample| 141 |retractIfCan| 145 |retract| 150 |rem| 155 
         |reducedSystem| 161 |recip| 172 |rationalIfCan| 177 |rational?| 182 
         |rational| 187 |random| 192 |quo| 201 |principalIdeal| 207 
         |prime?| 212 |powmod| 217 |positiveRemainder| 224 |positive?| 230 
         |permutation| 235 |patternMatch| 241 |one?| 248 |odd?| 253 |not| 258
         |nextItem| 263 |negative?| 268 |multiEuclidean| 273 |mulmod| 279
         |min| 286 |max| 296 |mask| 306 |length| 311 |lcm| 316 |latex| 327
         |invmod| 332 |init| 338 |inc| 342 |hash| 347 |gcdPolynomial| 357
         |gcd| 363 |factorial| 374 |factor| 379 |extendedEuclidean| 384
         |exquo| 397 |expressIdealMember| 403 |even?| 409 |euclideanSize| 414
         |divide| 419 |differentiate| 425 |dec| 436 |copy| 441 |convert| 446
         |coerce| 471 |characteristic| 491 |bit?| 495 |binomial| 501
         |base| 507 |associates?| 511 |addmod| 517 |abs| 524 ^ 529 |\\/| 541
         |Zero| 547 |Or| 551 |One| 557 |OMwrite| 561 |Not| 585 D 590
         |And| 601 >= 607 > 613 = 619 <= 625 < 631 |/\\| 637 - 643 + 654
          ** 660 * 672))
     (QUOTE (
       (|noetherian| . 0)
       (|canonicalsClosed| . 0)
       (|canonical| . 0)
       (|canonicalUnitNormal| . 0)
       (|multiplicativeValuation| . 0)
       (|noZeroDivisors| . 0)
       ((|commutative| "*") . 0)
       (|rightUnitary| . 0)
       (|leftUnitary| . 0)
       (|unitsKnown| . 0)))
     (CONS 
       (|makeByteWordVec2| 1 
         (QUOTE (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
                 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
                 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)))
       (CONS
         (QUOTE 
           #(|IntegerNumberSystem&| |EuclideanDomain&|
             |UniqueFactorizationDomain&| NIL NIL |GcdDomain&|
             |IntegralDomain&| |Algebra&| |Module&| NIL |Module&| NIL NIL
             |Module&| NIL |DifferentialRing&| |OrderedRing&| NIL |Module&|
             NIL |Module&| NIL NIL NIL NIL NIL NIL |Ring&| NIL NIL NIL NIL
             NIL NIL NIL NIL NIL NIL NIL NIL NIL |AbelianGroup&| NIL NIL
             |AbelianMonoid&| |Monoid&| NIL NIL NIL NIL |OrderedSet&|
             |AbelianSemiGroup&| |SemiGroup&| |Logic&| NIL |SetCategory&| NIL
             NIL NIL NIL |RetractableTo&| NIL NIL NIL |RetractableTo&| NIL NIL
             NIL NIL NIL NIL |RetractableTo&| NIL |BasicType&| NIL))
         (CONS
           (QUOTE 
             #((|IntegerNumberSystem|) (|EuclideanDomain|) 
               (|UniqueFactorizationDomain|) (|PrincipalIdealDomain|) 
               (|OrderedIntegralDomain|) (|GcdDomain|) (|IntegralDomain|) 
               (|Algebra| $$) (|Module| 12) (|LinearlyExplicitRingOver| 12) 
               (|Module| #0=#:G1062) (|LinearlyExplicitRingOver| #0#) 
               (|CharacteristicZero|) (|Module| #1=#:G106217) 
               (|LinearlyExplicitRingOver| #1#) (|DifferentialRing|) 
               (|OrderedRing|) (|CommutativeRing|) (|Module| |t#1|) 
               (|EntireRing|) (|Module| $$) (|BiModule| 12 12) 
               (|BiModule| #0# #0#) (|BiModule| #1# #1#) 
               (|OrderedAbelianGroup|) (|BiModule| |t#1| |t#1|) 
               (|BiModule| $$ $$) (|Ring|) (|RightModule| 12) 
               (|LeftModule| 12) (|RightModule| #0#) (|LeftModule| #0#) 
               (|RightModule| #1#) (|LeftModule| #1#) 
               (|OrderedCancellationAbelianMonoid|) (|RightModule| |t#1|) 
               (|LeftModule| |t#1|) (|LeftModule| $$) (|Rng|) 
               (|RightModule| $$) (|OrderedAbelianMonoid|) (|AbelianGroup|) 
               (|OrderedAbelianSemiGroup|) (|CancellationAbelianMonoid|) 
               (|AbelianMonoid|) (|Monoid|) (|PatternMatchable| 12) 
               (|PatternMatchable| #:G1065) (|StepThrough|) 
               (|PatternMatchable| #:G106220) (|OrderedSet|) 
               (|AbelianSemiGroup|) (|SemiGroup|) (|Logic|) (|RealConstant|) 
               (|SetCategory|) (|OpenMath|) (|CoercibleTo| #:G82356) 
               (|ConvertibleTo| 89) (|ConvertibleTo| 91) (|RetractableTo| 12) 
               (|ConvertibleTo| 12) (|ConvertibleTo| #:G1064) 
               (|ConvertibleTo| #:G1063) (|RetractableTo| #:G1061) 
               (|ConvertibleTo| #:G1060) (|ConvertibleTo| 87) 
               (|ConvertibleTo| 88) (|CombinatorialFunctionCategory|) 
               (|ConvertibleTo| #:G106219) (|ConvertibleTo| #:G106218) 
               (|RetractableTo| #:G106216) (|ConvertibleTo| #:G106215) 
               (|BasicType|) (|CoercibleTo| 29)))
             (|makeByteWordVec2| 102 
               (QUOTE 
                 (1 8 7 0 9 3 8 7 0 10 10 11 2 8 7 0 12 13 1 8 7 0 14 0 15 0
                  16 2 8 0 10 15 17 1 8 7 0 18 1 8 7 0 19 1 8 7 0 20 1 12 29
                  0 30 1 0 0 12 33 2 0 22 0 0 1 1 0 0 0 41 1 0 22 0 65 2 0 0 
                  0 0 48 1 0 82 0 83 1 0 0 0 1 1 0 22 0 1 2 0 0 0 0 1 2 0 86
                  0 0 1 3 0 0 0 0 0 73 1 0 0 0 1 1 0 99 0 1 2 0 22 0 0 1 1 0
                  12 0 1 2 0 0 0 0 70 0 0 0 1 1 0 92 0 1 1 0 12 0 1 2 0 0 0 0
                  59 1 0 26 27 28 2 0 75 27 76 77 1 0 86 0 1 1 0 84 0 1 1 0
                  22 0 1 1 0 85 0 1 1 0 0 0 81 0 0 0 80 2 0 0 0 0 58 1 0 93
                  94 1 1 0 22 0 1 3 0 0 0 0 0 1 2 0 0 0 0 78 1 0 22 0 1 2 0 0
                  0 0 1 3 0 90 0 89 90 1 1 0 22 0 1 1 0 22 0 64 1 0 0 0 42 1
                  0 86 0 1 1 0 22 0 74 2 0 95 94 0 1 3 0 0 0 0 0 71 0 0 0 39
                  2 0 0 0 0 67 0 0 0 38 2 0 0 0 0 66 1 0 0 0 1 1 0 0 0 69 1 0
                  0 94 1 2 0 0 0 0 1 1 0 10 0 1 2 0 0 0 0 1 0 0 0 1 1 0 0 0 50
                  1 0 0 0 68 1 0 102 0 1 2 0 100 100 100 1 1 0 0 94 1 2 0 0 0
                  0 62 1 0 0 0 1 1 0 99 0 1 2 0 96 0 0 1 3 0 98 0 0 0 1 2 0 86
                  0 0 1 2 0 95 94 0 1 1 0 22 0 1 1 0 56 0 1 2 0 60 0 0 61 1 0
                  0 0 1 2 0 0 0 56 1 1 0 0 0 51 1 0 0 0 1 1 0 87 0 1 1 0 88 0
                  1 1 0 89 0 1 1 0 91 0 1 1 0 12 0 32 1 0 0 12 79 1 0 0 0 1 1
                  0 0 12 79 1 0 29 0 31 0 0 56 1 2 0 22 0 0 1 2 0 0 0 0 1 0 0
                  0 37 2 0 22 0 0 1 3 0 0 0 0 0 72 1 0 0 0 63 2 0 0 0 56 1 2 0
                  0 0 101 1 2 0 0 0 0 44 0 0 0 35 2 0 0 0 0 47 0 0 0 36 3 0 7
                  8 0 22 25 2 0 10 0 22 23 2 0 7 8 0 24 1 0 10 0 21 1 0 0 0 45
                  1 0 0 0 1 2 0 0 0 56 1 2 0 0 0 0 46 2 0 22 0 0 1 2 0 22 0 0
                  1 2 0 22 0 0 40 2 0 22 0 0 1 2 0 22 0 0 49 2 0 0 0 0 43 1 0
                  0 0 52 2 0 0 0 0 54 2 0 0 0 0 53 2 0 0 0 56 57 2 0 0 0 101 1
                  2 0 0 0 0 55 2 0 0 12 0 34 2 0 0 56 0 1 2 0 0 101 0 1))))))
     (QUOTE |lookupComplete|))) 

(MAKEPROP (QUOTE |SingleInteger|) (QUOTE NILADIC) T) 

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