path: root/src/algebra/integer.spad.pamphlet

\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| (|getShellEntry| $ 8))
               (SPADCALL |dev| "arith1" "unary_minus"
                   (|getShellEntry| $ 10))
               (SPADCALL |dev| (- |x|) (|getShellEntry| $ 12))
               (EXIT (SPADCALL |dev| (|getShellEntry| $ 13)))))
         ('T (SPADCALL |dev| |x| (|getShellEntry| $ 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 (|getShellEntry| $ 15))
                     (|getShellEntry| $ 16))
                 |INT;OMwrite;$S;2|)
           (SPADCALL |dev| (|getShellEntry| $ 17))
           (|INT;writeOMInt| |dev| |x| $)
           (SPADCALL |dev| (|getShellEntry| $ 18))
           (SPADCALL |dev| (|getShellEntry| $ 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 (|getShellEntry| $ 15))
                     (|getShellEntry| $ 16))
                 |INT;OMwrite;$BS;3|)
           (COND (|wholeObj| (SPADCALL |dev| (|getShellEntry| $ 17))))
           (|INT;writeOMInt| |dev| |x| $)
           (COND (|wholeObj| (SPADCALL |dev| (|getShellEntry| $ 18))))
           (SPADCALL |dev| (|getShellEntry| $ 19))
           (LETT |s| (OM-STRINGPTRTOSTRING |sp|) |INT;OMwrite;$BS;3|)
           (EXIT |s|))))) 

(DEFUN |INT;OMwrite;Omd$V;4| (|dev| |x| $)
  (SEQ (SPADCALL |dev| (|getShellEntry| $ 17))
       (|INT;writeOMInt| |dev| |x| $)
       (EXIT (SPADCALL |dev| (|getShellEntry| $ 18))))) 

(DEFUN |INT;OMwrite;Omd$BV;5| (|dev| |x| |wholeObj| $)
  (SEQ (COND (|wholeObj| (SPADCALL |dev| (|getShellEntry| $ 17))))
       (|INT;writeOMInt| |dev| |x| $)
       (EXIT (COND
               (|wholeObj| (SPADCALL |dev| (|getShellEntry| $ 18))))))) 

