Initial population.

1 files changed, 865 insertions, 0 deletions

diff --git a/src/algebra/integer.spad.pamphlet b/src/algebra/integer.spad.pamphlet
new file mode 100644
index 00000000..3aa12fa9
--- /dev/null
+++ b/src/algebra/integer.spad.pamphlet
@@ -0,0 +1,865 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra integer.spad}
+\author{James Davenport}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package INTSLPE IntegerSolveLinearPolynomialEquation}
+<<package INTSLPE IntegerSolveLinearPolynomialEquation>>=
+)abbrev package INTSLPE IntegerSolveLinearPolynomialEquation
+++ Author: Davenport
+++ Date Created: 1991
+++ Date Last Updated:
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++ This package provides the implementation for the
+++ \spadfun{solveLinearPolynomialEquation}
+++ operation over the integers. It uses a lifting technique
+++ from the package GenExEuclid
+IntegerSolveLinearPolynomialEquation(): C ==T
+ where
+  ZP ==> SparseUnivariatePolynomial Integer
+  C == with
+      solveLinearPolynomialEquation: (List ZP,ZP) -> Union(List ZP,"failed")
+           ++ solveLinearPolynomialEquation([f1, ..., fn], g)
+           ++ (where the fi are relatively prime to each other)
+           ++ returns a list of ai such that
+           ++ \spad{g/prod fi = sum ai/fi}
+           ++ or returns "failed" if no such list of ai's exists.
+  T == add
+      oldlp:List ZP := []
+      slpePrime:Integer:=(2::Integer)
+      oldtable:Vector List ZP := empty()
+      solveLinearPolynomialEquation(lp,p) ==
+         if (oldlp ^= lp) then
+            -- we have to generate a new table
+            deg:= _+/[degree u for u in lp]
+            ans:Union(Vector List ZP,"failed"):="failed"
+            slpePrime:=2147483647::Integer   -- 2**31 -1 : a prime
+                 -- a good test case for this package is
+                 --  ([x**31-1,x-2],2)
+            while (ans case "failed") repeat
+              ans:=tablePow(deg,slpePrime,lp)$GenExEuclid(Integer,ZP)
+              if (ans case "failed") then
+                 slpePrime:= prevPrime(slpePrime)$IntegerPrimesPackage(Integer)
+            oldtable:=(ans:: Vector List ZP)
+         answer:=solveid(p,slpePrime,oldtable)
+         answer
+
+@
+\section{domain INT Integer}
+The function {\bf one?} has been rewritten back to its original form.
+The NAG version called a lisp primitive that exists only in Codemist
+Common Lisp and is not defined in Common Lisp.
+<<domain INT Integer>>=
+)abbrev domain INT Integer
+++ Author:
+++ Date Created:
+++ Change History:
+++ Basic Operations:
+++ Related Constructors:
+++ Keywords: integer
+++ Description: \spadtype{Integer} provides the domain of arbitrary precision
+++ integers.
+
+Integer: Join(IntegerNumberSystem, ConvertibleTo String, OpenMath) with
+    random   : % -> %
+      ++ random(n) returns a random integer from 0 to \spad{n-1}.
+    canonical
+      ++ mathematical equality is data structure equality.
+    canonicalsClosed
+      ++ two positives multiply to give positive.
+    noetherian
+      ++ ascending chain condition on ideals.
+    infinite
+      ++ nextItem never returns "failed".
+ == add
+      ZP ==> SparseUnivariatePolynomial %
+      ZZP ==> SparseUnivariatePolynomial Integer
+      x,y: %
+      n: NonNegativeInteger
+
+      writeOMInt(dev: OpenMathDevice, x: %): Void ==
+        if x < 0 then
+          OMputApp(dev)
+          OMputSymbol(dev, "arith1", "unary__minus")
+          OMputInteger(dev, (-x) pretend Integer)
+          OMputEndApp(dev)
+        else
+          OMputInteger(dev, x pretend Integer)
+
+      OMwrite(x: %): String ==
+        s: String := ""
+        sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
+        dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
+        OMputObject(dev)
+        writeOMInt(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)
+        writeOMInt(dev, x)
+        if wholeObj then
+          OMputEndObject(dev)
+        OMclose(dev)
+        s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
+        s
+
+      OMwrite(dev: OpenMathDevice, x: %): Void ==
+        OMputObject(dev)
+        writeOMInt(dev, x)
+        OMputEndObject(dev)
+
+      OMwrite(dev: OpenMathDevice, x: %, wholeObj: Boolean): Void ==
+        if wholeObj then
+          OMputObject(dev)
+        writeOMInt(dev, x)
+        if wholeObj then
+          OMputEndObject(dev)
+
+      zero? x == ZEROP(x)$Lisp
+--      one? x == ONEP(x)$Lisp
+      one? x == x = 1
+      0 == 0$Lisp
+      1 == 1$Lisp
+      base()  == 2$Lisp
+      copy x  == x
+      inc  x  == x + 1
+      dec  x  == x - 1
+      hash x == SXHASH(x)$Lisp
+      negative? x == MINUSP(x)$Lisp
+      coerce(x):OutputForm == outputForm(x pretend Integer)
+      coerce(m:Integer):% == m pretend %
+      convert(x:%):Integer == x pretend Integer
+      length a == INTEGER_-LENGTH(a)$Lisp
+      addmod(a, b, p) ==
+         (c:=a + b) >= p => c - p
+         c
+      submod(a, b, p) ==
+         (c:=a - b) < 0 => c + p
+         c
+      mulmod(a, b, p) == (a * b) rem p
+      convert(x:%):Float       == coerce(x pretend Integer)$Float
+      convert(x:%):DoubleFloat  == coerce(x pretend Integer)$DoubleFloat
+      convert(x:%):InputForm   == convert(x pretend Integer)$InputForm
+      convert(x:%):String      == string(x pretend Integer)$String
+
+      latex(x:%):String ==
+        s : String := string(x pretend Integer)$String
+        (-1 < (x pretend Integer)) and ((x  pretend Integer) < 10) => s
+        concat("{", concat(s, "}")$String)$String
+
+      positiveRemainder(a, b) ==
+        negative?(r := a rem b) =>
+           negative? b => r - b
+           r + b
+        r
+
+      reducedSystem(m:Matrix %):Matrix(Integer) ==
+        m pretend Matrix(Integer)
+
+      reducedSystem(m:Matrix %, v:Vector %):
+       Record(mat:Matrix(Integer), vec:Vector(Integer)) ==
+        [m pretend Matrix(Integer), vec pretend Vector(Integer)]
+
+      abs(x) == ABS(x)$Lisp
+      random() == random()$Lisp
+      random(x) == RANDOM(x)$Lisp
+      x = y == EQL(x,y)$Lisp
+      x < y == (x<y)$Lisp
+      - x == (-x)$Lisp
+      x + y == (x+y)$Lisp
+      x - y == (x-y)$Lisp
+      x * y == (x*y)$Lisp
+      (m:Integer) * (y:%) == (m*y)$Lisp -- for subsumption problem
+      x ** n == EXPT(x,n)$Lisp
+      odd? x == ODDP(x)$Lisp
+      max(x,y) == MAX(x,y)$Lisp
+      min(x,y) == MIN(x,y)$Lisp
+      divide(x,y) == DIVIDE2(x,y)$Lisp
+      x quo y == QUOTIENT2(x,y)$Lisp
+      x rem y == REMAINDER2(x,y)$Lisp
+      shift(x, y) == ASH(x,y)$Lisp
+      x exquo y ==
+         zero? y => "failed"
+         zero?(x rem y) => x quo y
+         "failed"
+--      recip(x) == if one? x or x=-1 then x else "failed"
+      recip(x) == if (x = 1) or x=-1 then x else "failed"
+      gcd(x,y) == GCD(x,y)$Lisp
+      UCA ==> Record(unit:%,canonical:%,associate:%)
+      unitNormal x ==
+         x < 0 => [-1,-x,-1]$UCA
+         [1,x,1]$UCA
+      unitCanonical x == abs x
+      solveLinearPolynomialEquation(lp:List ZP,p:ZP):Union(List ZP,"failed") ==
+         solveLinearPolynomialEquation(lp pretend List ZZP,
+               p pretend ZZP)$IntegerSolveLinearPolynomialEquation pretend
+                     Union(List ZP,"failed")
+      squareFreePolynomial(p:ZP):Factored ZP ==
+        squareFree(p)$UnivariatePolynomialSquareFree(%,ZP)
+      factorPolynomial(p:ZP):Factored ZP ==
+         -- GaloisGroupFactorizer doesn't factor the content
+         -- so we have to do this by hand
+         pp:=primitivePart p
+         leadingCoefficient pp = leadingCoefficient p =>
+             factor(p)$GaloisGroupFactorizer(ZP)
+         mergeFactors(factor(pp)$GaloisGroupFactorizer(ZP),
+                        map(#1::ZP,
+                            factor((leadingCoefficient p exquo
+                                    leadingCoefficient pp)
+                                   ::%))$FactoredFunctions2(%,ZP)
+                                     )$FactoredFunctionUtilities(ZP)
+      factorSquareFreePolynomial(p:ZP):Factored ZP ==
+           factorSquareFree(p)$GaloisGroupFactorizer(ZP)
+      gcdPolynomial(p:ZP, q:ZP):ZP ==
+         zero? p => unitCanonical q
+         zero? q => unitCanonical p
+         gcd([p,q])$HeuGcd(ZP)
+--    myNextPrime: (%,NonNegativeInteger) -> %
+--    myNextPrime(x,n) ==
+--       nextPrime(x)$IntegerPrimesPackage(%)
+--    TT:=InnerModularGcd(%,ZP,67108859 pretend %,myNextPrime)
+--    gcdPolynomial(p,q) == modularGcd(p,q)$TT
+
+@
+\section{INT.lsp BOOTSTRAP}
+{\bf INT} depends on {\bf OINTDOM} which depends on {\bf ORDRING}
+which depends on {\bf INT}.
+We need to break this cycle to build
+the algebra. So we keep a cached copy of the translated {\bf INT}
+category which we can write into the {\bf MID} directory. We compile 
+the lisp code and copy the {\bf INT.o} file to the {\bf OUT} directory.
+This is eventually forcibly replaced by a recompiled version. 
+
+Note that this code is not included in the generated catdef.spad file.
+
+<<INT.lsp BOOTSTRAP>>=
+
+(|/VERSIONCHECK| 2) 
+
+(DEFUN |INT;writeOMInt| (|dev| |x| |$|) (SEQ (COND ((|<| |x| 0) (SEQ (SPADCALL |dev| (QREFELT |$| 8)) (SPADCALL |dev| "arith1" "unary_minus" (QREFELT |$| 10)) (SPADCALL |dev| (|-| |x|) (QREFELT |$| 12)) (EXIT (SPADCALL |dev| (QREFELT |$| 13))))) ((QUOTE T) (SPADCALL |dev| |x| (QREFELT |$| 12)))))) 
+
+(DEFUN |INT;OMwrite;$S;2| (|x| |$|) (PROG (|sp| |dev| |s|) (RETURN (SEQ (LETT |s| "" |INT;OMwrite;$S;2|) (LETT |sp| (|OM-STRINGTOSTRINGPTR| |s|) |INT;OMwrite;$S;2|) (LETT |dev| (SPADCALL |sp| (SPADCALL (QREFELT |$| 15)) (QREFELT |$| 16)) |INT;OMwrite;$S;2|) (SPADCALL |dev| (QREFELT |$| 17)) (|INT;writeOMInt| |dev| |x| |$|) (SPADCALL |dev| (QREFELT |$| 18)) (SPADCALL |dev| (QREFELT |$| 19)) (LETT |s| (|OM-STRINGPTRTOSTRING| |sp|) |INT;OMwrite;$S;2|) (EXIT |s|))))) 
+
+(DEFUN |INT;OMwrite;$BS;3| (|x| |wholeObj| |$|) (PROG (|sp| |dev| |s|) (RETURN (SEQ (LETT |s| "" |INT;OMwrite;$BS;3|) (LETT |sp| (|OM-STRINGTOSTRINGPTR| |s|) |INT;OMwrite;$BS;3|) (LETT |dev| (SPADCALL |sp| (SPADCALL (QREFELT |$| 15)) (QREFELT |$| 16)) |INT;OMwrite;$BS;3|) (COND (|wholeObj| (SPADCALL |dev| (QREFELT |$| 17)))) (|INT;writeOMInt| |dev| |x| |$|) (COND (|wholeObj| (SPADCALL |dev| (QREFELT |$| 18)))) (SPADCALL |dev| (QREFELT |$| 19)) (LETT |s| (|OM-STRINGPTRTOSTRING| |sp|) |INT;OMwrite;$BS;3|) (EXIT |s|))))) 
+
+(DEFUN |INT;OMwrite;Omd$V;4| (|dev| |x| |$|) (SEQ (SPADCALL |dev| (QREFELT |$| 17)) (|INT;writeOMInt| |dev| |x| |$|) (EXIT (SPADCALL |dev| (QREFELT |$| 18))))) 
+
+(DEFUN |INT;OMwrite;Omd$BV;5| (|dev| |x| |wholeObj| |$|) (SEQ (COND (|wholeObj| (SPADCALL |dev| (QREFELT |$| 17)))) (|INT;writeOMInt| |dev| |x| |$|) (EXIT (COND (|wholeObj| (SPADCALL |dev| (QREFELT |$| 18))))))) 
+
+(PUT (QUOTE |INT;zero?;$B;6|) (QUOTE |SPADreplace|) (QUOTE ZEROP)) 
+
+(DEFUN |INT;zero?;$B;6| (|x| |$|) (ZEROP |x|)) 
+
+(PUT (QUOTE |INT;Zero;$;7|) (QUOTE |SPADreplace|) (QUOTE (XLAM NIL 0))) 
+
+(DEFUN |INT;Zero;$;7| (|$|) 0) 
+
+(PUT (QUOTE |INT;One;$;8|) (QUOTE |SPADreplace|) (QUOTE (XLAM NIL 1))) 
+
+(DEFUN |INT;One;$;8| (|$|) 1) 
+
+(PUT (QUOTE |INT;base;$;9|) (QUOTE |SPADreplace|) (QUOTE (XLAM NIL 2))) 
+
+(DEFUN |INT;base;$;9| (|$|) 2) 
+
+(PUT (QUOTE |INT;copy;2$;10|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|x|) |x|))) 
+
+(DEFUN |INT;copy;2$;10| (|x| |$|) |x|) 
+
+(PUT (QUOTE |INT;inc;2$;11|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|x|) (|+| |x| 1)))) 
+
+(DEFUN |INT;inc;2$;11| (|x| |$|) (|+| |x| 1)) 
+
+(PUT (QUOTE |INT;dec;2$;12|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|x|) (|-| |x| 1)))) 
+
+(DEFUN |INT;dec;2$;12| (|x| |$|) (|-| |x| 1)) 
+
+(PUT (QUOTE |INT;hash;2$;13|) (QUOTE |SPADreplace|) (QUOTE SXHASH)) 
+
+(DEFUN |INT;hash;2$;13| (|x| |$|) (SXHASH |x|)) 
+
+(PUT (QUOTE |INT;negative?;$B;14|) (QUOTE |SPADreplace|) (QUOTE MINUSP)) 
+
+(DEFUN |INT;negative?;$B;14| (|x| |$|) (MINUSP |x|)) 
+
+(DEFUN |INT;coerce;$Of;15| (|x| |$|) (SPADCALL |x| (QREFELT |$| 35))) 
+
+(PUT (QUOTE |INT;coerce;2$;16|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|m|) |m|))) 
+
+(DEFUN |INT;coerce;2$;16| (|m| |$|) |m|) 
+
+(PUT (QUOTE |INT;convert;2$;17|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|x|) |x|))) 
+
+(DEFUN |INT;convert;2$;17| (|x| |$|) |x|) 
+
+(PUT (QUOTE |INT;length;2$;18|) (QUOTE |SPADreplace|) (QUOTE |INTEGER-LENGTH|)) 
+
+(DEFUN |INT;length;2$;18| (|a| |$|) (|INTEGER-LENGTH| |a|)) 
+
+(DEFUN |INT;addmod;4$;19| (|a| |b| |p| |$|) (PROG (|c| #1=#:G86338) (RETURN (SEQ (EXIT (SEQ (SEQ (LETT |c| (|+| |a| |b|) |INT;addmod;4$;19|) (EXIT (COND ((NULL (|<| |c| |p|)) (PROGN (LETT #1# (|-| |c| |p|) |INT;addmod;4$;19|) (GO #1#)))))) (EXIT |c|))) #1# (EXIT #1#))))) 
+
+(DEFUN |INT;submod;4$;20| (|a| |b| |p| |$|) (PROG (|c|) (RETURN (SEQ (LETT |c| (|-| |a| |b|) |INT;submod;4$;20|) (EXIT (COND ((|<| |c| 0) (|+| |c| |p|)) ((QUOTE T) |c|))))))) 
+
+(DEFUN |INT;mulmod;4$;21| (|a| |b| |p| |$|) (REMAINDER2 (|*| |a| |b|) |p|)) 
+
+(DEFUN |INT;convert;$F;22| (|x| |$|) (SPADCALL |x| (QREFELT |$| 44))) 
+
+(PUT (QUOTE |INT;convert;$Df;23|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|x|) (FLOAT |x| |MOST-POSITIVE-LONG-FLOAT|)))) 
+
+(DEFUN |INT;convert;$Df;23| (|x| |$|) (FLOAT |x| |MOST-POSITIVE-LONG-FLOAT|)) 
+
+(DEFUN |INT;convert;$If;24| (|x| |$|) (SPADCALL |x| (QREFELT |$| 49))) 
+
+(PUT (QUOTE |INT;convert;$S;25|) (QUOTE |SPADreplace|) (QUOTE STRINGIMAGE)) 
+
+(DEFUN |INT;convert;$S;25| (|x| |$|) (STRINGIMAGE |x|)) 
+
+(DEFUN |INT;latex;$S;26| (|x| |$|) (PROG (|s|) (RETURN (SEQ (LETT |s| (STRINGIMAGE |x|) |INT;latex;$S;26|) (COND ((|<| -1 |x|) (COND ((|<| |x| 10) (EXIT |s|))))) (EXIT (STRCONC "{" (STRCONC |s| "}"))))))) 
+
+(DEFUN |INT;positiveRemainder;3$;27| (|a| |b| |$|) (PROG (|r|) (RETURN (COND ((MINUSP (LETT |r| (REMAINDER2 |a| |b|) |INT;positiveRemainder;3$;27|)) (COND ((MINUSP |b|) (|-| |r| |b|)) ((QUOTE T) (|+| |r| |b|)))) ((QUOTE T) |r|))))) 
+
+(PUT (QUOTE |INT;reducedSystem;2M;28|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|m|) |m|))) 
+
+(DEFUN |INT;reducedSystem;2M;28| (|m| |$|) |m|) 
+
+(DEFUN |INT;reducedSystem;MVR;29| (|m| |v| |$|) (CONS |m| (QUOTE |vec|))) 
+
+(PUT (QUOTE |INT;abs;2$;30|) (QUOTE |SPADreplace|) (QUOTE ABS)) 
+
+(DEFUN |INT;abs;2$;30| (|x| |$|) (ABS |x|)) 
+
+(PUT (QUOTE |INT;random;$;31|) (QUOTE |SPADreplace|) (QUOTE |random|)) 
+
+(DEFUN |INT;random;$;31| (|$|) (|random|)) 
+
+(PUT (QUOTE |INT;random;2$;32|) (QUOTE |SPADreplace|) (QUOTE RANDOM)) 
+
+(DEFUN |INT;random;2$;32| (|x| |$|) (RANDOM |x|)) 
+
+(PUT (QUOTE |INT;=;2$B;33|) (QUOTE |SPADreplace|) (QUOTE EQL)) 
+
+(DEFUN |INT;=;2$B;33| (|x| |y| |$|) (EQL |x| |y|)) 
+
+(PUT (QUOTE |INT;<;2$B;34|) (QUOTE |SPADreplace|) (QUOTE |<|)) 
+
+(DEFUN |INT;<;2$B;34| (|x| |y| |$|) (|<| |x| |y|)) 
+
+(PUT (QUOTE |INT;-;2$;35|) (QUOTE |SPADreplace|) (QUOTE |-|)) 
+
+(DEFUN |INT;-;2$;35| (|x| |$|) (|-| |x|)) 
+
+(PUT (QUOTE |INT;+;3$;36|) (QUOTE |SPADreplace|) (QUOTE |+|)) 
+
+(DEFUN |INT;+;3$;36| (|x| |y| |$|) (|+| |x| |y|)) 
+
+(PUT (QUOTE |INT;-;3$;37|) (QUOTE |SPADreplace|) (QUOTE |-|)) 
+
+(DEFUN |INT;-;3$;37| (|x| |y| |$|) (|-| |x| |y|)) 
+
+(PUT (QUOTE |INT;*;3$;38|) (QUOTE |SPADreplace|) (QUOTE |*|)) 
+
+(DEFUN |INT;*;3$;38| (|x| |y| |$|) (|*| |x| |y|)) 
+
+(PUT (QUOTE |INT;*;3$;39|) (QUOTE |SPADreplace|) (QUOTE |*|)) 
+
+(DEFUN |INT;*;3$;39| (|m| |y| |$|) (|*| |m| |y|)) 
+
+(PUT (QUOTE |INT;**;$Nni$;40|) (QUOTE |SPADreplace|) (QUOTE EXPT)) 
+
+(DEFUN |INT;**;$Nni$;40| (|x| |n| |$|) (EXPT |x| |n|)) 
+
+(PUT (QUOTE |INT;odd?;$B;41|) (QUOTE |SPADreplace|) (QUOTE ODDP)) 
+
+(DEFUN |INT;odd?;$B;41| (|x| |$|) (ODDP |x|)) 
+
+(PUT (QUOTE |INT;max;3$;42|) (QUOTE |SPADreplace|) (QUOTE MAX)) 
+
+(DEFUN |INT;max;3$;42| (|x| |y| |$|) (MAX |x| |y|)) 
+
+(PUT (QUOTE |INT;min;3$;43|) (QUOTE |SPADreplace|) (QUOTE MIN)) 
+
+(DEFUN |INT;min;3$;43| (|x| |y| |$|) (MIN |x| |y|)) 
+
+(PUT (QUOTE |INT;divide;2$R;44|) (QUOTE |SPADreplace|) (QUOTE DIVIDE2)) 
+
+(DEFUN |INT;divide;2$R;44| (|x| |y| |$|) (DIVIDE2 |x| |y|)) 
+
+(PUT (QUOTE |INT;quo;3$;45|) (QUOTE |SPADreplace|) (QUOTE QUOTIENT2)) 
+
+(DEFUN |INT;quo;3$;45| (|x| |y| |$|) (QUOTIENT2 |x| |y|)) 
+
+(PUT (QUOTE |INT;rem;3$;46|) (QUOTE |SPADreplace|) (QUOTE REMAINDER2)) 
+
+(DEFUN |INT;rem;3$;46| (|x| |y| |$|) (REMAINDER2 |x| |y|)) 
+
+(PUT (QUOTE |INT;shift;3$;47|) (QUOTE |SPADreplace|) (QUOTE ASH)) 
+
+(DEFUN |INT;shift;3$;47| (|x| |y| |$|) (ASH |x| |y|)) 
+
+(DEFUN |INT;exquo;2$U;48| (|x| |y| |$|) (COND ((OR (ZEROP |y|) (NULL (ZEROP (REMAINDER2 |x| |y|)))) (CONS 1 "failed")) ((QUOTE T) (CONS 0 (QUOTIENT2 |x| |y|))))) 
+
+(DEFUN |INT;recip;$U;49| (|x| |$|) (COND ((OR (EQL |x| 1) (EQL |x| -1)) (CONS 0 |x|)) ((QUOTE T) (CONS 1 "failed")))) 
+
+(PUT (QUOTE |INT;gcd;3$;50|) (QUOTE |SPADreplace|) (QUOTE GCD)) 
+
+(DEFUN |INT;gcd;3$;50| (|x| |y| |$|) (GCD |x| |y|)) 
+
+(DEFUN |INT;unitNormal;$R;51| (|x| |$|) (COND ((|<| |x| 0) (VECTOR -1 (|-| |x|) -1)) ((QUOTE T) (VECTOR 1 |x| 1)))) 
+
+(PUT (QUOTE |INT;unitCanonical;2$;52|) (QUOTE |SPADreplace|) (QUOTE ABS)) 
+
+(DEFUN |INT;unitCanonical;2$;52| (|x| |$|) (ABS |x|)) 
+
+(DEFUN |INT;solveLinearPolynomialEquation| (|lp| |p| |$|) (SPADCALL |lp| |p| (QREFELT |$| 91))) 
+
+(DEFUN |INT;squareFreePolynomial| (|p| |$|) (SPADCALL |p| (QREFELT |$| 95))) 
+
+(DEFUN |INT;factorPolynomial| (|p| |$|) (PROG (|pp| #1=#:G86409) (RETURN (SEQ (LETT |pp| (SPADCALL |p| (QREFELT |$| 96)) |INT;factorPolynomial|) (EXIT (COND ((EQL (SPADCALL |pp| (QREFELT |$| 97)) (SPADCALL |p| (QREFELT |$| 97))) (SPADCALL |p| (QREFELT |$| 99))) ((QUOTE T) (SPADCALL (SPADCALL |pp| (QREFELT |$| 99)) (SPADCALL (CONS (FUNCTION |INT;factorPolynomial!0|) |$|) (SPADCALL (PROG2 (LETT #1# (SPADCALL (SPADCALL |p| (QREFELT |$| 97)) (SPADCALL |pp| (QREFELT |$| 97)) (QREFELT |$| 81)) |INT;factorPolynomial|) (QCDR #1#) (|check-union| (QEQCAR #1# 0) |$| #1#)) (QREFELT |$| 102)) (QREFELT |$| 106)) (QREFELT |$| 108))))))))) 
+
+(DEFUN |INT;factorPolynomial!0| (|#1| |$|) (SPADCALL |#1| (QREFELT |$| 100))) 
+
+(DEFUN |INT;factorSquareFreePolynomial| (|p| |$|) (SPADCALL |p| (QREFELT |$| 109))) 
+
+(DEFUN |INT;gcdPolynomial;3Sup;57| (|p| |q| |$|) (COND ((SPADCALL |p| (QREFELT |$| 110)) (SPADCALL |q| (QREFELT |$| 111))) ((SPADCALL |q| (QREFELT |$| 110)) (SPADCALL |p| (QREFELT |$| 111))) ((QUOTE T) (SPADCALL (LIST |p| |q|) (QREFELT |$| 114))))) 
+
+(DEFUN |Integer| NIL (PROG NIL (RETURN (PROG (#1=#:G86434) (RETURN (COND ((LETT #1# (HGET |$ConstructorCache| (QUOTE |Integer|)) |Integer|) (|CDRwithIncrement| (CDAR #1#))) ((QUOTE T) (|UNWIND-PROTECT| (PROG1 (CDDAR (HPUT |$ConstructorCache| (QUOTE |Integer|) (LIST (CONS NIL (CONS 1 (|Integer;|)))))) (LETT #1# T |Integer|)) (COND ((NOT #1#) (HREM |$ConstructorCache| (QUOTE |Integer|)))))))))))) 
+
+(DEFUN |Integer;| NIL (PROG (|dv$| |$| |pv$|) (RETURN (PROGN (LETT |dv$| (QUOTE (|Integer|)) . #1=(|Integer|)) (LETT |$| (GETREFV 130) . #1#) (QSETREFV |$| 0 |dv$|) (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #1#)) (|haddProp| |$ConstructorCache| (QUOTE |Integer|) NIL (CONS 1 |$|)) (|stuffDomainSlots| |$|) (QSETREFV |$| 69 (QSETREFV |$| 68 (CONS (|dispatchFunction| |INT;*;3$;39|) |$|))) |$|)))) 
+
+(MAKEPROP (QUOTE |Integer|) (QUOTE |infovec|) (LIST (QUOTE #(NIL NIL NIL NIL NIL NIL (|Void|) (|OpenMathDevice|) (0 . |OMputApp|) (|String|) (5 . |OMputSymbol|) (|Integer|) (12 . |OMputInteger|) (18 . |OMputEndApp|) (|OpenMathEncoding|) (23 . |OMencodingXML|) (27 . |OMopenString|) (33 . |OMputObject|) (38 . |OMputEndObject|) (43 . |OMclose|) |INT;OMwrite;$S;2| (|Boolean|) |INT;OMwrite;$BS;3| |INT;OMwrite;Omd$V;4| |INT;OMwrite;Omd$BV;5| |INT;zero?;$B;6| (CONS IDENTITY (FUNCALL (|dispatchFunction| |INT;Zero;$;7|) |$|)) (CONS IDENTITY (FUNCALL (|dispatchFunction| |INT;One;$;8|) |$|)) |INT;base;$;9| |INT;copy;2$;10| |INT;inc;2$;11| |INT;dec;2$;12| |INT;hash;2$;13| |INT;negative?;$B;14| (|OutputForm|) (48 . |outputForm|) |INT;coerce;$Of;15| |INT;coerce;2$;16| |INT;convert;2$;17| |INT;length;2$;18| |INT;addmod;4$;19| |INT;submod;4$;20| |INT;mulmod;4$;21| (|Float|) (53 . |coerce|) |INT;convert;$F;22| (|DoubleFloat|) |INT;convert;$Df;23| (|InputForm|) (58 . |convert|) |INT;convert;$If;24| |INT;convert;$S;25| |INT;latex;$S;26| |INT;positiveRemainder;3$;27| (|Matrix| 11) (|Matrix| |$|) |INT;reducedSystem;2M;28| (|Record| (|:| |mat| 54) (|:| |vec| (|Vector| 11))) (|Vector| |$|) |INT;reducedSystem;MVR;29| |INT;abs;2$;30| |INT;random;$;31| |INT;random;2$;32| |INT;=;2$B;33| |INT;<;2$B;34| |INT;-;2$;35| |INT;+;3$;36| |INT;-;3$;37| NIL NIL (|NonNegativeInteger|) |INT;**;$Nni$;40| |INT;odd?;$B;41| |INT;max;3$;42| |INT;min;3$;43| (|Record| (|:| |quotient| |$|) (|:| |remainder| |$|)) |INT;divide;2$R;44| |INT;quo;3$;45| |INT;rem;3$;46| |INT;shift;3$;47| (|Union| |$| (QUOTE "failed")) |INT;exquo;2$U;48| |INT;recip;$U;49| |INT;gcd;3$;50| (|Record| (|:| |unit| |$|) (|:| |canonical| |$|) (|:| |associate| |$|)) |INT;unitNormal;$R;51| |INT;unitCanonical;2$;52| (|Union| 88 (QUOTE "failed")) (|List| 89) (|SparseUnivariatePolynomial| 11) (|IntegerSolveLinearPolynomialEquation|) (63 . |solveLinearPolynomialEquation|) (|Factored| 93) (|SparseUnivariatePolynomial| |$$|) (|UnivariatePolynomialSquareFree| |$$| 93) (69 . |squareFree|) (74 . |primitivePart|) (79 . |leadingCoefficient|) (|GaloisGroupFactorizer| 93) (84 . |factor|) (89 . |coerce|) (|Factored| |$|) (94 . |factor|) (|Mapping| 93 |$$|) (|Factored| |$$|) (|FactoredFunctions2| |$$| 93) (99 . |map|) (|FactoredFunctionUtilities| 93) (105 . |mergeFactors|) (111 . |factorSquareFree|) (116 . |zero?|) (121 . |unitCanonical|) (|List| 93) (|HeuGcd| 93) (126 . |gcd|) (|SparseUnivariatePolynomial| |$|) |INT;gcdPolynomial;3Sup;57| (|Union| 118 (QUOTE "failed")) (|Fraction| 11) (|PatternMatchResult| 11 |$|) (|Pattern| 11) (|Union| 11 (QUOTE "failed")) (|Union| 123 (QUOTE "failed")) (|List| |$|) (|Record| (|:| |coef| 123) (|:| |generator| |$|)) (|Record| (|:| |coef1| |$|) (|:| |coef2| |$|)) (|Union| 125 (QUOTE "failed")) (|Record| (|:| |coef1| |$|) (|:| |coef2| |$|) (|:| |generator| |$|)) (|PositiveInteger|) (|SingleInteger|))) (QUOTE #(|~=| 131 |zero?| 137 |unitNormal| 142 |unitCanonical| 147 |unit?| 152 |symmetricRemainder| 157 |subtractIfCan| 163 |submod| 169 |squareFreePart| 176 |squareFree| 181 |sizeLess?| 186 |sign| 192 |shift| 197 |sample| 203 |retractIfCan| 207 |retract| 212 |rem| 217 |reducedSystem| 223 |recip| 234 |rationalIfCan| 239 |rational?| 244 |rational| 249 |random| 254 |quo| 263 |principalIdeal| 269 |prime?| 274 |powmod| 279 |positiveRemainder| 286 |positive?| 292 |permutation| 297 |patternMatch| 303 |one?| 310 |odd?| 315 |nextItem| 320 |negative?| 325 |multiEuclidean| 330 |mulmod| 336 |min| 343 |max| 349 |mask| 355 |length| 360 |lcm| 365 |latex| 376 |invmod| 381 |init| 387 |inc| 391 |hash| 396 |gcdPolynomial| 406 |gcd| 412 |factorial| 423 |factor| 428 |extendedEuclidean| 433 |exquo| 446 |expressIdealMember| 452 |even?| 458 |euclideanSize| 463 |divide| 468 |differentiate| 474 |dec| 485 |copy| 490 |convert| 495 |coerce| 525 |characteristic| 545 |bit?| 549 |binomial| 555 |base| 561 |associates?| 565 |addmod| 571 |abs| 578 |^| 583 |Zero| 595 |One| 599 |OMwrite| 603 D 627 |>=| 638 |>| 644 |=| 650 |<=| 656 |<| 662 |-| 668 |+| 679 |**| 685 |*| 697)) (QUOTE ((|infinite| . 0) (|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))) (CONS (QUOTE #(|IntegerNumberSystem&| |EuclideanDomain&| |UniqueFactorizationDomain&| NIL NIL |GcdDomain&| |IntegralDomain&| |Algebra&| NIL NIL |DifferentialRing&| |OrderedRing&| NIL NIL |Module&| NIL NIL |Ring&| NIL NIL NIL NIL NIL |AbelianGroup&| NIL NIL |AbelianMonoid&| |Monoid&| NIL NIL |OrderedSet&| |AbelianSemiGroup&| |SemiGroup&| NIL |SetCategory&| NIL NIL NIL NIL NIL NIL NIL |RetractableTo&| NIL |BasicType&| NIL)) (CONS (QUOTE #((|IntegerNumberSystem|) (|EuclideanDomain|) (|UniqueFactorizationDomain|) (|PrincipalIdealDomain|) (|OrderedIntegralDomain|) (|GcdDomain|) (|IntegralDomain|) (|Algebra| |$$|) (|CharacteristicZero|) (|LinearlyExplicitRingOver| 11) (|DifferentialRing|) (|OrderedRing|) (|CommutativeRing|) (|EntireRing|) (|Module| |$$|) (|OrderedAbelianGroup|) (|BiModule| |$$| |$$|) (|Ring|) (|OrderedCancellationAbelianMonoid|) (|LeftModule| |$$|) (|Rng|) (|RightModule| |$$|) (|OrderedAbelianMonoid|) (|AbelianGroup|) (|OrderedAbelianSemiGroup|) (|CancellationAbelianMonoid|) (|AbelianMonoid|) (|Monoid|) (|StepThrough|) (|PatternMatchable| 11) (|OrderedSet|) (|AbelianSemiGroup|) (|SemiGroup|) (|RealConstant|) (|SetCategory|) (|OpenMath|) (|ConvertibleTo| 9) (|ConvertibleTo| 43) (|ConvertibleTo| 46) (|CombinatorialFunctionCategory|) (|ConvertibleTo| 120) (|ConvertibleTo| 48) (|RetractableTo| 11) (|ConvertibleTo| 11) (|BasicType|) (|CoercibleTo| 34))) (|makeByteWordVec2| 129 (QUOTE (1 7 6 0 8 3 7 6 0 9 9 10 2 7 6 0 11 12 1 7 6 0 13 0 14 0 15 2 7 0 9 14 16 1 7 6 0 17 1 7 6 0 18 1 7 6 0 19 1 34 0 11 35 1 43 0 11 44 1 48 0 11 49 2 90 87 88 89 91 1 94 92 93 95 1 93 0 0 96 1 93 2 0 97 1 98 92 93 99 1 93 0 2 100 1 0 101 0 102 2 105 92 103 104 106 2 107 92 92 92 108 1 98 92 93 109 1 93 21 0 110 1 93 0 0 111 1 113 93 112 114 2 0 21 0 0 1 1 0 21 0 25 1 0 84 0 85 1 0 0 0 86 1 0 21 0 1 2 0 0 0 0 1 2 0 80 0 0 1 3 0 0 0 0 0 41 1 0 0 0 1 1 0 101 0 1 2 0 21 0 0 1 1 0 11 0 1 2 0 0 0 0 79 0 0 0 1 1 0 121 0 1 1 0 11 0 1 2 0 0 0 0 78 2 0 57 55 58 59 1 0 54 55 56 1 0 80 0 82 1 0 117 0 1 1 0 21 0 1 1 0 118 0 1 1 0 0 0 62 0 0 0 61 2 0 0 0 0 77 1 0 124 123 1 1 0 21 0 1 3 0 0 0 0 0 1 2 0 0 0 0 53 1 0 21 0 1 2 0 0 0 0 1 3 0 119 0 120 119 1 1 0 21 0 1 1 0 21 0 72 1 0 80 0 1 1 0 21 0 33 2 0 122 123 0 1 3 0 0 0 0 0 42 2 0 0 0 0 74 2 0 0 0 0 73 1 0 0 0 1 1 0 0 0 39 1 0 0 123 1 2 0 0 0 0 1 1 0 9 0 52 2 0 0 0 0 1 0 0 0 1 1 0 0 0 30 1 0 0 0 32 1 0 129 0 1 2 0 115 115 115 116 2 0 0 0 0 83 1 0 0 123 1 1 0 0 0 1 1 0 101 0 102 3 0 126 0 0 0 1 2 0 127 0 0 1 2 0 80 0 0 81 2 0 122 123 0 1 1 0 21 0 1 1 0 70 0 1 2 0 75 0 0 76 1 0 0 0 1 2 0 0 0 70 1 1 0 0 0 31 1 0 0 0 29 1 0 9 0 51 1 0 46 0 47 1 0 43 0 45 1 0 48 0 50 1 0 120 0 1 1 0 11 0 38 1 0 0 11 37 1 0 0 11 37 1 0 0 0 1 1 0 34 0 36 0 0 70 1 2 0 21 0 0 1 2 0 0 0 0 1 0 0 0 28 2 0 21 0 0 1 3 0 0 0 0 0 40 1 0 0 0 60 2 0 0 0 70 1 2 0 0 0 128 1 0 0 0 26 0 0 0 27 3 0 6 7 0 21 24 2 0 9 0 21 22 2 0 6 7 0 23 1 0 9 0 20 1 0 0 0 1 2 0 0 0 70 1 2 0 21 0 0 1 2 0 21 0 0 1 2 0 21 0 0 63 2 0 21 0 0 1 2 0 21 0 0 64 2 0 0 0 0 67 1 0 0 0 65 2 0 0 0 0 66 2 0 0 0 70 71 2 0 0 0 128 1 2 0 0 0 0 68 2 0 0 11 0 69 2 0 0 70 0 1 2 0 0 128 0 1)))))) (QUOTE |lookupComplete|))) 
+
+(MAKEPROP (QUOTE |Integer|) (QUOTE NILADIC) T) 
+@
+\section{domain NNI NonNegativeInteger}
+<<domain NNI NonNegativeInteger>>=
+)abbrev domain NNI NonNegativeInteger
+++ Author:
+++ Date Created:
+++ Change History:
+++ Basic Operations:
+++ Related Constructors:
+++ Keywords: integer
+++ Description: \spadtype{NonNegativeInteger} provides functions for non
+++   negative integers.
+NonNegativeInteger: Join(OrderedAbelianMonoidSup,Monoid) with
+            _quo : (%,%) -> %
+              ++ a quo b returns the quotient of \spad{a} and b, forgetting
+              ++ the remainder.
+            _rem : (%,%) -> %
+              ++ a rem b returns the remainder of \spad{a} and b.
+            gcd  : (%,%) -> %
+              ++ gcd(a,b) computes the greatest common divisor of two
+              ++ non negative integers \spad{a} and b.
+            divide: (%,%) -> Record(quotient:%,remainder:%)
+              ++ divide(a,b) returns a record containing both
+              ++ remainder and quotient.
+            _exquo: (%,%) -> Union(%,"failed")
+              ++ exquo(a,b) returns the quotient of \spad{a} and b, or "failed"
+              ++ if b is zero or \spad{a} rem b is zero.
+            shift: (%, Integer) -> %
+              ++ shift(a,i) shift \spad{a} by i bits.
+            random   : % -> %
+              ++ random(n) returns a random integer from 0 to \spad{n-1}.
+            commutative("*")
+              ++ commutative("*") means multiplication is commutative : \spad{x*y = y*x}.
+
+  == SubDomain(Integer,#1 >= 0) add
+      x,y:%
+      sup(x,y) == MAX(x,y)$Lisp
+      shift(x:%, n:Integer):% == ASH(x,n)$Lisp
+      subtractIfCan(x, y) ==
+        c:Integer := (x pretend Integer) - (y pretend Integer)
+        c < 0 => "failed"
+        c pretend %
+
+@
+\section{NNI.lsp BOOTSTRAP}
+{\bf NNI} depends on itself. We need to break this cycle to build
+the algebra. So we keep a cached copy of the translated {\bf NNI}
+category which we can write into the {\bf MID} directory. We compile 
+the lisp code and copy the {\bf NNI.o} file to the {\bf OUT} directory.
+This is eventually forcibly replaced by a recompiled version. 
+
+Note that this code is not included in the generated catdef.spad file.
+
+<<NNI.lsp BOOTSTRAP>>=
+
+(|/VERSIONCHECK| 2) 
+
+(SETQ |$CategoryFrame| 
+  (|put| 
+    #1=(QUOTE |NonNegativeInteger|) 
+   (QUOTE |SuperDomain|) 
+   #2=(QUOTE (|Integer|)) 
+  (|put| 
+    #2# 
+    #3=(QUOTE |SubDomain|) 
+    (CONS 
+      (QUOTE 
+        (|NonNegativeInteger| 
+          COND ((|<| |#1| 0) (QUOTE NIL)) ((QUOTE T) (QUOTE T))))
+      (DELASC #1# (|get| #2# #3# |$CategoryFrame|)))
+   |$CategoryFrame|))) 
+
+(PUT 
+  (QUOTE |NNI;sup;3$;1|) 
+  (QUOTE |SPADreplace|) 
+  (QUOTE MAX)) 
+
+(DEFUN |NNI;sup;3$;1| (|x| |y| |$|) (MAX |x| |y|)) 
+
+(PUT 
+  (QUOTE |NNI;shift;$I$;2|) 
+  (QUOTE |SPADreplace|) 
+  (QUOTE ASH)) 
+
+(DEFUN |NNI;shift;$I$;2| (|x| |n| |$|) (ASH |x| |n|)) 
+
+(DEFUN |NNI;subtractIfCan;2$U;3| (|x| |y| |$|) 
+  (PROG (|c|) 
+    (RETURN 
+      (SEQ 
+        (LETT |c| (|-| |x| |y|) |NNI;subtractIfCan;2$U;3|)
+        (EXIT 
+          (COND 
+            ((|<| |c| 0) (CONS 1 "failed"))
+            ((QUOTE T) (CONS 0 |c|)))))))) 
+
+(DEFUN |NonNegativeInteger| NIL 
+  (PROG NIL 
+    (RETURN 
+      (PROG (#1=#:G96708) 
+        (RETURN 
+          (COND 
+            ((LETT #1# 
+                (HGET |$ConstructorCache| (QUOTE |NonNegativeInteger|))
+                |NonNegativeInteger|)
+              (|CDRwithIncrement| (CDAR #1#)))
+            ((QUOTE T) 
+              (|UNWIND-PROTECT| 
+                (PROG1 
+                  (CDDAR 
+                    (HPUT 
+                       |$ConstructorCache| 
+                       (QUOTE |NonNegativeInteger|) 
+                       (LIST (CONS NIL (CONS 1 (|NonNegativeInteger;|))))))
+                  (LETT #1# T |NonNegativeInteger|))
+                (COND 
+                  ((NOT #1#) 
+                    (HREM 
+                      |$ConstructorCache| 
+                      (QUOTE |NonNegativeInteger|)))))))))))) 
+
+(DEFUN |NonNegativeInteger;| NIL 
+  (PROG (|dv$| |$| |pv$|) 
+    (RETURN 
+      (PROGN 
+        (LETT |dv$| (QUOTE (|NonNegativeInteger|)) . #1=(|NonNegativeInteger|))
+        (LETT |$| (GETREFV 17) . #1#)
+        (QSETREFV |$| 0 |dv$|)
+        (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #1#))
+        (|haddProp| 
+           |$ConstructorCache| 
+           (QUOTE |NonNegativeInteger|) 
+           NIL 
+           (CONS 1 |$|))
+        (|stuffDomainSlots| |$|) |$|)))) 
+
+(MAKEPROP 
+  (QUOTE |NonNegativeInteger|)
+  (QUOTE |infovec|)
+  (LIST 
+    (QUOTE 
+      #(NIL NIL NIL NIL NIL 
+        (|Integer|) 
+        |NNI;sup;3$;1| 
+        |NNI;shift;$I$;2| 
+        (|Union| |$| (QUOTE "failed"))
+        |NNI;subtractIfCan;2$U;3| 
+        (|Record| (|:| |quotient| |$|) (|:| |remainder| |$|))
+        (|PositiveInteger|)
+        (|Boolean|)
+        (|NonNegativeInteger|)
+        (|SingleInteger|)
+        (|String|)
+        (|OutputForm|)))
+    (QUOTE 
+      #(|~=| 0 |zero?| 6 |sup| 11 |subtractIfCan| 17 |shift| 23 |sample| 29 
+        |rem| 33 |recip| 39 |random| 44 |quo| 49 |one?| 55 |min| 60 |max| 66 
+        |latex| 72 |hash| 77 |gcd| 82 |exquo| 88 |divide| 94 |coerce| 100 
+        |^| 105 |Zero| 117 |One| 121 |>=| 125 |>| 131 |=| 137 |<=| 143 
+        |<| 149 |+| 155 |**| 161 |*| 173)) 
+    (QUOTE (((|commutative| "*") . 0)))
+    (CONS 
+      (|makeByteWordVec2| 1 (QUOTE (0 0 0 0 0 0 0 0 0 0 0 0 0)))
+      (CONS 
+        (QUOTE 
+          #(NIL NIL NIL NIL NIL 
+            |Monoid&| 
+            |AbelianMonoid&|
+            |OrderedSet&|
+            |SemiGroup&|
+            |AbelianSemiGroup&|
+            |SetCategory&|
+            |BasicType&|
+            NIL))
+        (CONS 
+          (QUOTE 
+            #((|OrderedAbelianMonoidSup|)
+              (|OrderedCancellationAbelianMonoid|)
+              (|OrderedAbelianMonoid|)
+              (|OrderedAbelianSemiGroup|)
+              (|CancellationAbelianMonoid|)
+              (|Monoid|)
+              (|AbelianMonoid|)
+              (|OrderedSet|)
+              (|SemiGroup|)
+              (|AbelianSemiGroup|)
+              (|SetCategory|)
+              (|BasicType|)
+              (|CoercibleTo| 16)))
+          (|makeByteWordVec2| 16 
+            (QUOTE 
+              (2 0 12 0 0 1 1 0 12 0 1 2 0 0 0 0 6 2 0 8 0 0 9 2 0 0 0 5 7 0 0
+               0 1 2 0 0 0 0 1 1 0 8 0 1 1 0 0 0 1 2 0 0 0 0 1 1 0 12 0 1 2 0
+               0 0 0 1 2 0 0 0 0 1 1 0 15 0 1 1 0 14 0 1 2 0 0 0 0 1 2 0 8 0 0
+               1 2 0 10 0 0 1 1 0 16 0 1 2 0 0 0 11 1 2 0 0 0 13 1 0 0 0 1 0 0
+               0 1 2 0 12 0 0 1 2 0 12 0 0 1 2 0 12 0 0 1 2 0 12 0 0 1 2 0 12
+               0 0 1 2 0 0 0 0 1 2 0 0 0 11 1 2 0 0 0 13 1 2 0 0 0 0 1 2 0 0 
+               11 0 1 2 0 0 13 0 1))))))
+     (QUOTE |lookupComplete|))) 
+
+(MAKEPROP (QUOTE |NonNegativeInteger|) (QUOTE NILADIC) T) 
+
+@
+\section{domain PI PositiveInteger}
+<<domain PI PositiveInteger>>=
+)abbrev domain PI PositiveInteger
+++ Author:
+++ Date Created:
+++ Change History:
+++ Basic Operations:
+++ Related Constructors:
+++ Keywords: positive integer
+++ Description: \spadtype{PositiveInteger} provides functions for
+++   positive integers.
+PositiveInteger: Join(AbelianSemiGroup,OrderedSet,Monoid) with
+            gcd: (%,%) -> %
+              ++ gcd(a,b) computes the greatest common divisor of two
+              ++ positive integers \spad{a} and b.
+            commutative("*")
+              ++ commutative("*") means multiplication is commutative : x*y = y*x
+ == SubDomain(NonNegativeInteger,#1 > 0) add
+     x:%
+     y:%
+
+@
+\section{PI.lsp BOOTSTRAP}
+{\bf PI} depends on itself. We need to break this cycle to build
+the algebra. So we keep a cached copy of the translated {\bf PI}
+category which we can write into the {\bf MID} directory. We compile 
+the lisp code and copy the {\bf PI.o} file to the {\bf OUT} directory.
+This is eventually forcibly replaced by a recompiled version. 
+
+Note that this code is not included in the generated catdef.spad file.
+
+<<PI.lsp BOOTSTRAP>>=
+
+(|/VERSIONCHECK| 2) 
+
+(SETQ |$CategoryFrame| 
+  (|put| 
+    #1=(QUOTE |PositiveInteger|)
+    (QUOTE |SuperDomain|)
+    #2=(QUOTE (|NonNegativeInteger|))
+    (|put| 
+      #2# 
+      #3=(QUOTE |SubDomain|) 
+      (CONS 
+        (QUOTE (|PositiveInteger| |<| 0 |#1|))
+        (DELASC #1# (|get| #2# #3# |$CategoryFrame|)))
+      |$CategoryFrame|))) 
+
+(DEFUN |PositiveInteger| NIL 
+  (PROG NIL 
+    (RETURN 
+      (PROG (#1=#:G96739) 
+        (RETURN 
+          (COND 
+            ((LETT #1# 
+               (HGET |$ConstructorCache| (QUOTE |PositiveInteger|))
+               |PositiveInteger|)
+                 (|CDRwithIncrement| (CDAR #1#)))
+            ((QUOTE T) 
+              (|UNWIND-PROTECT| 
+                (PROG1 
+                  (CDDAR (HPUT |$ConstructorCache| (QUOTE |PositiveInteger|) (LIST (CONS NIL (CONS 1 (|PositiveInteger;|))))))
+                  (LETT #1# T |PositiveInteger|))
+                (COND 
+                  ((NOT #1#) 
+                     (HREM 
+                       |$ConstructorCache| 
+                       (QUOTE |PositiveInteger|)))))))))))) 
+
+(DEFUN |PositiveInteger;| NIL 
+  (PROG (|dv$| |$| |pv$|) 
+    (RETURN 
+      (PROGN 
+        (LETT |dv$| (QUOTE (|PositiveInteger|)) . #1=(|PositiveInteger|))
+        (LETT |$| (GETREFV 12) . #1#)
+        (QSETREFV |$| 0 |dv$|)
+        (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #1#))
+        (|haddProp| 
+           |$ConstructorCache| (QUOTE |PositiveInteger|) NIL (CONS 1 |$|))
+        (|stuffDomainSlots| |$|)
+        |$|)))) 
+
+(MAKEPROP 
+  (QUOTE |PositiveInteger|)
+  (QUOTE |infovec|)
+  (LIST 
+    (QUOTE 
+      #(NIL NIL NIL NIL NIL 
+        (|NonNegativeInteger|)
+        (|PositiveInteger|)
+        (|Boolean|)
+        (|Union| |$| (QUOTE "failed"))
+        (|SingleInteger|)
+        (|String|)
+        (|OutputForm|))) 
+    (QUOTE #(|~=| 0 |sample| 6 |recip| 10 |one?| 15 |min| 20 |max| 26 
+             |latex| 32 |hash| 37 |gcd| 42 |coerce| 48 |^| 53 |One| 65 
+             |>=| 69 |>| 75 |=| 81 |<=| 87 |<| 93 |+| 99 |**| 105 |*| 117))
+    (QUOTE (((|commutative| "*") . 0)))
+    (CONS 
+      (|makeByteWordVec2| 1 (QUOTE (0 0 0 0 0 0 0)))
+      (CONS 
+        (QUOTE #(|Monoid&| |AbelianSemiGroup&| |SemiGroup&| |OrderedSet&| 
+                 |SetCategory&| |BasicType&| NIL))
+        (CONS 
+          (QUOTE #(
+            (|Monoid|)
+            (|AbelianSemiGroup|)
+            (|SemiGroup|)
+            (|OrderedSet|)
+            (|SetCategory|)
+            (|BasicType|)
+            (|CoercibleTo| 11)))
+          (|makeByteWordVec2| 11 
+           (QUOTE (2 0 7 0 0 1 0 0 0 1 1 0 8 0 1 1 0 7 0 1 2 0 0 0 0 1 2 0 0 0
+                   0 1 1 0 10 0 1 1 0 9 0 1 2 0 0 0 0 1 1 0 11 0 1 2 0 0 0 6 1
+                   2 0 0 0 5 1 0 0 0 1 2 0 7 0 0 1 2 0 7 0 0 1 2 0 7 0 0 1 2 0
+                   7 0 0 1 2 0 7 0 0 1 2 0 0 0 0 1 2 0 0 0 6 1 2 0 0 0 5 1 2 0
+                   0 0 0 1 2 0 0 6 0 1))))))
+     (QUOTE |lookupComplete|))) 
+
+(MAKEPROP (QUOTE |PositiveInteger|) (QUOTE NILADIC) T) 
+
+@
+\section{domain ROMAN RomanNumeral}
+<<domain ROMAN RomanNumeral>>=
+)abbrev domain ROMAN RomanNumeral
+++ Author:
+++ Date Created:
+++ Change History:
+++ Basic Operations:
+++   convert, roman
+++ Related Constructors:
+++ Keywords: roman numerals
+++ Description:  \spadtype{RomanNumeral} provides functions for converting
+++   integers to roman numerals.
+RomanNumeral(): IntegerNumberSystem with
+    canonical
+      ++ mathematical equality is data structure equality.
+    canonicalsClosed
+      ++ two positives multiply to give positive.
+    noetherian
+      ++ ascending chain condition on ideals.
+    convert: Symbol  -> %
+      ++ convert(n) creates a roman numeral for symbol n.
+    roman  : Symbol  -> %
+      ++ roman(n) creates a roman numeral for symbol n.
+    roman  : Integer -> %
+      ++ roman(n) creates a roman numeral for n.
+
+  == Integer add
+        import NumberFormats()
+
+        roman(n:Integer) == n::%
+        roman(sy:Symbol) == convert sy
+        convert(sy:Symbol):%    == ScanRoman(string sy)::%
+
+        coerce(r:%):OutputForm ==
+            n := convert(r)@Integer
+            -- okay, we stretch it
+            zero? n => n::OutputForm
+            negative? n => - ((-r)::OutputForm)
+            FormatRoman(n::PositiveInteger)::Symbol::OutputForm
+
+@
+\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 INTSLPE IntegerSolveLinearPolynomialEquation>>
+<<domain INT Integer>>
+<<domain NNI NonNegativeInteger>>
+<<domain PI PositiveInteger>>
+<<domain ROMAN RomanNumeral>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}