diff options
author | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
---|---|---|
committer | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
commit | ab8cc85adde879fb963c94d15675783f2cf4b183 (patch) | |
tree | c202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/integer.spad.pamphlet | |
download | open-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz |
Initial population.
Diffstat (limited to 'src/algebra/integer.spad.pamphlet')
-rw-r--r-- | src/algebra/integer.spad.pamphlet | 865 |
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} |