(PUT '|INT;zero?;$B;6| '|SPADreplace| 'ZEROP) 

(DEFUN |INT;zero?;$B;6| (|x| $) (ZEROP |x|)) 

(PUT '|INT;one?;$B;7| '|SPADreplace| '(XLAM (|x|) (EQL |x| 1))) 

(DEFUN |INT;one?;$B;7| (|x| $) (EQL |x| 1)) 

(PUT '|INT;Zero;$;8| '|SPADreplace| '(XLAM NIL 0)) 

(DEFUN |INT;Zero;$;8| ($) 0) 

(PUT '|INT;One;$;9| '|SPADreplace| '(XLAM NIL 1)) 

(DEFUN |INT;One;$;9| ($) 1) 

(PUT '|INT;base;$;10| '|SPADreplace| '(XLAM NIL 2)) 

(DEFUN |INT;base;$;10| ($) 2) 

(PUT '|INT;copy;2$;11| '|SPADreplace| '(XLAM (|x|) |x|)) 

(DEFUN |INT;copy;2$;11| (|x| $) |x|) 

(PUT '|INT;inc;2$;12| '|SPADreplace| '(XLAM (|x|) (+ |x| 1))) 

(DEFUN |INT;inc;2$;12| (|x| $) (+ |x| 1)) 

(PUT '|INT;dec;2$;13| '|SPADreplace| '(XLAM (|x|) (- |x| 1))) 

(DEFUN |INT;dec;2$;13| (|x| $) (- |x| 1)) 

(PUT '|INT;hash;2$;14| '|SPADreplace| 'SXHASH) 

(DEFUN |INT;hash;2$;14| (|x| $) (SXHASH |x|)) 

(PUT '|INT;negative?;$B;15| '|SPADreplace| 'MINUSP) 

(DEFUN |INT;negative?;$B;15| (|x| $) (MINUSP |x|)) 

(DEFUN |INT;coerce;$Of;16| (|x| $)
  (SPADCALL |x| (|getShellEntry| $ 36))) 

(PUT '|INT;coerce;I$;17| '|SPADreplace| '(XLAM (|m|) |m|)) 

(DEFUN |INT;coerce;I$;17| (|m| $) |m|) 

(PUT '|INT;convert;$I;18| '|SPADreplace| '(XLAM (|x|) |x|)) 

(DEFUN |INT;convert;$I;18| (|x| $) |x|) 

(PUT '|INT;length;2$;19| '|SPADreplace| 'INTEGER-LENGTH) 

(DEFUN |INT;length;2$;19| (|a| $) (INTEGER-LENGTH |a|)) 

(DEFUN |INT;addmod;4$;20| (|a| |b| |p| $)
  (PROG (|c| #0=#:G1427)
    (RETURN
      (SEQ (EXIT (SEQ (SEQ (LETT |c| (+ |a| |b|) |INT;addmod;4$;20|)
                           (EXIT (COND
                                   ((NULL (< |c| |p|))
                                    (PROGN
                                      (LETT #0# (- |c| |p|)
                                       |INT;addmod;4$;20|)
                                      (GO #0#))))))
                      (EXIT |c|)))
           #0# (EXIT #0#))))) 

(DEFUN |INT;submod;4$;21| (|a| |b| |p| $)
  (PROG (|c|)
    (RETURN
      (SEQ (LETT |c| (- |a| |b|) |INT;submod;4$;21|)
           (EXIT (COND ((< |c| 0) (+ |c| |p|)) ('T |c|))))))) 

(DEFUN |INT;mulmod;4$;22| (|a| |b| |p| $)
  (REMAINDER2 (* |a| |b|) |p|)) 

(DEFUN |INT;convert;$F;23| (|x| $)
  (SPADCALL |x| (|getShellEntry| $ 45))) 

(PUT '|INT;convert;$Df;24| '|SPADreplace|
     '(XLAM (|x|) (FLOAT |x| MOST-POSITIVE-LONG-FLOAT))) 

(DEFUN |INT;convert;$Df;24| (|x| $)
  (FLOAT |x| MOST-POSITIVE-LONG-FLOAT)) 

(DEFUN |INT;convert;$If;25| (|x| $)
  (SPADCALL |x| (|getShellEntry| $ 50))) 

(PUT '|INT;convert;$S;26| '|SPADreplace| 'STRINGIMAGE) 

(DEFUN |INT;convert;$S;26| (|x| $) (STRINGIMAGE |x|)) 

(DEFUN |INT;latex;$S;27| (|x| $)
  (PROG (|s|)
    (RETURN
      (SEQ (LETT |s| (STRINGIMAGE |x|) |INT;latex;$S;27|)
           (COND ((< -1 |x|) (COND ((< |x| 10) (EXIT |s|)))))
           (EXIT (STRCONC "{" (STRCONC |s| "}"))))))) 

(DEFUN |INT;positiveRemainder;3$;28| (|a| |b| $)
  (PROG (|r|)
    (RETURN
      (COND
        ((MINUSP (LETT |r| (REMAINDER2 |a| |b|)
                       |INT;positiveRemainder;3$;28|))
         (COND ((MINUSP |b|) (- |r| |b|)) ('T (+ |r| |b|))))
        ('T |r|))))) 

(PUT '|INT;reducedSystem;MM;29| '|SPADreplace| '(XLAM (|m|) |m|)) 

(DEFUN |INT;reducedSystem;MM;29| (|m| $) |m|) 

(DEFUN |INT;reducedSystem;MVR;30| (|m| |v| $) (CONS |m| '|vec|)) 

(PUT '|INT;abs;2$;31| '|SPADreplace| 'ABS) 

(DEFUN |INT;abs;2$;31| (|x| $) (ABS |x|)) 

(PUT '|INT;random;$;32| '|SPADreplace| '|random|) 

(DEFUN |INT;random;$;32| ($) (|random|)) 

(PUT '|INT;random;2$;33| '|SPADreplace| 'RANDOM) 

(DEFUN |INT;random;2$;33| (|x| $) (RANDOM |x|)) 

(PUT '|INT;=;2$B;34| '|SPADreplace| 'EQL) 

(DEFUN |INT;=;2$B;34| (|x| |y| $) (EQL |x| |y|)) 

(PUT '|INT;<;2$B;35| '|SPADreplace| '<) 

(DEFUN |INT;<;2$B;35| (|x| |y| $) (< |x| |y|)) 

(PUT '|INT;-;2$;36| '|SPADreplace| '-) 

(DEFUN |INT;-;2$;36| (|x| $) (- |x|)) 

(PUT '|INT;+;3$;37| '|SPADreplace| '+) 

(DEFUN |INT;+;3$;37| (|x| |y| $) (+ |x| |y|)) 

(PUT '|INT;-;3$;38| '|SPADreplace| '-) 

(DEFUN |INT;-;3$;38| (|x| |y| $) (- |x| |y|)) 

(PUT '|INT;*;3$;39| '|SPADreplace| '*) 

(DEFUN |INT;*;3$;39| (|x| |y| $) (* |x| |y|)) 

(PUT '|INT;*;I2$;40| '|SPADreplace| '*) 

(DEFUN |INT;*;I2$;40| (|m| |y| $) (* |m| |y|)) 

(PUT '|INT;**;$Nni$;41| '|SPADreplace| 'EXPT) 

(DEFUN |INT;**;$Nni$;41| (|x| |n| $) (EXPT |x| |n|)) 

(PUT '|INT;odd?;$B;42| '|SPADreplace| 'ODDP) 

(DEFUN |INT;odd?;$B;42| (|x| $) (ODDP |x|)) 

(PUT '|INT;max;3$;43| '|SPADreplace| 'MAX) 

(DEFUN |INT;max;3$;43| (|x| |y| $) (MAX |x| |y|)) 

(PUT '|INT;min;3$;44| '|SPADreplace| 'MIN) 

(DEFUN |INT;min;3$;44| (|x| |y| $) (MIN |x| |y|)) 

(PUT '|INT;divide;2$R;45| '|SPADreplace| 'DIVIDE2) 

(DEFUN |INT;divide;2$R;45| (|x| |y| $) (DIVIDE2 |x| |y|)) 

(PUT '|INT;quo;3$;46| '|SPADreplace| 'QUOTIENT2) 

(DEFUN |INT;quo;3$;46| (|x| |y| $) (QUOTIENT2 |x| |y|)) 

(PUT '|INT;rem;3$;47| '|SPADreplace| 'REMAINDER2) 

(DEFUN |INT;rem;3$;47| (|x| |y| $) (REMAINDER2 |x| |y|)) 

(PUT '|INT;shift;3$;48| '|SPADreplace| 'ASH) 

(DEFUN |INT;shift;3$;48| (|x| |y| $) (ASH |x| |y|)) 

(DEFUN |INT;exquo;2$U;49| (|x| |y| $)
  (COND
    ((OR (ZEROP |y|) (NULL (ZEROP (REMAINDER2 |x| |y|))))
     (CONS 1 "failed"))
    ('T (CONS 0 (QUOTIENT2 |x| |y|))))) 

(DEFUN |INT;recip;$U;50| (|x| $)
  (COND
    ((OR (EQL |x| 1) (EQL |x| -1)) (CONS 0 |x|))
    ('T (CONS 1 "failed")))) 

(PUT '|INT;gcd;3$;51| '|SPADreplace| 'GCD) 

(DEFUN |INT;gcd;3$;51| (|x| |y| $) (GCD |x| |y|)) 

(DEFUN |INT;unitNormal;$R;52| (|x| $)
  (COND ((< |x| 0) (VECTOR -1 (- |x|) -1)) ('T (VECTOR 1 |x| 1)))) 

(PUT '|INT;unitCanonical;2$;53| '|SPADreplace| 'ABS) 

(DEFUN |INT;unitCanonical;2$;53| (|x| $) (ABS |x|)) 

(DEFUN |INT;solveLinearPolynomialEquation| (|lp| |p| $)
  (SPADCALL |lp| |p| (|getShellEntry| $ 93))) 

(DEFUN |INT;squareFreePolynomial| (|p| $)
  (SPADCALL |p| (|getShellEntry| $ 97))) 

(DEFUN |INT;factorPolynomial| (|p| $)
  (PROG (|pp| #0=#:G1498)
    (RETURN
      (SEQ (LETT |pp| (SPADCALL |p| (|getShellEntry| $ 98))
                 |INT;factorPolynomial|)
           (EXIT (COND
                   ((EQL (SPADCALL |pp| (|getShellEntry| $ 99))
                         (SPADCALL |p| (|getShellEntry| $ 99)))
                    (SPADCALL |p| (|getShellEntry| $ 101)))
                   ('T
                    (SPADCALL (SPADCALL |pp| (|getShellEntry| $ 101))
                        (SPADCALL (CONS #'|INT;factorPolynomial!0| $)
                            (SPADCALL
                                (PROG2 (LETT #0#
                                        (SPADCALL
                                         (SPADCALL |p|
                                          (|getShellEntry| $ 99))
                                         (SPADCALL |pp|
                                          (|getShellEntry| $ 99))
                                         (|getShellEntry| $ 83))
                                        |INT;factorPolynomial|)
                                       (QCDR #0#)
                                  (|check-union| (QEQCAR #0# 0) $ #0#))
                                (|getShellEntry| $ 104))
                            (|getShellEntry| $ 108))
                        (|getShellEntry| $ 110))))))))) 

(DEFUN |INT;factorPolynomial!0| (|#1| $)
  (SPADCALL |#1| (|getShellEntry| $ 102))) 

(DEFUN |INT;factorSquareFreePolynomial| (|p| $)
  (SPADCALL |p| (|getShellEntry| $ 111))) 

(DEFUN |INT;gcdPolynomial;3Sup;58| (|p| |q| $)
  (COND
    ((SPADCALL |p| (|getShellEntry| $ 112))
     (SPADCALL |q| (|getShellEntry| $ 113)))
    ((SPADCALL |q| (|getShellEntry| $ 112))
     (SPADCALL |p| (|getShellEntry| $ 113)))
    ('T (SPADCALL (LIST |p| |q|) (|getShellEntry| $ 116))))) 

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

(DEFUN |Integer;| ()
  (PROG (|dv$| $ |pv$|)
    (RETURN
      (PROGN
        (LETT |dv$| '(|Integer|) . #0=(|Integer|))
        (LETT $ (|newShell| 132) . #0#)
        (|setShellEntry| $ 0 |dv$|)
        (|setShellEntry| $ 3
            (LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#))
        (|haddProp| |$ConstructorCache| '|Integer| NIL (CONS 1 $))
        (|stuffDomainSlots| $)
        (|setShellEntry| $ 71
            (|setShellEntry| $ 70
                (CONS (|dispatchFunction| |INT;*;I2$;40|) $)))
        $)))) 

(MAKEPROP '|Integer| '|infovec|
    (LIST '#(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| |INT;one?;$B;7|
             (CONS IDENTITY
                   (FUNCALL (|dispatchFunction| |INT;Zero;$;8|) $))
             (CONS IDENTITY
                   (FUNCALL (|dispatchFunction| |INT;One;$;9|) $))
             |INT;base;$;10| |INT;copy;2$;11| |INT;inc;2$;12|
             |INT;dec;2$;13| |INT;hash;2$;14| |INT;negative?;$B;15|
             (|OutputForm|) (48 . |outputForm|) |INT;coerce;$Of;16|
             |INT;coerce;I$;17| |INT;convert;$I;18| |INT;length;2$;19|
             |INT;addmod;4$;20| |INT;submod;4$;21| |INT;mulmod;4$;22|
             (|Float|) (53 . |coerce|) |INT;convert;$F;23|
             (|DoubleFloat|) |INT;convert;$Df;24| (|InputForm|)
             (58 . |convert|) |INT;convert;$If;25| |INT;convert;$S;26|
             |INT;latex;$S;27| |INT;positiveRemainder;3$;28|
             (|Matrix| 11) (|Matrix| $) |INT;reducedSystem;MM;29|
             (|Vector| 11) (|Record| (|:| |mat| 55) (|:| |vec| 58))
             (|Vector| $) |INT;reducedSystem;MVR;30| |INT;abs;2$;31|
             |INT;random;$;32| |INT;random;2$;33| |INT;=;2$B;34|
             |INT;<;2$B;35| |INT;-;2$;36| |INT;+;3$;37| |INT;-;3$;38|
             NIL NIL (|NonNegativeInteger|) |INT;**;$Nni$;41|
             |INT;odd?;$B;42| |INT;max;3$;43| |INT;min;3$;44|
             (|Record| (|:| |quotient| $) (|:| |remainder| $))
             |INT;divide;2$R;45| |INT;quo;3$;46| |INT;rem;3$;47|
             |INT;shift;3$;48| (|Union| $ '"failed") |INT;exquo;2$U;49|
             |INT;recip;$U;50| |INT;gcd;3$;51|
             (|Record| (|:| |unit| $) (|:| |canonical| $)
                 (|:| |associate| $))
             |INT;unitNormal;$R;52| |INT;unitCanonical;2$;53|
             (|SparseUnivariatePolynomial| 11) (|List| 89)
             (|Union| 90 '"failed")
             (|IntegerSolveLinearPolynomialEquation|)
             (63 . |solveLinearPolynomialEquation|)
             (|SparseUnivariatePolynomial| $$) (|Factored| 94)
             (|UnivariatePolynomialSquareFree| $$ 94)
             (69 . |squareFree|) (74 . |primitivePart|)
             (79 . |leadingCoefficient|) (|GaloisGroupFactorizer| 94)
             (84 . |factor|) (89 . |coerce|) (|Factored| $)
             (94 . |factor|) (|Mapping| 94 $$) (|Factored| $$)
             (|FactoredFunctions2| $$ 94) (99 . |map|)
             (|FactoredFunctionUtilities| 94) (105 . |mergeFactors|)
             (111 . |factorSquareFree|) (116 . |zero?|)
             (121 . |unitCanonical|) (|List| 94) (|HeuGcd| 94)
             (126 . |gcd|) (|SparseUnivariatePolynomial| $)
             |INT;gcdPolynomial;3Sup;58| (|Fraction| 11)
             (|Union| 119 '"failed") (|PatternMatchResult| 11 $)
             (|Pattern| 11) (|Union| 11 '"failed") (|List| $)
             (|Union| 124 '"failed")
             (|Record| (|:| |coef| 124) (|:| |generator| $))
             (|Record| (|:| |coef1| $) (|:| |coef2| $))
             (|Union| 127 '"failed")
             (|Record| (|:| |coef1| $) (|:| |coef2| $)
                 (|:| |generator| $))
             (|PositiveInteger|) (|SingleInteger|))
          '#(~= 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)
          '((|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
                    '(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 '#(|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 '#((|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| 44)
                               (|ConvertibleTo| 47)
                               (|CombinatorialFunctionCategory|)
                               (|ConvertibleTo| 122)
                               (|ConvertibleTo| 49)
                               (|RetractableTo| 11)
                               (|ConvertibleTo| 11) (|BasicType|)
                               (|CoercibleTo| 35))
                            (|makeByteWordVec2| 131
                                '(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 35
                                  0 11 36 1 44 0 11 45 1 49 0 11 50 2
                                  92 91 90 89 93 1 96 95 94 97 1 94 0 0
                                  98 1 94 2 0 99 1 100 95 94 101 1 94 0
                                  2 102 1 0 103 0 104 2 107 95 105 106
                                  108 2 109 95 95 95 110 1 100 95 94
                                  111 1 94 21 0 112 1 94 0 0 113 1 115
                                  94 114 116 2 0 21 0 0 1 1 0 21 0 25 1
                                  0 86 0 87 1 0 0 0 88 1 0 21 0 1 2 0 0
                                  0 0 1 2 0 82 0 0 1 3 0 0 0 0 0 42 1 0
                                  0 0 1 1 0 103 0 1 2 0 21 0 0 1 1 0 11
                                  0 1 2 0 0 0 0 81 0 0 0 1 1 0 123 0 1
                                  1 0 11 0 1 2 0 0 0 0 80 2 0 59 56 60
                                  61 1 0 55 56 57 1 0 82 0 84 1 0 120 0
                                  1 1 0 21 0 1 1 0 119 0 1 1 0 0 0 64 0
                                  0 0 63 2 0 0 0 0 79 1 0 126 124 1 1 0
                                  21 0 1 3 0 0 0 0 0 1 2 0 0 0 0 54 1 0
                                  21 0 1 2 0 0 0 0 1 3 0 121 0 122 121
                                  1 1 0 21 0 26 1 0 21 0 74 1 0 82 0 1
                                  1 0 21 0 34 2 0 125 124 0 1 3 0 0 0 0
                                  0 43 2 0 0 0 0 76 2 0 0 0 0 75 1 0 0
                                  0 1 1 0 0 0 40 1 0 0 124 1 2 0 0 0 0
                                  1 1 0 9 0 53 2 0 0 0 0 1 0 0 0 1 1 0
                                  0 0 31 1 0 0 0 33 1 0 131 0 1 2 0 117
                                  117 117 118 2 0 0 0 0 85 1 0 0 124 1
                                  1 0 0 0 1 1 0 103 0 104 3 0 128 0 0 0
                                  1 2 0 129 0 0 1 2 0 82 0 0 83 2 0 125
                                  124 0 1 1 0 21 0 1 1 0 72 0 1 2 0 77
                                  0 0 78 1 0 0 0 1 2 0 0 0 72 1 1 0 0 0
                                  32 1 0 0 0 30 1 0 9 0 52 1 0 47 0 48
                                  1 0 44 0 46 1 0 49 0 51 1 0 122 0 1 1
                                  0 11 0 39 1 0 0 11 38 1 0 0 11 38 1 0
                                  0 0 1 1 0 35 0 37 0 0 72 1 2 0 21 0 0
                                  1 2 0 0 0 0 1 0 0 0 29 2 0 21 0 0 1 3
                                  0 0 0 0 0 41 1 0 0 0 62 2 0 0 0 72 1
                                  2 0 0 0 130 1 0 0 0 27 0 0 0 28 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 72 1 2 0
                                  21 0 0 1 2 0 21 0 0 1 2 0 21 0 0 65 2
                                  0 21 0 0 1 2 0 21 0 0 66 2 0 0 0 0 69
                                  1 0 0 0 67 2 0 0 0 0 68 2 0 0 0 72 73
                                  2 0 0 0 130 1 2 0 0 0 0 70 2 0 0 11 0
                                  71 2 0 0 72 0 1 2 0 0 130 0 1)))))
          '|lookupComplete|)) 

(MAKEPROP '|Integer| '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(OrderedAbelianSemiGroup,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| #0='|PositiveInteger| '|SuperDomain|
             #1='(|NonNegativeInteger|)
             (|put| #1# '|SubDomain|
                    (CONS '(|PositiveInteger| < 0 |#1|)
                          (DELASC #0#
                                  (|get| #1# '|SubDomain|
                                         |$CategoryFrame|)))
                    |$CategoryFrame|))) 

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

(DEFUN |PositiveInteger;| ()
  (PROG (|dv$| $ |pv$|)
    (RETURN
      (PROGN
        (LETT |dv$| '(|PositiveInteger|) . #0=(|PositiveInteger|))
        (LETT $ (|newShell| 12) . #0#)
        (|setShellEntry| $ 0 |dv$|)
        (|setShellEntry| $ 3
            (LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#))
        (|haddProp| |$ConstructorCache| '|PositiveInteger| NIL
            (CONS 1 $))
        (|stuffDomainSlots| $)
        $)))) 

(MAKEPROP '|PositiveInteger| '|infovec|
    (LIST '#(NIL NIL NIL NIL NIL (|NonNegativeInteger|)
             (|PositiveInteger|) (|Boolean|) (|Union| $ '"failed")
             (|SingleInteger|) (|String|) (|OutputForm|))
          '#(~= 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)
          '(((|commutative| "*") . 0))
          (CONS (|makeByteWordVec2| 1 '(0 0 0 0 0 0 0 0))
                (CONS '#(NIL |Monoid&| |OrderedSet&| |SemiGroup&|
                         |AbelianSemiGroup&| |SetCategory&|
                         |BasicType&| NIL)
                      (CONS '#((|OrderedAbelianSemiGroup|) (|Monoid|)
                               (|OrderedSet|) (|SemiGroup|)
                               (|AbelianSemiGroup|) (|SetCategory|)
                               (|BasicType|) (|CoercibleTo| 11))
                            (|makeByteWordVec2| 11
                                '(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)))))
          '|lookupComplete|)) 

(MAKEPROP '|PositiveInteger| '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}