\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra si.spad}
\author{Stephen M. Watt, Michael Monagan, James Davenport, Barry Trager}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{category INS IntegerNumberSystem}
<<category INS IntegerNumberSystem>>=
)abbrev category INS IntegerNumberSystem
++ Author: Stephen M. Watt
++ Date Created:
++ January 1988
++ Change History:
++ Basic Operations:
++ addmod, base, bit?, copy, dec, even?, hash, inc, invmod, length, mask,
++ positiveRemainder, symmetricRemainder, multiplicativeValuation, mulmod,
++ odd?, powmod, random, rational, rational?, rationalIfCan, shift, submod
++ Description: An \spad{IntegerNumberSystem} is a model for the integers.
IntegerNumberSystem(): Category ==
Join(UniqueFactorizationDomain, EuclideanDomain, OrderedIntegralDomain,
DifferentialRing, ConvertibleTo Integer, RetractableTo Integer,
LinearlyExplicitRingOver Integer, ConvertibleTo InputForm,
ConvertibleTo Pattern Integer, PatternMatchable Integer,
CombinatorialFunctionCategory, RealConstant,
CharacteristicZero, StepThrough) with
odd? : % -> Boolean
++ odd?(n) returns true if and only if n is odd.
even? : % -> Boolean
++ even?(n) returns true if and only if n is even.
multiplicativeValuation
++ euclideanSize(a*b) returns \spad{euclideanSize(a)*euclideanSize(b)}.
base : () -> %
++ base() returns the base for the operations of \spad{IntegerNumberSystem}.
length : % -> %
++ length(a) length of \spad{a} in digits.
shift : (%, %) -> %
++ shift(a,i) shift \spad{a} by i digits.
bit? : (%, %) -> Boolean
++ bit?(n,i) returns true if and only if i-th bit of n is a 1.
positiveRemainder : (%, %) -> %
++ positiveRemainder(a,b) (where \spad{b > 1}) yields r
++ where \spad{0 <= r < b} and \spad{r == a rem b}.
symmetricRemainder : (%, %) -> %
++ symmetricRemainder(a,b) (where \spad{b > 1}) yields r
++ where \spad{ -b/2 <= r < b/2 }.
rational?: % -> Boolean
++ rational?(n) tests if n is a rational number
++ (see \spadtype{Fraction Integer}).
rational : % -> Fraction Integer
++ rational(n) creates a rational number (see \spadtype{Fraction Integer})..
rationalIfCan: % -> Union(Fraction Integer, "failed")
++ rationalIfCan(n) creates a rational number, or returns "failed" if this is not possible.
random : () -> %
++ random() creates a random element.
random : % -> %
++ random(a) creates a random element from 0 to \spad{n-1}.
hash : % -> %
++ hash(n) returns the hash code of n.
copy : % -> %
++ copy(n) gives a copy of n.
inc : % -> %
++ inc(x) returns \spad{x + 1}.
dec : % -> %
++ dec(x) returns \spad{x - 1}.
mask : % -> %
++ mask(n) returns \spad{2**n-1} (an n bit mask).
addmod : (%,%,%) -> %
++ addmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a+b mod p}.
submod : (%,%,%) -> %
++ submod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a-b mod p}.
mulmod : (%,%,%) -> %
++ mulmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a*b mod p}.
powmod : (%,%,%) -> %
++ powmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a**b mod p}.
invmod : (%,%) -> %
++ invmod(a,b), \spad{0<=a<b>1}, \spad{(a,b)=1} means \spad{1/a mod b}.
canonicalUnitNormal
-- commutative("*") -- follows from the above
add
characteristic() == 0
differentiate x == 0
even? x == not odd? x
positive? x == x > 0
copy x == x
bit?(x, i) == odd? shift(x, -i)
mask n == dec shift(1, n)
rational? x == true
euclideanSize(x) ==
x=0 => error "euclideanSize called on zero"
x<0 => (-convert(x)@Integer)::NonNegativeInteger
convert(x)@Integer::NonNegativeInteger
convert(x:%):Float == (convert(x)@Integer)::Float
convert(x:%):DoubleFloat == (convert(x)@Integer)::DoubleFloat
convert(x:%):InputForm == convert(convert(x)@Integer)
retract(x:%):Integer == convert(x)@Integer
convert(x:%):Pattern(Integer)== convert(x)@Integer ::Pattern(Integer)
factor x == factor(x)$IntegerFactorizationPackage(%)
squareFree x == squareFree(x)$IntegerFactorizationPackage(%)
prime? x == prime?(x)$IntegerPrimesPackage(%)
factorial x == factorial(x)$IntegerCombinatoricFunctions(%)
binomial(n, m) == binomial(n, m)$IntegerCombinatoricFunctions(%)
permutation(n, m) == permutation(n,m)$IntegerCombinatoricFunctions(%)
retractIfCan(x:%):Union(Integer, "failed") == convert(x)@Integer
init() == 0
-- iterates in order 0,1,-1,2,-2,3,-3,...
nextItem(n) ==
zero? n => 1
n>0 => -n
1-n
patternMatch(x, p, l) ==
patternMatch(x, p, l)$PatternMatchIntegerNumberSystem(%)
rational(x:%):Fraction(Integer) ==
(convert(x)@Integer)::Fraction(Integer)
rationalIfCan(x:%):Union(Fraction Integer, "failed") ==
(convert(x)@Integer)::Fraction(Integer)
symmetricRemainder(x, n) ==
r := x rem n
r = 0 => r
if n < 0 then n:=-n
r > 0 =>
2 * r > n => r - n
r
2*r + n <= 0 => r + n
r
invmod(a, b) ==
if negative? a then a := positiveRemainder(a, b)
c := a; c1:% := 1
d := b; d1:% := 0
while not zero? d repeat
q := c quo d
r := c-q*d
r1 := c1-q*d1
c := d; c1 := d1
d := r; d1 := r1
-- not one? c => error "inverse does not exist"
not (c = 1) => error "inverse does not exist"
negative? c1 => c1 + b
c1
powmod(x, n, p) ==
if negative? x then x := positiveRemainder(x, p)
zero? x => 0
zero? n => 1
y:% := 1
z := x
repeat
if odd? n then y := mulmod(y, z, p)
zero?(n := shift(n, -1)) => return y
z := mulmod(z, z, p)
@
\section{INS.lsp BOOTSTRAP}
{\bf INS} depends on itself. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf INS}
category which we can write into the {\bf MID} directory. We compile
the lisp code and copy the {\bf INS.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version.
<<INS.lsp BOOTSTRAP>>=
(/VERSIONCHECK 2)
(DEFPARAMETER |IntegerNumberSystem;AL| 'NIL)
(DEFUN |IntegerNumberSystem| ()
(LET (#:G1403)
(COND
(|IntegerNumberSystem;AL|)
(T (SETQ |IntegerNumberSystem;AL| (|IntegerNumberSystem;|))))))
(DEFUN |IntegerNumberSystem;| ()
(PROG (#0=#:G1401)
(RETURN
(PROG1 (LETT #0#
(|sublisV|
(PAIR '(#1=#:G1395 #2=#:G1396 #3=#:G1397
#4=#:G1398 #5=#:G1399 #6=#:G1400)
(LIST '(|Integer|) '(|Integer|)
'(|Integer|) '(|InputForm|)
'(|Pattern| (|Integer|))
'(|Integer|)))
(|Join| (|UniqueFactorizationDomain|)
(|EuclideanDomain|)
(|OrderedIntegralDomain|)
(|DifferentialRing|)
(|ConvertibleTo| '#1#)
(|RetractableTo| '#2#)
(|LinearlyExplicitRingOver| '#3#)
(|ConvertibleTo| '#4#)
(|ConvertibleTo| '#5#)
(|PatternMatchable| '#6#)
(|CombinatorialFunctionCategory|)
(|RealConstant|) (|CharacteristicZero|)
(|StepThrough|)
(|mkCategory| '|domain|
'(((|odd?| ((|Boolean|) $)) T)
((|even?| ((|Boolean|) $)) T)
((|base| ($)) T)
((|length| ($ $)) T)
((|shift| ($ $ $)) T)
((|bit?| ((|Boolean|) $ $)) T)
((|positiveRemainder| ($ $ $)) T)
((|symmetricRemainder| ($ $ $)) T)
((|rational?| ((|Boolean|) $)) T)
((|rational|
((|Fraction| (|Integer|)) $))
T)
((|rationalIfCan|
((|Union|
(|Fraction| (|Integer|))
"failed")
$))
T)
((|random| ($)) T)
((|random| ($ $)) T)
((|hash| ($ $)) T)
((|copy| ($ $)) T)
((|inc| ($ $)) T)
((|dec| ($ $)) T)
((|mask| ($ $)) T)
((|addmod| ($ $ $ $)) T)
((|submod| ($ $ $ $)) T)
((|mulmod| ($ $ $ $)) T)
((|powmod| ($ $ $ $)) T)
((|invmod| ($ $ $)) T))
'((|multiplicativeValuation| T)
(|canonicalUnitNormal| T))
'((|Fraction| (|Integer|))
(|Boolean|))
NIL)))
|IntegerNumberSystem|)
(SETELT #0# 0 '(|IntegerNumberSystem|))))))
(MAKEPROP '|IntegerNumberSystem| 'NILADIC T)
@
\section{INS-.lsp BOOTSTRAP}
{\bf INS-} depends on {\bf INS}. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf INS-}
category which we can write into the {\bf MID} directory. We compile
the lisp code and copy the {\bf INS-.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version.
<<INS-.lsp BOOTSTRAP>>=
(/VERSIONCHECK 2)
(PUT '|INS-;characteristic;Nni;1| '|SPADreplace| '(XLAM NIL 0))
(DEFUN |INS-;characteristic;Nni;1| ($) 0)
(DEFUN |INS-;differentiate;2S;2| (|x| $) (|spadConstant| $ 9))
(DEFUN |INS-;even?;SB;3| (|x| $)
(SPADCALL (SPADCALL |x| (QREFELT $ 12)) (QREFELT $ 13)))
(DEFUN |INS-;positive?;SB;4| (|x| $)
(SPADCALL (|spadConstant| $ 9) |x| (QREFELT $ 15)))
(PUT '|INS-;copy;2S;5| '|SPADreplace| '(XLAM (|x|) |x|))
(DEFUN |INS-;copy;2S;5| (|x| $) |x|)
(DEFUN |INS-;bit?;2SB;6| (|x| |i| $)
(SPADCALL (SPADCALL |x| (SPADCALL |i| (QREFELT $ 18)) (QREFELT $ 19))
(QREFELT $ 12)))
(DEFUN |INS-;mask;2S;7| (|n| $)
(SPADCALL (SPADCALL (|spadConstant| $ 21) |n| (QREFELT $ 19))
(QREFELT $ 22)))
(PUT '|INS-;rational?;SB;8| '|SPADreplace| '(XLAM (|x|) 'T))
(DEFUN |INS-;rational?;SB;8| (|x| $) 'T)
(DEFUN |INS-;euclideanSize;SNni;9| (|x| $)
(PROG (#0=#:G1412 #1=#:G1413)
(RETURN
(COND
((SPADCALL |x| (|spadConstant| $ 9) (QREFELT $ 25))
(|error| "euclideanSize called on zero"))
((SPADCALL |x| (|spadConstant| $ 9) (QREFELT $ 15))
(PROG1 (LETT #0# (- (SPADCALL |x| (QREFELT $ 27)))
|INS-;euclideanSize;SNni;9|)
(|check-subtype| (>= #0# 0) '(|NonNegativeInteger|) #0#)))
('T
(PROG1 (LETT #1# (SPADCALL |x| (QREFELT $ 27))
|INS-;euclideanSize;SNni;9|)
(|check-subtype| (>= #1# 0) '(|NonNegativeInteger|) #1#)))))))
(DEFUN |INS-;convert;SF;10| (|x| $)
(SPADCALL (SPADCALL |x| (QREFELT $ 27)) (QREFELT $ 30)))
(DEFUN |INS-;convert;SDf;11| (|x| $)
(FLOAT (SPADCALL |x| (QREFELT $ 27)) MOST-POSITIVE-LONG-FLOAT))
(DEFUN |INS-;convert;SIf;12| (|x| $)
(SPADCALL (SPADCALL |x| (QREFELT $ 27)) (QREFELT $ 35)))
(DEFUN |INS-;retract;SI;13| (|x| $) (SPADCALL |x| (QREFELT $ 27)))
(DEFUN |INS-;convert;SP;14| (|x| $)
(SPADCALL (SPADCALL |x| (QREFELT $ 27)) (QREFELT $ 39)))
(DEFUN |INS-;factor;SF;15| (|x| $) (SPADCALL |x| (QREFELT $ 43)))
(DEFUN |INS-;squareFree;SF;16| (|x| $) (SPADCALL |x| (QREFELT $ 46)))
(DEFUN |INS-;prime?;SB;17| (|x| $) (SPADCALL |x| (QREFELT $ 49)))
(DEFUN |INS-;factorial;2S;18| (|x| $) (SPADCALL |x| (QREFELT $ 52)))
(DEFUN |INS-;binomial;3S;19| (|n| |m| $)
(SPADCALL |n| |m| (QREFELT $ 54)))
(DEFUN |INS-;permutation;3S;20| (|n| |m| $)
(SPADCALL |n| |m| (QREFELT $ 56)))
(DEFUN |INS-;retractIfCan;SU;21| (|x| $)
(CONS 0 (SPADCALL |x| (QREFELT $ 27))))
(DEFUN |INS-;init;S;22| ($) (|spadConstant| $ 9))
(DEFUN |INS-;nextItem;SU;23| (|n| $)
(COND
((SPADCALL |n| (QREFELT $ 61)) (CONS 0 (|spadConstant| $ 21)))
((SPADCALL (|spadConstant| $ 9) |n| (QREFELT $ 15))
(CONS 0 (SPADCALL |n| (QREFELT $ 18))))
('T (CONS 0 (SPADCALL (|spadConstant| $ 21) |n| (QREFELT $ 62))))))
(DEFUN |INS-;patternMatch;SP2Pmr;24| (|x| |p| |l| $)
(SPADCALL |x| |p| |l| (QREFELT $ 67)))
(DEFUN |INS-;rational;SF;25| (|x| $)
(SPADCALL (SPADCALL |x| (QREFELT $ 27)) (QREFELT $ 71)))
(DEFUN |INS-;rationalIfCan;SU;26| (|x| $)
(CONS 0 (SPADCALL (SPADCALL |x| (QREFELT $ 27)) (QREFELT $ 71))))
(DEFUN |INS-;symmetricRemainder;3S;27| (|x| |n| $)
(PROG (|r|)
(RETURN
(SEQ (LETT |r| (SPADCALL |x| |n| (QREFELT $ 75))
|INS-;symmetricRemainder;3S;27|)
(EXIT (COND
((SPADCALL |r| (|spadConstant| $ 9) (QREFELT $ 25))
|r|)
('T
(SEQ (COND
((SPADCALL |n| (|spadConstant| $ 9)
(QREFELT $ 15))
(LETT |n| (SPADCALL |n| (QREFELT $ 18))
|INS-;symmetricRemainder;3S;27|)))
(EXIT (COND
((SPADCALL (|spadConstant| $ 9) |r|
(QREFELT $ 15))
(COND
((SPADCALL |n|
(SPADCALL 2 |r| (QREFELT $ 77))
(QREFELT $ 15))
(SPADCALL |r| |n| (QREFELT $ 62)))
('T |r|)))
((NULL (SPADCALL (|spadConstant| $ 9)
(SPADCALL
(SPADCALL 2 |r|
(QREFELT $ 77))
|n| (QREFELT $ 78))
(QREFELT $ 15)))
(SPADCALL |r| |n| (QREFELT $ 78)))
('T |r|)))))))))))
(DEFUN |INS-;invmod;3S;28| (|a| |b| $)
(PROG (|q| |r| |r1| |c| |c1| |d| |d1|)
(RETURN
(SEQ (COND
((SPADCALL |a| (QREFELT $ 80))
(LETT |a| (SPADCALL |a| |b| (QREFELT $ 81))
|INS-;invmod;3S;28|)))
(LETT |c| |a| |INS-;invmod;3S;28|)
(LETT |c1| (|spadConstant| $ 21) |INS-;invmod;3S;28|)
(LETT |d| |b| |INS-;invmod;3S;28|)
(LETT |d1| (|spadConstant| $ 9) |INS-;invmod;3S;28|)
(SEQ G190
(COND
((NULL (SPADCALL (SPADCALL |d| (QREFELT $ 61))
(QREFELT $ 13)))
(GO G191)))
(SEQ (LETT |q| (SPADCALL |c| |d| (QREFELT $ 82))
|INS-;invmod;3S;28|)
(LETT |r|
(SPADCALL |c|
(SPADCALL |q| |d| (QREFELT $ 83))
(QREFELT $ 62))
|INS-;invmod;3S;28|)
(LETT |r1|
(SPADCALL |c1|
(SPADCALL |q| |d1| (QREFELT $ 83))
(QREFELT $ 62))
|INS-;invmod;3S;28|)
(LETT |c| |d| |INS-;invmod;3S;28|)
(LETT |c1| |d1| |INS-;invmod;3S;28|)
(LETT |d| |r| |INS-;invmod;3S;28|)
(EXIT (LETT |d1| |r1| |INS-;invmod;3S;28|)))
NIL (GO G190) G191 (EXIT NIL))
(EXIT (COND
((SPADCALL |c| (|spadConstant| $ 21) (QREFELT $ 25))
(COND
((SPADCALL |c1| (QREFELT $ 80))
(SPADCALL |c1| |b| (QREFELT $ 78)))
('T |c1|)))
('T (|error| "inverse does not exist"))))))))
(DEFUN |INS-;powmod;4S;29| (|x| |n| |p| $)
(PROG (|y| #0=#:G1470 |z|)
(RETURN
(SEQ (EXIT (SEQ (COND
((SPADCALL |x| (QREFELT $ 80))
(LETT |x| (SPADCALL |x| |p| (QREFELT $ 81))
|INS-;powmod;4S;29|)))
(EXIT (COND
((SPADCALL |x| (QREFELT $ 61))
(|spadConstant| $ 9))
((SPADCALL |n| (QREFELT $ 61))
(|spadConstant| $ 21))
('T
(SEQ (LETT |y| (|spadConstant| $ 21)
|INS-;powmod;4S;29|)
(LETT |z| |x| |INS-;powmod;4S;29|)
(EXIT
(SEQ G190 NIL
(SEQ
(COND
((SPADCALL |n| (QREFELT $ 12))
(LETT |y|
(SPADCALL |y| |z| |p|
(QREFELT $ 85))
|INS-;powmod;4S;29|)))
(EXIT
(COND
((SPADCALL
(LETT |n|
(SPADCALL |n|
(SPADCALL
(|spadConstant| $ 21)
(QREFELT $ 18))
(QREFELT $ 19))
|INS-;powmod;4S;29|)
(QREFELT $ 61))
(PROGN
(LETT #0# |y|
|INS-;powmod;4S;29|)
(GO #0#)))
('T
(LETT |z|
(SPADCALL |z| |z| |p|
(QREFELT $ 85))
|INS-;powmod;4S;29|)))))
NIL (GO G190) G191 (EXIT NIL)))))))))
#0# (EXIT #0#)))))
(DEFUN |IntegerNumberSystem&| (|#1|)
(PROG (|dv$1| |dv$| $ |pv$|)
(RETURN
(PROGN
(LETT |dv$1| (|devaluate| |#1|) . #0=(|IntegerNumberSystem&|))
(LETT |dv$| (LIST '|IntegerNumberSystem&| |dv$1|) . #0#)
(LETT $ (GETREFV 87) . #0#)
(QSETREFV $ 0 |dv$|)
(QSETREFV $ 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#))
(|stuffDomainSlots| $)
(QSETREFV $ 6 |#1|)
$))))
(MAKEPROP '|IntegerNumberSystem&| '|infovec|
(LIST '#(NIL NIL NIL NIL NIL NIL (|local| |#1|)
(|NonNegativeInteger|) |INS-;characteristic;Nni;1|
(0 . |Zero|) |INS-;differentiate;2S;2| (|Boolean|)
(4 . |odd?|) (9 . |not|) |INS-;even?;SB;3| (14 . <)
|INS-;positive?;SB;4| |INS-;copy;2S;5| (20 . -)
(25 . |shift|) |INS-;bit?;2SB;6| (31 . |One|) (35 . |dec|)
|INS-;mask;2S;7| |INS-;rational?;SB;8| (40 . =)
(|Integer|) (46 . |convert|) |INS-;euclideanSize;SNni;9|
(|Float|) (51 . |coerce|) |INS-;convert;SF;10|
(|DoubleFloat|) |INS-;convert;SDf;11| (|InputForm|)
(56 . |convert|) |INS-;convert;SIf;12|
|INS-;retract;SI;13| (|Pattern| 26) (61 . |coerce|)
|INS-;convert;SP;14| (|Factored| 6)
(|IntegerFactorizationPackage| 6) (66 . |factor|)
(|Factored| $) |INS-;factor;SF;15| (71 . |squareFree|)
|INS-;squareFree;SF;16| (|IntegerPrimesPackage| 6)
(76 . |prime?|) |INS-;prime?;SB;17|
(|IntegerCombinatoricFunctions| 6) (81 . |factorial|)
|INS-;factorial;2S;18| (86 . |binomial|)
|INS-;binomial;3S;19| (92 . |permutation|)
|INS-;permutation;3S;20| (|Union| 26 '"failed")
|INS-;retractIfCan;SU;21| |INS-;init;S;22| (98 . |zero?|)
(103 . -) (|Union| $ '"failed") |INS-;nextItem;SU;23|
(|PatternMatchResult| 26 6)
(|PatternMatchIntegerNumberSystem| 6)
(109 . |patternMatch|) (|PatternMatchResult| 26 $)
|INS-;patternMatch;SP2Pmr;24| (|Fraction| 26)
(116 . |coerce|) |INS-;rational;SF;25|
(|Union| 70 '"failed") |INS-;rationalIfCan;SU;26|
(121 . |rem|) (|PositiveInteger|) (127 . *) (133 . +)
|INS-;symmetricRemainder;3S;27| (139 . |negative?|)
(144 . |positiveRemainder|) (150 . |quo|) (156 . *)
|INS-;invmod;3S;28| (162 . |mulmod|) |INS-;powmod;4S;29|)
'#(|symmetricRemainder| 169 |squareFree| 175 |retractIfCan|
180 |retract| 185 |rationalIfCan| 190 |rational?| 195
|rational| 200 |prime?| 205 |powmod| 210 |positive?| 217
|permutation| 222 |patternMatch| 228 |nextItem| 235 |mask|
240 |invmod| 245 |init| 251 |factorial| 255 |factor| 260
|even?| 265 |euclideanSize| 270 |differentiate| 275 |copy|
280 |convert| 285 |characteristic| 305 |bit?| 309
|binomial| 315)
'NIL
(CONS (|makeByteWordVec2| 1 'NIL)
(CONS '#()
(CONS '#()
(|makeByteWordVec2| 86
'(0 6 0 9 1 6 11 0 12 1 11 0 0 13 2 6
11 0 0 15 1 6 0 0 18 2 6 0 0 0 19 0 6
0 21 1 6 0 0 22 2 6 11 0 0 25 1 6 26
0 27 1 29 0 26 30 1 34 0 26 35 1 38 0
26 39 1 42 41 6 43 1 42 41 6 46 1 48
11 6 49 1 51 6 6 52 2 51 6 6 6 54 2
51 6 6 6 56 1 6 11 0 61 2 6 0 0 0 62
3 66 65 6 38 65 67 1 70 0 26 71 2 6 0
0 0 75 2 6 0 76 0 77 2 6 0 0 0 78 1 6
11 0 80 2 6 0 0 0 81 2 6 0 0 0 82 2 6
0 0 0 83 3 6 0 0 0 0 85 2 0 0 0 0 79
1 0 44 0 47 1 0 58 0 59 1 0 26 0 37 1
0 73 0 74 1 0 11 0 24 1 0 70 0 72 1 0
11 0 50 3 0 0 0 0 0 86 1 0 11 0 16 2
0 0 0 0 57 3 0 68 0 38 68 69 1 0 63 0
64 1 0 0 0 23 2 0 0 0 0 84 0 0 0 60 1
0 0 0 53 1 0 44 0 45 1 0 11 0 14 1 0
7 0 28 1 0 0 0 10 1 0 0 0 17 1 0 32 0
33 1 0 29 0 31 1 0 38 0 40 1 0 34 0
36 0 0 7 8 2 0 11 0 0 20 2 0 0 0 0
55)))))
'|lookupComplete|))
@
\section{domain SINT SingleInteger}
The definition of {\bf one?} has been rewritten
as it relies on calling {\bf ONEP} which is a function specific
to Codemist Common Lisp but is not defined in Common Lisp.
<<domain SINT SingleInteger>>=
)abbrev domain SINT SingleInteger
-- following patch needed to deal with *:(I,%) -> %
-- affects behavior of SourceLevelSubset
--)bo $noSubsets := true
-- No longer - JHD !! still needed 5/3/91 BMT
++ Author: Michael Monagan
++ Date Created:
++ January 1988
++ Change History:
++ Basic Operations: max, min,
++ not, and, or, xor, Not, And, Or
++ Related Constructors:
++ Keywords: single integer
++ Description: SingleInteger is intended to support machine integer
++ arithmetic.
-- MAXINT, BASE (machine integer constants)
-- MODULUS, MULTIPLIER (random number generator constants)
-- Lisp dependencies
-- EQ, ABSVAL, TIMES, INTEGER-LENGTH, HASHEQ, REMAINDER
-- QSLESSP, QSGREATERP, QSADD1, QSSUB1, QSMINUS, QSPLUS, QSDIFFERENCE
-- QSTIMES, QSREMAINDER, QSODDP, QSZEROP, QSMAX, QSMIN, QSNOT, QSAND
-- QSOR, QSXOR, QSLEFTSHIFT, QSADDMOD, QSDIFMOD, QSMULTMOD
SingleInteger(): Join(IntegerNumberSystem,Logic,OpenMath) with
canonical
++ \spad{canonical} means that mathematical equality is implied by data structure equality.
canonicalsClosed
++ \spad{canonicalClosed} means two positives multiply to give positive.
noetherian
++ \spad{noetherian} all ideals are finitely generated (in fact principal).
max : () -> %
++ max() returns the largest single integer.
min : () -> %
++ min() returns the smallest single integer.
-- bit operations
"not": % -> %
++ not(n) returns the bit-by-bit logical {\em not} of the single integer n.
"~" : % -> %
++ ~ n returns the bit-by-bit logical {\em not } of the single integer n.
"/\": (%, %) -> %
++ n /\ m returns the bit-by-bit logical {\em and} of
++ the single integers n and m.
"\/" : (%, %) -> %
++ n \/ m returns the bit-by-bit logical {\em or} of
++ the single integers n and m.
"xor": (%, %) -> %
++ xor(n,m) returns the bit-by-bit logical {\em xor} of
++ the single integers n and m.
Not : % -> %
++ Not(n) returns the bit-by-bit logical {\em not} of the single integer n.
And : (%,%) -> %
++ And(n,m) returns the bit-by-bit logical {\em and} of
++ the single integers n and m.
Or : (%,%) -> %
++ Or(n,m) returns the bit-by-bit logical {\em or} of
++ the single integers n and m.
== add
seed : % := 1$Lisp -- for random()
MAXINT ==> MOST_-POSITIVE_-FIXNUM$Lisp
MININT ==> MOST_-NEGATIVE_-FIXNUM$Lisp
BASE ==> 67108864$Lisp -- 2**26
MULTIPLIER ==> 314159269$Lisp -- from Knuth's table
MODULUS ==> 2147483647$Lisp -- 2**31-1
writeOMSingleInt(dev: OpenMathDevice, x: %): Void ==
if x < 0 then
OMputApp(dev)
OMputSymbol(dev, "arith1", "unary_minus")
OMputInteger(dev, convert(-x))
OMputEndApp(dev)
else
OMputInteger(dev, convert(x))
OMwrite(x: %): String ==
s: String := ""
sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
OMputObject(dev)
writeOMSingleInt(dev, x)
OMputEndObject(dev)
OMclose(dev)
s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
s
OMwrite(x: %, wholeObj: Boolean): String ==
s: String := ""
sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
if wholeObj then
OMputObject(dev)
writeOMSingleInt(dev, x)
if wholeObj then
OMputEndObject(dev)
OMclose(dev)
s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
s
OMwrite(dev: OpenMathDevice, x: %): Void ==
OMputObject(dev)
writeOMSingleInt(dev, x)
OMputEndObject(dev)
OMwrite(dev: OpenMathDevice, x: %, wholeObj: Boolean): Void ==
if wholeObj then
OMputObject(dev)
writeOMSingleInt(dev, x)
if wholeObj then
OMputEndObject(dev)
reducedSystem m == m pretend Matrix(Integer)
coerce(x):OutputForm == (convert(x)@Integer)::OutputForm
convert(x:%):Integer == x pretend Integer
i:Integer * y:% == i::% * y
0 == 0$Lisp
1 == 1$Lisp
base() == 2$Lisp
max() == MAXINT
min() == MININT
x = y == EQL(x,y)$Lisp
_~ x == LOGNOT(x)$Lisp
not(x) == LOGNOT(x)$Lisp
_/_\(x,y) == LOGAND(x,y)$Lisp
_\_/(x,y) == LOGIOR(x,y)$Lisp
Not(x) == LOGNOT(x)$Lisp
And(x,y) == LOGAND(x,y)$Lisp
Or(x,y) == LOGIOR(x,y)$Lisp
xor(x,y) == LOGXOR(x,y)$Lisp
x < y == QSLESSP(x,y)$Lisp
inc x == QSADD1(x)$Lisp
dec x == QSSUB1(x)$Lisp
- x == QSMINUS(x)$Lisp
x + y == QSPLUS(x,y)$Lisp
x:% - y:% == QSDIFFERENCE(x,y)$Lisp
x:% * y:% == QSTIMES(x,y)$Lisp
x:% ** n:NonNegativeInteger == ((EXPT(x, n)$Lisp) pretend Integer)::%
x quo y == QSQUOTIENT(x,y)$Lisp
x rem y == QSREMAINDER(x,y)$Lisp
divide(x, y) == CONS(QSQUOTIENT(x,y)$Lisp,QSREMAINDER(x,y)$Lisp)$Lisp
gcd(x,y) == GCD(x,y)$Lisp
abs(x) == QSABSVAL(x)$Lisp
odd?(x) == QSODDP(x)$Lisp
zero?(x) == QSZEROP(x)$Lisp
-- one?(x) == ONEP(x)$Lisp
one?(x) == x = 1
max(x,y) == QSMAX(x,y)$Lisp
min(x,y) == QSMIN(x,y)$Lisp
hash(x) == HASHEQ(x)$Lisp
length(x) == INTEGER_-LENGTH(x)$Lisp
shift(x,n) == QSLEFTSHIFT(x,n)$Lisp
mulmod(a,b,p) == QSMULTMOD(a,b,p)$Lisp
addmod(a,b,p) == QSADDMOD(a,b,p)$Lisp
submod(a,b,p) == QSDIFMOD(a,b,p)$Lisp
negative?(x) == QSMINUSP$Lisp x
reducedSystem(m, v) ==
[m pretend Matrix(Integer), v pretend Vector(Integer)]
positiveRemainder(x,n) ==
r := QSREMAINDER(x,n)$Lisp
QSMINUSP(r)$Lisp =>
QSMINUSP(n)$Lisp => QSDIFFERENCE(x, n)$Lisp
QSPLUS(r, n)$Lisp
r
coerce(x:Integer):% ==
(x <= max pretend Integer) and (x >= min pretend Integer) =>
x pretend %
error "integer too large to represent in a machine word"
random() ==
seed := REMAINDER(TIMES(MULTIPLIER,seed)$Lisp,MODULUS)$Lisp
REMAINDER(seed,BASE)$Lisp
random(n) == RANDOM(n)$Lisp
UCA ==> Record(unit:%,canonical:%,associate:%)
unitNormal x ==
x < 0 => [-1,-x,-1]$UCA
[1,x,1]$UCA
)bo $noSubsets := false
@
\section{SINT.lsp BOOTSTRAP}
<<SINT.lsp BOOTSTRAP>>=
(/VERSIONCHECK 2)
(DEFUN |SINT;writeOMSingleInt| (|dev| |x| $)
(SEQ (COND
((QSLESSP |x| 0)
(SEQ (SPADCALL |dev| (|getShellEntry| $ 9))
(SPADCALL |dev| "arith1" "unaryminus"
(|getShellEntry| $ 11))
(SPADCALL |dev| (QSMINUS |x|) (|getShellEntry| $ 13))
(EXIT (SPADCALL |dev| (|getShellEntry| $ 14)))))
('T (SPADCALL |dev| |x| (|getShellEntry| $ 13))))))
(DEFUN |SINT;OMwrite;$S;2| (|x| $)
(PROG (|sp| |dev| |s|)
(RETURN
(SEQ (LETT |s| "" |SINT;OMwrite;$S;2|)
(LETT |sp| (OM-STRINGTOSTRINGPTR |s|) |SINT;OMwrite;$S;2|)
(LETT |dev|
(SPADCALL |sp| (SPADCALL (|getShellEntry| $ 16))
(|getShellEntry| $ 17))
|SINT;OMwrite;$S;2|)
(SPADCALL |dev| (|getShellEntry| $ 18))
(|SINT;writeOMSingleInt| |dev| |x| $)
(SPADCALL |dev| (|getShellEntry| $ 19))
(SPADCALL |dev| (|getShellEntry| $ 20))
(LETT |s| (OM-STRINGPTRTOSTRING |sp|) |SINT;OMwrite;$S;2|)
(EXIT |s|)))))
(DEFUN |SINT;OMwrite;$BS;3| (|x| |wholeObj| $)
(PROG (|sp| |dev| |s|)
(RETURN
(SEQ (LETT |s| "" |SINT;OMwrite;$BS;3|)
(LETT |sp| (OM-STRINGTOSTRINGPTR |s|) |SINT;OMwrite;$BS;3|)
(LETT |dev|
(SPADCALL |sp| (SPADCALL (|getShellEntry| $ 16))
(|getShellEntry| $ 17))
|SINT;OMwrite;$BS;3|)
(COND (|wholeObj| (SPADCALL |dev| (|getShellEntry| $ 18))))
(|SINT;writeOMSingleInt| |dev| |x| $)
(COND (|wholeObj| (SPADCALL |dev| (|getShellEntry| $ 19))))
(SPADCALL |dev| (|getShellEntry| $ 20))
(LETT |s| (OM-STRINGPTRTOSTRING |sp|) |SINT;OMwrite;$BS;3|)
(EXIT |s|)))))
(DEFUN |SINT;OMwrite;Omd$V;4| (|dev| |x| $)
(SEQ (SPADCALL |dev| (|getShellEntry| $ 18))
(|SINT;writeOMSingleInt| |dev| |x| $)
(EXIT (SPADCALL |dev| (|getShellEntry| $ 19)))))
(DEFUN |SINT;OMwrite;Omd$BV;5| (|dev| |x| |wholeObj| $)
(SEQ (COND (|wholeObj| (SPADCALL |dev| (|getShellEntry| $ 18))))
(|SINT;writeOMSingleInt| |dev| |x| $)
(EXIT (COND
(|wholeObj| (SPADCALL |dev| (|getShellEntry| $ 19)))))))
(PUT '|SINT;reducedSystem;MM;6| '|SPADreplace| '(XLAM (|m|) |m|))
(DEFUN |SINT;reducedSystem;MM;6| (|m| $) |m|)
(DEFUN |SINT;coerce;$Of;7| (|x| $)
(SPADCALL |x| (|getShellEntry| $ 30)))
(PUT '|SINT;convert;$I;8| '|SPADreplace| '(XLAM (|x|) |x|))
(DEFUN |SINT;convert;$I;8| (|x| $) |x|)
(DEFUN |SINT;*;I2$;9| (|i| |y| $)
(QSTIMES (SPADCALL |i| (|getShellEntry| $ 33)) |y|))
(PUT '|SINT;Zero;$;10| '|SPADreplace| '(XLAM NIL 0))
(DEFUN |SINT;Zero;$;10| ($) 0)
(PUT '|SINT;One;$;11| '|SPADreplace| '(XLAM NIL 1))
(DEFUN |SINT;One;$;11| ($) 1)
(PUT '|SINT;base;$;12| '|SPADreplace| '(XLAM NIL 2))
(DEFUN |SINT;base;$;12| ($) 2)
(PUT '|SINT;max;$;13| '|SPADreplace| '(XLAM NIL MOST-POSITIVE-FIXNUM))
(DEFUN |SINT;max;$;13| ($) MOST-POSITIVE-FIXNUM)
(PUT '|SINT;min;$;14| '|SPADreplace| '(XLAM NIL MOST-NEGATIVE-FIXNUM))
(DEFUN |SINT;min;$;14| ($) MOST-NEGATIVE-FIXNUM)
(PUT '|SINT;=;2$B;15| '|SPADreplace| 'EQL)
(DEFUN |SINT;=;2$B;15| (|x| |y| $) (EQL |x| |y|))
(PUT '|SINT;~;2$;16| '|SPADreplace| 'LOGNOT)
(DEFUN |SINT;~;2$;16| (|x| $) (LOGNOT |x|))
(PUT '|SINT;not;2$;17| '|SPADreplace| 'LOGNOT)
(DEFUN |SINT;not;2$;17| (|x| $) (LOGNOT |x|))
(PUT '|SINT;/\\;3$;18| '|SPADreplace| 'LOGAND)
(DEFUN |SINT;/\\;3$;18| (|x| |y| $) (LOGAND |x| |y|))
(PUT '|SINT;\\/;3$;19| '|SPADreplace| 'LOGIOR)
(DEFUN |SINT;\\/;3$;19| (|x| |y| $) (LOGIOR |x| |y|))
(PUT '|SINT;Not;2$;20| '|SPADreplace| 'LOGNOT)
(DEFUN |SINT;Not;2$;20| (|x| $) (LOGNOT |x|))
(PUT '|SINT;And;3$;21| '|SPADreplace| 'LOGAND)
(DEFUN |SINT;And;3$;21| (|x| |y| $) (LOGAND |x| |y|))
(PUT '|SINT;Or;3$;22| '|SPADreplace| 'LOGIOR)
(DEFUN |SINT;Or;3$;22| (|x| |y| $) (LOGIOR |x| |y|))
(PUT '|SINT;xor;3$;23| '|SPADreplace| 'LOGXOR)
(DEFUN |SINT;xor;3$;23| (|x| |y| $) (LOGXOR |x| |y|))
(PUT '|SINT;<;2$B;24| '|SPADreplace| 'QSLESSP)
(DEFUN |SINT;<;2$B;24| (|x| |y| $) (QSLESSP |x| |y|))
(PUT '|SINT;inc;2$;25| '|SPADreplace| 'QSADD1)
(DEFUN |SINT;inc;2$;25| (|x| $) (QSADD1 |x|))
(PUT '|SINT;dec;2$;26| '|SPADreplace| 'QSSUB1)
(DEFUN |SINT;dec;2$;26| (|x| $) (QSSUB1 |x|))
(PUT '|SINT;-;2$;27| '|SPADreplace| 'QSMINUS)
(DEFUN |SINT;-;2$;27| (|x| $) (QSMINUS |x|))
(PUT '|SINT;+;3$;28| '|SPADreplace| 'QSPLUS)
(DEFUN |SINT;+;3$;28| (|x| |y| $) (QSPLUS |x| |y|))
(PUT '|SINT;-;3$;29| '|SPADreplace| 'QSDIFFERENCE)
(DEFUN |SINT;-;3$;29| (|x| |y| $) (QSDIFFERENCE |x| |y|))
(PUT '|SINT;*;3$;30| '|SPADreplace| 'QSTIMES)
(DEFUN |SINT;*;3$;30| (|x| |y| $) (QSTIMES |x| |y|))
(DEFUN |SINT;**;$Nni$;31| (|x| |n| $)
(SPADCALL (EXPT |x| |n|) (|getShellEntry| $ 33)))
(PUT '|SINT;quo;3$;32| '|SPADreplace| 'QSQUOTIENT)
(DEFUN |SINT;quo;3$;32| (|x| |y| $) (QSQUOTIENT |x| |y|))
(PUT '|SINT;rem;3$;33| '|SPADreplace| 'QSREMAINDER)
(DEFUN |SINT;rem;3$;33| (|x| |y| $) (QSREMAINDER |x| |y|))
(DEFUN |SINT;divide;2$R;34| (|x| |y| $)
(CONS (QSQUOTIENT |x| |y|) (QSREMAINDER |x| |y|)))
(PUT '|SINT;gcd;3$;35| '|SPADreplace| 'GCD)
(DEFUN |SINT;gcd;3$;35| (|x| |y| $) (GCD |x| |y|))
(PUT '|SINT;abs;2$;36| '|SPADreplace| 'QSABSVAL)
(DEFUN |SINT;abs;2$;36| (|x| $) (QSABSVAL |x|))
(PUT '|SINT;odd?;$B;37| '|SPADreplace| 'QSODDP)
(DEFUN |SINT;odd?;$B;37| (|x| $) (QSODDP |x|))
(PUT '|SINT;zero?;$B;38| '|SPADreplace| 'QSZEROP)
(DEFUN |SINT;zero?;$B;38| (|x| $) (QSZEROP |x|))
(PUT '|SINT;one?;$B;39| '|SPADreplace| '(XLAM (|x|) (EQL |x| 1)))
(DEFUN |SINT;one?;$B;39| (|x| $) (EQL |x| 1))
(PUT '|SINT;max;3$;40| '|SPADreplace| 'QSMAX)
(DEFUN |SINT;max;3$;40| (|x| |y| $) (QSMAX |x| |y|))
(PUT '|SINT;min;3$;41| '|SPADreplace| 'QSMIN)
(DEFUN |SINT;min;3$;41| (|x| |y| $) (QSMIN |x| |y|))
(PUT '|SINT;hash;2$;42| '|SPADreplace| 'HASHEQ)
(DEFUN |SINT;hash;2$;42| (|x| $) (HASHEQ |x|))
(PUT '|SINT;length;2$;43| '|SPADreplace| 'INTEGER-LENGTH)
(DEFUN |SINT;length;2$;43| (|x| $) (INTEGER-LENGTH |x|))
(PUT '|SINT;shift;3$;44| '|SPADreplace| 'QSLEFTSHIFT)
(DEFUN |SINT;shift;3$;44| (|x| |n| $) (QSLEFTSHIFT |x| |n|))
(PUT '|SINT;mulmod;4$;45| '|SPADreplace| 'QSMULTMOD)
(DEFUN |SINT;mulmod;4$;45| (|a| |b| |p| $) (QSMULTMOD |a| |b| |p|))
(PUT '|SINT;addmod;4$;46| '|SPADreplace| 'QSADDMOD)
(DEFUN |SINT;addmod;4$;46| (|a| |b| |p| $) (QSADDMOD |a| |b| |p|))
(PUT '|SINT;submod;4$;47| '|SPADreplace| 'QSDIFMOD)
(DEFUN |SINT;submod;4$;47| (|a| |b| |p| $) (QSDIFMOD |a| |b| |p|))
(PUT '|SINT;negative?;$B;48| '|SPADreplace| 'QSMINUSP)
(DEFUN |SINT;negative?;$B;48| (|x| $) (QSMINUSP |x|))
(PUT '|SINT;reducedSystem;MVR;49| '|SPADreplace| 'CONS)
(DEFUN |SINT;reducedSystem;MVR;49| (|m| |v| $) (CONS |m| |v|))
(DEFUN |SINT;positiveRemainder;3$;50| (|x| |n| $)
(PROG (|r|)
(RETURN
(SEQ (LETT |r| (QSREMAINDER |x| |n|)
|SINT;positiveRemainder;3$;50|)
(EXIT (COND
((QSMINUSP |r|)
(COND
((QSMINUSP |n|) (QSDIFFERENCE |x| |n|))
('T (QSPLUS |r| |n|))))
('T |r|)))))))
(DEFUN |SINT;coerce;I$;51| (|x| $)
(SEQ (COND
((NULL (< MOST-POSITIVE-FIXNUM |x|))
(COND ((NULL (< |x| MOST-NEGATIVE-FIXNUM)) (EXIT |x|)))))
(EXIT (|error| "integer too large to represent in a machine word"))))
(DEFUN |SINT;random;$;52| ($)
(SEQ (SETELT $ 6
(REMAINDER (TIMES 314159269 (|getShellEntry| $ 6))
2147483647))
(EXIT (REMAINDER (|getShellEntry| $ 6) 67108864))))
(PUT '|SINT;random;2$;53| '|SPADreplace| 'RANDOM)
(DEFUN |SINT;random;2$;53| (|n| $) (RANDOM |n|))
(DEFUN |SINT;unitNormal;$R;54| (|x| $)
(COND
((QSLESSP |x| 0) (VECTOR -1 (QSMINUS |x|) -1))
('T (VECTOR 1 |x| 1))))
(DEFUN |SingleInteger| ()
(PROG ()
(RETURN
(PROG (#0=#:G1486)
(RETURN
(COND
((LETT #0# (HGET |$ConstructorCache| '|SingleInteger|)
|SingleInteger|)
(|CDRwithIncrement| (CDAR #0#)))
('T
(UNWIND-PROTECT
(PROG1 (CDDAR (HPUT |$ConstructorCache| '|SingleInteger|
(LIST
(CONS NIL
(CONS 1 (|SingleInteger;|))))))
(LETT #0# T |SingleInteger|))
(COND
((NOT #0#)
(HREM |$ConstructorCache| '|SingleInteger|)))))))))))
(DEFUN |SingleInteger;| ()
(PROG (|dv$| $ |pv$|)
(RETURN
(PROGN
(LETT |dv$| '(|SingleInteger|) . #0=(|SingleInteger|))
(LETT $ (|newShell| 105) . #0#)
(|setShellEntry| $ 0 |dv$|)
(|setShellEntry| $ 3
(LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#))
(|haddProp| |$ConstructorCache| '|SingleInteger| NIL
(CONS 1 $))
(|stuffDomainSlots| $)
(|setShellEntry| $ 6 1)
$))))
(MAKEPROP '|SingleInteger| '|infovec|
(LIST '#(NIL NIL NIL NIL NIL NIL '|seed| (|Void|)
(|OpenMathDevice|) (0 . |OMputApp|) (|String|)
(5 . |OMputSymbol|) (|Integer|) (12 . |OMputInteger|)
(18 . |OMputEndApp|) (|OpenMathEncoding|)
(23 . |OMencodingXML|) (27 . |OMopenString|)
(33 . |OMputObject|) (38 . |OMputEndObject|)
(43 . |OMclose|) |SINT;OMwrite;$S;2| (|Boolean|)
|SINT;OMwrite;$BS;3| |SINT;OMwrite;Omd$V;4|
|SINT;OMwrite;Omd$BV;5| (|Matrix| 12) (|Matrix| $)
|SINT;reducedSystem;MM;6| (|OutputForm|) (48 . |coerce|)
|SINT;coerce;$Of;7| |SINT;convert;$I;8| (53 . |coerce|)
|SINT;*;I2$;9|
(CONS IDENTITY
(FUNCALL (|dispatchFunction| |SINT;Zero;$;10|) $))
(CONS IDENTITY
(FUNCALL (|dispatchFunction| |SINT;One;$;11|) $))
|SINT;base;$;12| |SINT;max;$;13| |SINT;min;$;14|
|SINT;=;2$B;15| |SINT;~;2$;16| |SINT;not;2$;17|
|SINT;/\\;3$;18| |SINT;\\/;3$;19| |SINT;Not;2$;20|
|SINT;And;3$;21| |SINT;Or;3$;22| |SINT;xor;3$;23|
|SINT;<;2$B;24| |SINT;inc;2$;25| |SINT;dec;2$;26|
|SINT;-;2$;27| |SINT;+;3$;28| |SINT;-;3$;29|
|SINT;*;3$;30| (|NonNegativeInteger|) |SINT;**;$Nni$;31|
|SINT;quo;3$;32| |SINT;rem;3$;33|
(|Record| (|:| |quotient| $) (|:| |remainder| $))
|SINT;divide;2$R;34| |SINT;gcd;3$;35| |SINT;abs;2$;36|
|SINT;odd?;$B;37| |SINT;zero?;$B;38| |SINT;one?;$B;39|
|SINT;max;3$;40| |SINT;min;3$;41| |SINT;hash;2$;42|
|SINT;length;2$;43| |SINT;shift;3$;44| |SINT;mulmod;4$;45|
|SINT;addmod;4$;46| |SINT;submod;4$;47|
|SINT;negative?;$B;48| (|Vector| 12)
(|Record| (|:| |mat| 26) (|:| |vec| 76)) (|Vector| $)
|SINT;reducedSystem;MVR;49| |SINT;positiveRemainder;3$;50|
|SINT;coerce;I$;51| |SINT;random;$;52| |SINT;random;2$;53|
(|Record| (|:| |unit| $) (|:| |canonical| $)
(|:| |associate| $))
|SINT;unitNormal;$R;54| (|Fraction| 12)
(|Union| 86 '"failed") (|Union| $ '"failed") (|Float|)
(|DoubleFloat|) (|Pattern| 12) (|PatternMatchResult| 12 $)
(|InputForm|) (|Union| 12 '"failed") (|List| $)
(|Record| (|:| |coef| 95) (|:| |generator| $))
(|Union| 95 '"failed")
(|Record| (|:| |coef1| $) (|:| |coef2| $)
(|:| |generator| $))
(|Record| (|:| |coef1| $) (|:| |coef2| $))
(|Union| 99 '"failed") (|Factored| $)
(|SparseUnivariatePolynomial| $) (|PositiveInteger|)
(|SingleInteger|))
'#(~= 58 ~ 64 |zero?| 69 |xor| 74 |unitNormal| 80
|unitCanonical| 85 |unit?| 90 |symmetricRemainder| 95
|subtractIfCan| 101 |submod| 107 |squareFreePart| 114
|squareFree| 119 |sizeLess?| 124 |sign| 130 |shift| 135
|sample| 141 |retractIfCan| 145 |retract| 150 |rem| 155
|reducedSystem| 161 |recip| 172 |rationalIfCan| 177
|rational?| 182 |rational| 187 |random| 192 |quo| 201
|principalIdeal| 207 |prime?| 212 |powmod| 217
|positiveRemainder| 224 |positive?| 230 |permutation| 235
|patternMatch| 241 |one?| 248 |odd?| 253 |not| 258
|nextItem| 263 |negative?| 268 |multiEuclidean| 273
|mulmod| 279 |min| 286 |max| 296 |mask| 306 |length| 311
|lcm| 316 |latex| 327 |invmod| 332 |init| 338 |inc| 342
|hash| 347 |gcdPolynomial| 357 |gcd| 363 |factorial| 374
|factor| 379 |extendedEuclidean| 384 |exquo| 397
|expressIdealMember| 403 |even?| 409 |euclideanSize| 414
|divide| 419 |differentiate| 425 |dec| 436 |copy| 441
|convert| 446 |coerce| 471 |characteristic| 491 |bit?| 495
|binomial| 501 |base| 507 |associates?| 511 |addmod| 517
|abs| 524 ^ 529 |\\/| 541 |Zero| 547 |Or| 551 |One| 557
|OMwrite| 561 |Not| 585 D 590 |And| 601 >= 607 > 613 = 619
<= 625 < 631 |/\\| 637 - 643 + 654 ** 660 * 672)
'((|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&| |Logic&| NIL
|SetCategory&| NIL NIL NIL NIL NIL NIL
|RetractableTo&| NIL |BasicType&| NIL)
(CONS '#((|IntegerNumberSystem|)
(|EuclideanDomain|)
(|UniqueFactorizationDomain|)
(|PrincipalIdealDomain|)
(|OrderedIntegralDomain|) (|GcdDomain|)
(|IntegralDomain|) (|Algebra| $$)
(|CharacteristicZero|)
(|LinearlyExplicitRingOver| 12)
(|DifferentialRing|) (|OrderedRing|)
(|CommutativeRing|) (|EntireRing|)
(|Module| $$) (|OrderedAbelianGroup|)
(|BiModule| $$ $$) (|Ring|)
(|OrderedCancellationAbelianMonoid|)
(|LeftModule| $$) (|Rng|)
(|RightModule| $$)
(|OrderedAbelianMonoid|)
(|AbelianGroup|)
(|OrderedAbelianSemiGroup|)
(|CancellationAbelianMonoid|)
(|AbelianMonoid|) (|Monoid|)
(|StepThrough|) (|PatternMatchable| 12)
(|OrderedSet|) (|AbelianSemiGroup|)
(|SemiGroup|) (|Logic|) (|RealConstant|)
(|SetCategory|) (|OpenMath|)
(|ConvertibleTo| 89)
(|ConvertibleTo| 90)
(|CombinatorialFunctionCategory|)
(|ConvertibleTo| 91)
(|ConvertibleTo| 93)
(|RetractableTo| 12)
(|ConvertibleTo| 12) (|BasicType|)
(|CoercibleTo| 29))
(|makeByteWordVec2| 104
'(1 8 7 0 9 3 8 7 0 10 10 11 2 8 7 0 12
13 1 8 7 0 14 0 15 0 16 2 8 0 10 15
17 1 8 7 0 18 1 8 7 0 19 1 8 7 0 20 1
12 29 0 30 1 0 0 12 33 2 0 22 0 0 1 1
0 0 0 41 1 0 22 0 65 2 0 0 0 0 48 1 0
84 0 85 1 0 0 0 1 1 0 22 0 1 2 0 0 0
0 1 2 0 88 0 0 1 3 0 0 0 0 0 74 1 0 0
0 1 1 0 101 0 1 2 0 22 0 0 1 1 0 12 0
1 2 0 0 0 0 71 0 0 0 1 1 0 94 0 1 1 0
12 0 1 2 0 0 0 0 59 1 0 26 27 28 2 0
77 27 78 79 1 0 88 0 1 1 0 87 0 1 1 0
22 0 1 1 0 86 0 1 1 0 0 0 83 0 0 0 82
2 0 0 0 0 58 1 0 96 95 1 1 0 22 0 1 3
0 0 0 0 0 1 2 0 0 0 0 80 1 0 22 0 1 2
0 0 0 0 1 3 0 92 0 91 92 1 1 0 22 0
66 1 0 22 0 64 1 0 0 0 42 1 0 88 0 1
1 0 22 0 75 2 0 97 95 0 1 3 0 0 0 0 0
72 0 0 0 39 2 0 0 0 0 68 0 0 0 38 2 0
0 0 0 67 1 0 0 0 1 1 0 0 0 70 1 0 0
95 1 2 0 0 0 0 1 1 0 10 0 1 2 0 0 0 0
1 0 0 0 1 1 0 0 0 50 1 0 0 0 69 1 0
104 0 1 2 0 102 102 102 1 1 0 0 95 1
2 0 0 0 0 62 1 0 0 0 1 1 0 101 0 1 2
0 98 0 0 1 3 0 100 0 0 0 1 2 0 88 0 0
1 2 0 97 95 0 1 1 0 22 0 1 1 0 56 0 1
2 0 60 0 0 61 1 0 0 0 1 2 0 0 0 56 1
1 0 0 0 51 1 0 0 0 1 1 0 89 0 1 1 0
90 0 1 1 0 91 0 1 1 0 93 0 1 1 0 12 0
32 1 0 0 12 81 1 0 0 0 1 1 0 0 12 81
1 0 29 0 31 0 0 56 1 2 0 22 0 0 1 2 0
0 0 0 1 0 0 0 37 2 0 22 0 0 1 3 0 0 0
0 0 73 1 0 0 0 63 2 0 0 0 56 1 2 0 0
0 103 1 2 0 0 0 0 44 0 0 0 35 2 0 0 0
0 47 0 0 0 36 3 0 7 8 0 22 25 2 0 10
0 22 23 2 0 7 8 0 24 1 0 10 0 21 1 0
0 0 45 1 0 0 0 1 2 0 0 0 56 1 2 0 0 0
0 46 2 0 22 0 0 1 2 0 22 0 0 1 2 0 22
0 0 40 2 0 22 0 0 1 2 0 22 0 0 49 2 0
0 0 0 43 1 0 0 0 52 2 0 0 0 0 54 2 0
0 0 0 53 2 0 0 0 56 57 2 0 0 0 103 1
2 0 0 0 0 55 2 0 0 12 0 34 2 0 0 56 0
1 2 0 0 103 0 1)))))
'|lookupComplete|))
(MAKEPROP '|SingleInteger| 'NILADIC T)
@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
-- - Redistributions of source code must retain the above copyright
-- notice, this list of conditions and the following disclaimer.
--
-- - Redistributions in binary form must reproduce the above copyright
-- notice, this list of conditions and the following disclaimer in
-- the documentation and/or other materials provided with the
-- distribution.
--
-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the
-- names of its contributors may be used to endorse or promote products
-- derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>
<<category INS IntegerNumberSystem>>
<<domain SINT SingleInteger>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}