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