From ab8cc85adde879fb963c94d15675783f2cf4b183 Mon Sep 17 00:00:00 2001 From: dos-reis Date: Tue, 14 Aug 2007 05:14:52 +0000 Subject: Initial population. --- src/algebra/si.spad.pamphlet | 1557 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1557 insertions(+) create mode 100644 src/algebra/si.spad.pamphlet (limited to 'src/algebra/si.spad.pamphlet') diff --git a/src/algebra/si.spad.pamphlet b/src/algebra/si.spad.pamphlet new file mode 100644 index 00000000..b7be18aa --- /dev/null +++ b/src/algebra/si.spad.pamphlet @@ -0,0 +1,1557 @@ +\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} +<>= +)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

1}, means \spad{a+b mod p}. + submod : (%,%,%) -> % + ++ submod(a,b,p), \spad{0<=a,b

1}, means \spad{a-b mod p}. + mulmod : (%,%,%) -> % + ++ mulmod(a,b,p), \spad{0<=a,b

1}, means \spad{a*b mod p}. + powmod : (%,%,%) -> % + ++ powmod(a,b,p), \spad{0<=a,b

1}, means \spad{a**b mod p}. + invmod : (%,%) -> % + ++ invmod(a,b), \spad{0<=a1}, \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. +<>= + +(/VERSIONCHECK 2) + +(SETQ |IntegerNumberSystem;AL| (QUOTE NIL)) + +(DEFUN |IntegerNumberSystem| NIL + (LET (#:G1068) + (COND + (|IntegerNumberSystem;AL|) + (T (SETQ |IntegerNumberSystem;AL| (|IntegerNumberSystem;|)))))) + +(DEFUN |IntegerNumberSystem;| NIL (PROG (#0=#:G1066) + (RETURN + (PROG1 + (LETT #0# + (|sublisV| + (PAIR + (QUOTE (#1=#:G1060 #2=#:G1061 #3=#:G1062 + #4=#:G1063 #5=#:G1064 #6=#:G1065)) + (LIST + (QUOTE (|Integer|)) + (QUOTE (|Integer|)) + (QUOTE (|Integer|)) + (QUOTE (|InputForm|)) + (QUOTE (|Pattern| (|Integer|))) + (QUOTE (|Integer|)))) + (|Join| + (|UniqueFactorizationDomain|) + (|EuclideanDomain|) + (|OrderedIntegralDomain|) + (|DifferentialRing|) + (|ConvertibleTo| (QUOTE #1#)) + (|RetractableTo| (QUOTE #2#)) + (|LinearlyExplicitRingOver| (QUOTE #3#)) + (|ConvertibleTo| (QUOTE #4#)) + (|ConvertibleTo| (QUOTE #5#)) + (|PatternMatchable| (QUOTE #6#)) + (|CombinatorialFunctionCategory|) + (|RealConstant|) + (|CharacteristicZero|) + (|StepThrough|) + (|mkCategory| + (QUOTE |domain|) + (QUOTE ( + ((|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))) + (QUOTE ((|multiplicativeValuation| T) (|canonicalUnitNormal| T))) + (QUOTE ((|Fraction| (|Integer|)) (|Boolean|))) NIL))) + |IntegerNumberSystem|) + (SETELT #0# 0 (QUOTE (|IntegerNumberSystem|))))))) + +(MAKEPROP (QUOTE |IntegerNumberSystem|) (QUOTE 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. +<>= + +(/VERSIONCHECK 2) + +(PUT + (QUOTE |INS-;characteristic;Nni;1|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM NIL 0))) + +(DEFUN |INS-;characteristic;Nni;1| ($) 0) + +(DEFUN |INS-;differentiate;2S;2| (|x| $) + (|spadConstant| $ 9)) + +(DEFUN |INS-;even?;SB;3| (|x| $) + (COND + ((SPADCALL |x| (QREFELT $ 12)) (QUOTE NIL)) + ((QUOTE T) (QUOTE T)))) + +(DEFUN |INS-;positive?;SB;4| (|x| $) + (SPADCALL (|spadConstant| $ 9) |x| (QREFELT $ 14))) + +(PUT + (QUOTE |INS-;copy;2S;5|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM (|x|) |x|))) + +(DEFUN |INS-;copy;2S;5| (|x| $) |x|) + +(DEFUN |INS-;bit?;2SB;6| (|x| |i| $) + (SPADCALL + (SPADCALL |x| + (SPADCALL |i| (QREFELT $ 17)) + (QREFELT $ 18)) + (QREFELT $ 12))) + +(DEFUN |INS-;mask;2S;7| (|n| $) + (SPADCALL + (SPADCALL (|spadConstant| $ 20) |n| (QREFELT $ 18)) + (QREFELT $ 21))) + +(PUT + (QUOTE |INS-;rational?;SB;8|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM (|x|) (QUOTE T)))) + +(DEFUN |INS-;rational?;SB;8| (|x| $) + (QUOTE T)) + +(DEFUN |INS-;euclideanSize;SNni;9| (|x| $) + (PROG (#0=#:G1078 #1=#:G1079) + (RETURN + (COND + ((SPADCALL |x| (|spadConstant| $ 9) (QREFELT $ 24)) + (|error| "euclideanSize called on zero")) + ((SPADCALL |x| (|spadConstant| $ 9) (QREFELT $ 14)) + (PROG1 + (LETT #0# + (- (SPADCALL |x| (QREFELT $ 26))) + |INS-;euclideanSize;SNni;9|) + (|check-subtype| + (>= #0# 0) + (QUOTE (|NonNegativeInteger|)) + #0#))) + ((QUOTE T) + (PROG1 + (LETT #1# + (SPADCALL |x| (QREFELT $ 26)) + |INS-;euclideanSize;SNni;9|) + (|check-subtype| + (>= #1# 0) + (QUOTE (|NonNegativeInteger|)) + #1#))))))) + +(DEFUN |INS-;convert;SF;10| (|x| $) + (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 29))) + +(DEFUN |INS-;convert;SDf;11| (|x| $) + (FLOAT (SPADCALL |x| (QREFELT $ 26)) MOST-POSITIVE-LONG-FLOAT)) + +(DEFUN |INS-;convert;SIf;12| (|x| $) + (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 34))) + +(DEFUN |INS-;retract;SI;13| (|x| $) + (SPADCALL |x| (QREFELT $ 26))) + +(DEFUN |INS-;convert;SP;14| (|x| $) + (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 38))) + +(DEFUN |INS-;factor;SF;15| (|x| $) + (SPADCALL |x| (QREFELT $ 42))) + +(DEFUN |INS-;squareFree;SF;16| (|x| $) + (SPADCALL |x| (QREFELT $ 45))) + +(DEFUN |INS-;prime?;SB;17| (|x| $) + (SPADCALL |x| (QREFELT $ 48))) + +(DEFUN |INS-;factorial;2S;18| (|x| $) + (SPADCALL |x| (QREFELT $ 51))) + +(DEFUN |INS-;binomial;3S;19| (|n| |m| $) + (SPADCALL |n| |m| (QREFELT $ 53))) + +(DEFUN |INS-;permutation;3S;20| (|n| |m| $) + (SPADCALL |n| |m| (QREFELT $ 55))) + +(DEFUN |INS-;retractIfCan;SU;21| (|x| $) + (CONS 0 (SPADCALL |x| (QREFELT $ 26)))) + +(DEFUN |INS-;init;S;22| ($) + (|spadConstant| $ 9)) + +(DEFUN |INS-;nextItem;SU;23| (|n| $) + (COND + ((SPADCALL |n| (QREFELT $ 60)) + (CONS 0 (|spadConstant| $ 20))) + ((SPADCALL (|spadConstant| $ 9) |n| (QREFELT $ 14)) + (CONS 0 (SPADCALL |n| (QREFELT $ 17)))) + ((QUOTE T) + (CONS 0 (SPADCALL (|spadConstant| $ 20) |n| (QREFELT $ 61)))))) + +(DEFUN |INS-;patternMatch;SP2Pmr;24| (|x| |p| |l| $) + (SPADCALL |x| |p| |l| (QREFELT $ 66))) + +(DEFUN |INS-;rational;SF;25| (|x| $) + (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 70))) + +(DEFUN |INS-;rationalIfCan;SU;26| (|x| $) + (CONS 0 (SPADCALL (SPADCALL |x| (QREFELT $ 26)) (QREFELT $ 70)))) + +(DEFUN |INS-;symmetricRemainder;3S;27| (|x| |n| $) + (PROG (|r|) + (RETURN + (SEQ + (LETT |r| + (SPADCALL |x| |n| (QREFELT $ 74)) + |INS-;symmetricRemainder;3S;27|) + (EXIT + (COND + ((SPADCALL |r| (|spadConstant| $ 9) (QREFELT $ 24)) |r|) + ((QUOTE T) + (SEQ + (COND + ((SPADCALL |n| (|spadConstant| $ 9) (QREFELT $ 14)) + (LETT |n| + (SPADCALL |n| (QREFELT $ 17)) + |INS-;symmetricRemainder;3S;27|))) + (EXIT + (COND + ((SPADCALL (|spadConstant| $ 9) |r| (QREFELT $ 14)) + (COND + ((SPADCALL |n| + (SPADCALL 2 |r| (QREFELT $ 76)) + (QREFELT $ 14)) + (SPADCALL |r| |n| (QREFELT $ 61))) + ((QUOTE T) |r|))) + ((NULL + (SPADCALL + (|spadConstant| $ 9) + (SPADCALL + (SPADCALL 2 |r| (QREFELT $ 76)) + |n| + (QREFELT $ 77)) + (QREFELT $ 14))) + (SPADCALL |r| |n| (QREFELT $ 77))) + ((QUOTE T) |r|))))))))))) + +(DEFUN |INS-;invmod;3S;28| (|a| |b| $) + (PROG (|q| |r| |r1| |c| |c1| |d| |d1|) + (RETURN + (SEQ + (COND + ((SPADCALL |a| (QREFELT $ 79)) + (LETT |a| (SPADCALL |a| |b| (QREFELT $ 80)) |INS-;invmod;3S;28|))) + (LETT |c| |a| |INS-;invmod;3S;28|) + (LETT |c1| (|spadConstant| $ 20) |INS-;invmod;3S;28|) + (LETT |d| |b| |INS-;invmod;3S;28|) + (LETT |d1| (|spadConstant| $ 9) |INS-;invmod;3S;28|) + (SEQ G190 + (COND + ((NULL + (COND + ((SPADCALL |d| (QREFELT $ 60)) (QUOTE NIL)) + ((QUOTE T) (QUOTE T)))) + (GO G191))) + (SEQ + (LETT |q| (SPADCALL |c| |d| (QREFELT $ 81)) |INS-;invmod;3S;28|) + (LETT |r| + (SPADCALL |c| (SPADCALL |q| |d| (QREFELT $ 82)) (QREFELT $ 61)) + |INS-;invmod;3S;28|) + (LETT |r1| + (SPADCALL |c1| (SPADCALL |q| |d1| (QREFELT $ 82)) (QREFELT $ 61)) + |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)) + (COND + ((NULL (SPADCALL |c| (QREFELT $ 83))) + (EXIT (|error| "inverse does not exist")))) + (EXIT + (COND + ((SPADCALL |c1| (QREFELT $ 79)) (SPADCALL |c1| |b| (QREFELT $ 77))) + ((QUOTE T) |c1|))))))) + +(DEFUN |INS-;powmod;4S;29| (|x| |n| |p| $) + (PROG (|y| #0=#:G1137 |z|) + (RETURN + (SEQ + (EXIT + (SEQ + (COND + ((SPADCALL |x| (QREFELT $ 79)) + (LETT |x| + (SPADCALL |x| |p| (QREFELT $ 80)) + |INS-;powmod;4S;29|))) + (EXIT + (COND + ((SPADCALL |x| (QREFELT $ 60)) (|spadConstant| $ 9)) + ((SPADCALL |n| (QREFELT $ 60)) (|spadConstant| $ 20)) + ((QUOTE T) + (SEQ + (LETT |y| (|spadConstant| $ 20) |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| $ 20) + (QREFELT $ 17)) + (QREFELT $ 18)) + |INS-;powmod;4S;29|) + (QREFELT $ 60)) + (PROGN + (LETT #0# |y| |INS-;powmod;4S;29|) + (GO #0#))) + ((QUOTE 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 (QUOTE |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 + (QUOTE |IntegerNumberSystem&|) + (QUOTE |infovec|) + (LIST + (QUOTE + #(NIL NIL NIL NIL NIL NIL + (|local| |#1|) + (|NonNegativeInteger|) + |INS-;characteristic;Nni;1| + (0 . |Zero|) + |INS-;differentiate;2S;2| + (|Boolean|) + (4 . |odd?|) + |INS-;even?;SB;3| + (9 . <) + |INS-;positive?;SB;4| + |INS-;copy;2S;5| + (15 . -) + (20 . |shift|) + |INS-;bit?;2SB;6| + (26 . |One|) + (30 . |dec|) + |INS-;mask;2S;7| + |INS-;rational?;SB;8| + (35 . =) + (|Integer|) + (41 . |convert|) + |INS-;euclideanSize;SNni;9| + (|Float|) + (46 . |coerce|) + |INS-;convert;SF;10| + (|DoubleFloat|) + |INS-;convert;SDf;11| + (|InputForm|) + (51 . |convert|) + |INS-;convert;SIf;12| + |INS-;retract;SI;13| + (|Pattern| 25) + (56 . |coerce|) + |INS-;convert;SP;14| + (|Factored| 6) + (|IntegerFactorizationPackage| 6) + (61 . |factor|) + (|Factored| $) + |INS-;factor;SF;15| + (66 . |squareFree|) + |INS-;squareFree;SF;16| + (|IntegerPrimesPackage| 6) + (71 . |prime?|) + |INS-;prime?;SB;17| + (|IntegerCombinatoricFunctions| 6) + (76 . |factorial|) + |INS-;factorial;2S;18| + (81 . |binomial|) + |INS-;binomial;3S;19| + (87 . |permutation|) + |INS-;permutation;3S;20| + (|Union| 25 (QUOTE "failed")) + |INS-;retractIfCan;SU;21| + |INS-;init;S;22| + (93 . |zero?|) + (98 . -) + (|Union| $ (QUOTE "failed")) + |INS-;nextItem;SU;23| + (|PatternMatchResult| 25 6) + (|PatternMatchIntegerNumberSystem| 6) + (104 . |patternMatch|) + (|PatternMatchResult| 25 $) + |INS-;patternMatch;SP2Pmr;24| + (|Fraction| 25) + (111 . |coerce|) + |INS-;rational;SF;25| + (|Union| 69 (QUOTE "failed")) + |INS-;rationalIfCan;SU;26| + (116 . |rem|) + (|PositiveInteger|) + (122 . *) + (128 . +) + |INS-;symmetricRemainder;3S;27| + (134 . |negative?|) + (139 . |positiveRemainder|) + (145 . |quo|) + (151 . *) + (157 . |one?|) + |INS-;invmod;3S;28| + (162 . |mulmod|) + |INS-;powmod;4S;29|)) + (QUOTE + #(|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)) + (QUOTE NIL) + (CONS + (|makeByteWordVec2| 1 (QUOTE NIL)) + (CONS + (QUOTE #()) + (CONS + (QUOTE #()) + (|makeByteWordVec2| 86 + (QUOTE + (0 6 0 9 1 6 11 0 12 2 6 11 0 0 14 1 6 0 0 17 2 6 0 0 0 18 0 6 + 0 20 1 6 0 0 21 2 6 11 0 0 24 1 6 25 0 26 1 28 0 25 29 1 33 0 + 25 34 1 37 0 25 38 1 41 40 6 42 1 41 40 6 45 1 47 11 6 48 1 50 + 6 6 51 2 50 6 6 6 53 2 50 6 6 6 55 1 6 11 0 60 2 6 0 0 0 61 3 + 65 64 6 37 64 66 1 69 0 25 70 2 6 0 0 0 74 2 6 0 75 0 76 2 6 0 + 0 0 77 1 6 11 0 79 2 6 0 0 0 80 2 6 0 0 0 81 2 6 0 0 0 82 1 6 + 11 0 83 3 6 0 0 0 0 85 2 0 0 0 0 78 1 0 43 0 46 1 0 57 0 58 1 + 0 25 0 36 1 0 72 0 73 1 0 11 0 23 1 0 69 0 71 1 0 11 0 49 3 0 + 0 0 0 0 86 1 0 11 0 15 2 0 0 0 0 56 3 0 67 0 37 67 68 1 0 62 + 0 63 1 0 0 0 22 2 0 0 0 0 84 0 0 0 59 1 0 0 0 52 1 0 43 0 44 + 1 0 11 0 13 1 0 7 0 27 1 0 0 0 10 1 0 0 0 16 1 0 31 0 32 1 0 + 28 0 30 1 0 37 0 39 1 0 33 0 35 0 0 7 8 2 0 11 0 0 19 2 0 0 + 0 0 54)))))) + (QUOTE |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. +<>= +)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} +<>= + +(/VERSIONCHECK 2) + +(DEFUN |SINT;writeOMSingleInt| (|dev| |x| $) + (SEQ + (COND + ((QSLESSP |x| 0) + (SEQ + (SPADCALL |dev| (QREFELT $ 9)) + (SPADCALL |dev| "arith1" "unaryminus" (QREFELT $ 11)) + (SPADCALL |dev| (QSMINUS |x|) (QREFELT $ 13)) + (EXIT (SPADCALL |dev| (QREFELT $ 14))))) + ((QUOTE T) (SPADCALL |dev| |x| (QREFELT $ 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 (QREFELT $ 16)) (QREFELT $ 17)) + |SINT;OMwrite;$S;2|) + (SPADCALL |dev| (QREFELT $ 18)) + (|SINT;writeOMSingleInt| |dev| |x| $) + (SPADCALL |dev| (QREFELT $ 19)) + (SPADCALL |dev| (QREFELT $ 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 (QREFELT $ 16)) (QREFELT $ 17)) + |SINT;OMwrite;$BS;3|) + (COND (|wholeObj| (SPADCALL |dev| (QREFELT $ 18)))) + (|SINT;writeOMSingleInt| |dev| |x| $) + (COND (|wholeObj| (SPADCALL |dev| (QREFELT $ 19)))) + (SPADCALL |dev| (QREFELT $ 20)) + (LETT |s| (OM-STRINGPTRTOSTRING |sp|) |SINT;OMwrite;$BS;3|) + (EXIT |s|))))) + +(DEFUN |SINT;OMwrite;Omd$V;4| (|dev| |x| $) + (SEQ + (SPADCALL |dev| (QREFELT $ 18)) + (|SINT;writeOMSingleInt| |dev| |x| $) + (EXIT (SPADCALL |dev| (QREFELT $ 19))))) + +(DEFUN |SINT;OMwrite;Omd$BV;5| (|dev| |x| |wholeObj| $) + (SEQ + (COND (|wholeObj| (SPADCALL |dev| (QREFELT $ 18)))) + (|SINT;writeOMSingleInt| |dev| |x| $) + (EXIT (COND (|wholeObj| (SPADCALL |dev| (QREFELT $ 19))))))) + +(PUT + (QUOTE |SINT;reducedSystem;MM;6|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM (|m|) |m|))) + +(DEFUN |SINT;reducedSystem;MM;6| (|m| $) |m|) + +(DEFUN |SINT;coerce;$Of;7| (|x| $) + (SPADCALL |x| (QREFELT $ 30))) + +(PUT + (QUOTE |SINT;convert;$I;8|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM (|x|) |x|))) + +(DEFUN |SINT;convert;$I;8| (|x| $) |x|) + +(DEFUN |SINT;*;I2$;9| (|i| |y| $) + (QSTIMES (SPADCALL |i| (QREFELT $ 33)) |y|)) + +(PUT + (QUOTE |SINT;Zero;$;10|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM NIL 0))) + +(DEFUN |SINT;Zero;$;10| ($) 0) + +(PUT + (QUOTE |SINT;One;$;11|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM NIL 1))) + +(DEFUN |SINT;One;$;11| ($) 1) + +(PUT + (QUOTE |SINT;base;$;12|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM NIL 2))) + +(DEFUN |SINT;base;$;12| ($) 2) + +(PUT + (QUOTE |SINT;max;$;13|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM NIL MOST-POSITIVE-FIXNUM))) + +(DEFUN |SINT;max;$;13| ($) MOST-POSITIVE-FIXNUM) + +(PUT + (QUOTE |SINT;min;$;14|) + (QUOTE |SPADreplace|) + (QUOTE (XLAM NIL MOST-NEGATIVE-FIXNUM))) + +(DEFUN |SINT;min;$;14| ($) MOST-NEGATIVE-FIXNUM) + +(PUT + (QUOTE |SINT;=;2$B;15|) + (QUOTE |SPADreplace|) + (QUOTE EQL)) + +(DEFUN |SINT;=;2$B;15| (|x| |y| $) + (EQL |x| |y|)) + +(PUT + (QUOTE |SINT;~;2$;16|) + (QUOTE |SPADreplace|) + (QUOTE LOGNOT)) + +(DEFUN |SINT;~;2$;16| (|x| $) + (LOGNOT |x|)) + +(PUT + (QUOTE |SINT;not;2$;17|) + (QUOTE |SPADreplace|) + (QUOTE LOGNOT)) + +(DEFUN |SINT;not;2$;17| (|x| $) + (LOGNOT |x|)) + +(PUT + (QUOTE |SINT;/\\;3$;18|) + (QUOTE |SPADreplace|) + (QUOTE LOGAND)) + +(DEFUN |SINT;/\\;3$;18| (|x| |y| $) + (LOGAND |x| |y|)) + +(PUT + (QUOTE |SINT;\\/;3$;19|) + (QUOTE |SPADreplace|) + (QUOTE LOGIOR)) + +(DEFUN |SINT;\\/;3$;19| (|x| |y| $) + (LOGIOR |x| |y|)) + +(PUT + (QUOTE |SINT;Not;2$;20|) + (QUOTE |SPADreplace|) + (QUOTE LOGNOT)) + +(DEFUN |SINT;Not;2$;20| (|x| $) + (LOGNOT |x|)) + +(PUT + (QUOTE |SINT;And;3$;21|) + (QUOTE |SPADreplace|) + (QUOTE LOGAND)) + +(DEFUN |SINT;And;3$;21| (|x| |y| $) + (LOGAND |x| |y|)) + +(PUT + (QUOTE |SINT;Or;3$;22|) + (QUOTE |SPADreplace|) + (QUOTE LOGIOR)) + +(DEFUN |SINT;Or;3$;22| (|x| |y| $) + (LOGIOR |x| |y|)) + +(PUT + (QUOTE |SINT;xor;3$;23|) + (QUOTE |SPADreplace|) + (QUOTE LOGXOR)) + +(DEFUN |SINT;xor;3$;23| (|x| |y| $) + (LOGXOR |x| |y|)) + +(PUT + (QUOTE |SINT;<;2$B;24|) + (QUOTE |SPADreplace|) + (QUOTE QSLESSP)) + +(DEFUN |SINT;<;2$B;24| (|x| |y| $) + (QSLESSP |x| |y|)) + +(PUT + (QUOTE |SINT;inc;2$;25|) + (QUOTE |SPADreplace|) + (QUOTE QSADD1)) + +(DEFUN |SINT;inc;2$;25| (|x| $) + (QSADD1 |x|)) + +(PUT + (QUOTE |SINT;dec;2$;26|) + (QUOTE |SPADreplace|) + (QUOTE QSSUB1)) + +(DEFUN |SINT;dec;2$;26| (|x| $) + (QSSUB1 |x|)) + +(PUT + (QUOTE |SINT;-;2$;27|) + (QUOTE |SPADreplace|) + (QUOTE QSMINUS)) + +(DEFUN |SINT;-;2$;27| (|x| $) + (QSMINUS |x|)) + +(PUT + (QUOTE |SINT;+;3$;28|) + (QUOTE |SPADreplace|) + (QUOTE QSPLUS)) + +(DEFUN |SINT;+;3$;28| (|x| |y| $) + (QSPLUS |x| |y|)) + +(PUT + (QUOTE |SINT;-;3$;29|) + (QUOTE |SPADreplace|) + (QUOTE QSDIFFERENCE)) + +(DEFUN |SINT;-;3$;29| (|x| |y| $) + (QSDIFFERENCE |x| |y|)) + +(PUT + (QUOTE |SINT;*;3$;30|) + (QUOTE |SPADreplace|) + (QUOTE QSTIMES)) + +(DEFUN |SINT;*;3$;30| (|x| |y| $) + (QSTIMES |x| |y|)) + +(DEFUN |SINT;**;$Nni$;31| (|x| |n| $) + (SPADCALL (EXPT |x| |n|) (QREFELT $ 33))) + +(PUT + (QUOTE |SINT;quo;3$;32|) + (QUOTE |SPADreplace|) + (QUOTE QSQUOTIENT)) + +(DEFUN |SINT;quo;3$;32| (|x| |y| $) + (QSQUOTIENT |x| |y|)) + +(PUT + (QUOTE |SINT;rem;3$;33|) + (QUOTE |SPADreplace|) + (QUOTE 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 (QUOTE |SINT;gcd;3$;35|) + (QUOTE |SPADreplace|) (QUOTE GCD)) + +(DEFUN |SINT;gcd;3$;35| (|x| |y| $) + (GCD |x| |y|)) + +(PUT + (QUOTE |SINT;abs;2$;36|) + (QUOTE |SPADreplace|) + (QUOTE QSABSVAL)) + +(DEFUN |SINT;abs;2$;36| (|x| $) + (QSABSVAL |x|)) + +(PUT + (QUOTE |SINT;odd?;$B;37|) + (QUOTE |SPADreplace|) + (QUOTE QSODDP)) + +(DEFUN |SINT;odd?;$B;37| (|x| $) + (QSODDP |x|)) + +(PUT + (QUOTE |SINT;zero?;$B;38|) + (QUOTE |SPADreplace|) + (QUOTE QSZEROP)) + +(DEFUN |SINT;zero?;$B;38| (|x| $) + (QSZEROP |x|)) + +(PUT + (QUOTE |SINT;max;3$;39|) + (QUOTE |SPADreplace|) + (QUOTE QSMAX)) + +(DEFUN |SINT;max;3$;39| (|x| |y| $) + (QSMAX |x| |y|)) + +(PUT + (QUOTE |SINT;min;3$;40|) + (QUOTE |SPADreplace|) + (QUOTE QSMIN)) + +(DEFUN |SINT;min;3$;40| (|x| |y| $) + (QSMIN |x| |y|)) + +(PUT + (QUOTE |SINT;hash;2$;41|) + (QUOTE |SPADreplace|) + (QUOTE HASHEQ)) + +(DEFUN |SINT;hash;2$;41| (|x| $) + (HASHEQ |x|)) + +(PUT + (QUOTE |SINT;length;2$;42|) + (QUOTE |SPADreplace|) + (QUOTE INTEGER-LENGTH)) + +(DEFUN |SINT;length;2$;42| (|x| $) + (INTEGER-LENGTH |x|)) + +(PUT + (QUOTE |SINT;shift;3$;43|) + (QUOTE |SPADreplace|) + (QUOTE QSLEFTSHIFT)) + +(DEFUN |SINT;shift;3$;43| (|x| |n| $) + (QSLEFTSHIFT |x| |n|)) + +(PUT + (QUOTE |SINT;mulmod;4$;44|) + (QUOTE |SPADreplace|) + (QUOTE QSMULTMOD)) + +(DEFUN |SINT;mulmod;4$;44| (|a| |b| |p| $) + (QSMULTMOD |a| |b| |p|)) + +(PUT + (QUOTE |SINT;addmod;4$;45|) + (QUOTE |SPADreplace|) + (QUOTE QSADDMOD)) + +(DEFUN |SINT;addmod;4$;45| (|a| |b| |p| $) + (QSADDMOD |a| |b| |p|)) + +(PUT + (QUOTE |SINT;submod;4$;46|) + (QUOTE |SPADreplace|) + (QUOTE QSDIFMOD)) + +(DEFUN |SINT;submod;4$;46| (|a| |b| |p| $) + (QSDIFMOD |a| |b| |p|)) + +(PUT + (QUOTE |SINT;negative?;$B;47|) + (QUOTE |SPADreplace|) + (QUOTE QSMINUSP)) + +(DEFUN |SINT;negative?;$B;47| (|x| $) + (QSMINUSP |x|)) + +(PUT + (QUOTE |SINT;reducedSystem;MVR;48|) + (QUOTE |SPADreplace|) + (QUOTE CONS)) + +(DEFUN |SINT;reducedSystem;MVR;48| (|m| |v| $) + (CONS |m| |v|)) + +(DEFUN |SINT;positiveRemainder;3$;49| (|x| |n| $) + (PROG (|r|) + (RETURN + (SEQ + (LETT |r| (QSREMAINDER |x| |n|) |SINT;positiveRemainder;3$;49|) + (EXIT + (COND + ((QSMINUSP |r|) + (COND + ((QSMINUSP |n|) (QSDIFFERENCE |x| |n|)) + ((QUOTE T) (QSPLUS |r| |n|)))) + ((QUOTE T) |r|))))))) + +(DEFUN |SINT;coerce;I$;50| (|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;$;51| ($) + (SEQ + (SETELT $ 6 (REMAINDER (TIMES 314159269 (QREFELT $ 6)) 2147483647)) + (EXIT (REMAINDER (QREFELT $ 6) 67108864)))) + +(PUT + (QUOTE |SINT;random;2$;52|) + (QUOTE |SPADreplace|) + (QUOTE RANDOM)) + +(DEFUN |SINT;random;2$;52| (|n| $) + (RANDOM |n|)) + +(DEFUN |SINT;unitNormal;$R;53| (|x| $) + (COND + ((QSLESSP |x| 0) (VECTOR -1 (QSMINUS |x|) -1)) + ((QUOTE T) (VECTOR 1 |x| 1)))) + +(DEFUN |SingleInteger| NIL + (PROG NIL + (RETURN + (PROG (#0=#:G1358) + (RETURN + (COND + ((LETT #0# + (HGET |$ConstructorCache| (QUOTE |SingleInteger|)) + |SingleInteger|) + (|CDRwithIncrement| (CDAR #0#))) + ((QUOTE T) + (UNWIND-PROTECT + (PROG1 + (CDDAR + (HPUT + |$ConstructorCache| + (QUOTE |SingleInteger|) + (LIST (CONS NIL (CONS 1 (|SingleInteger;|)))))) + (LETT #0# T |SingleInteger|)) + (COND + ((NOT #0#) + (HREM |$ConstructorCache| + (QUOTE |SingleInteger|)))))))))))) + +(DEFUN |SingleInteger;| NIL + (PROG (|dv$| $ |pv$|) + (RETURN + (PROGN + (LETT |dv$| (QUOTE (|SingleInteger|)) . #0=(|SingleInteger|)) + (LETT $ (GETREFV 103) . #0#) + (QSETREFV $ 0 |dv$|) + (QSETREFV $ 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#)) + (|haddProp| |$ConstructorCache| (QUOTE |SingleInteger|) NIL (CONS 1 $)) + (|stuffDomainSlots| $) (QSETREFV $ 6 1) $)))) + +(MAKEPROP + (QUOTE |SingleInteger|) + (QUOTE |infovec|) + (LIST + (QUOTE + #(NIL NIL NIL NIL NIL NIL + (QUOTE |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;max;3$;39| + |SINT;min;3$;40| + |SINT;hash;2$;41| + |SINT;length;2$;42| + |SINT;shift;3$;43| + |SINT;mulmod;4$;44| + |SINT;addmod;4$;45| + |SINT;submod;4$;46| + |SINT;negative?;$B;47| + (|Record| (|:| |mat| 26) (|:| |vec| (|Vector| 12))) + (|Vector| $) + |SINT;reducedSystem;MVR;48| + |SINT;positiveRemainder;3$;49| + |SINT;coerce;I$;50| + |SINT;random;$;51| + |SINT;random;2$;52| + (|Record| (|:| |unit| $) (|:| |canonical| $) (|:| |associate| $)) + |SINT;unitNormal;$R;53| + (|Union| 85 (QUOTE "failed")) + (|Fraction| 12) + (|Union| $ (QUOTE "failed")) + (|Float|) + (|DoubleFloat|) + (|Pattern| 12) + (|PatternMatchResult| 12 $) + (|InputForm|) + (|Union| 12 (QUOTE "failed")) + (|Record| (|:| |coef| 94) (|:| |generator| $)) + (|List| $) + (|Union| 94 (QUOTE "failed")) + (|Record| (|:| |coef1| $) (|:| |coef2| $) (|:| |generator| $)) + (|Record| (|:| |coef1| $) (|:| |coef2| $)) + (|Union| 97 (QUOTE "failed")) + (|Factored| $) + (|SparseUnivariatePolynomial| $) + (|PositiveInteger|) + (|SingleInteger|))) + (QUOTE + #(~= 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)) + (QUOTE ( + (|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 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&| |Module&| NIL |Module&| NIL NIL + |Module&| NIL |DifferentialRing&| |OrderedRing&| NIL |Module&| + NIL |Module&| NIL NIL NIL NIL NIL NIL |Ring&| NIL NIL NIL NIL + NIL NIL NIL NIL NIL NIL NIL NIL NIL |AbelianGroup&| NIL NIL + |AbelianMonoid&| |Monoid&| NIL NIL NIL NIL |OrderedSet&| + |AbelianSemiGroup&| |SemiGroup&| |Logic&| NIL |SetCategory&| NIL + NIL NIL NIL |RetractableTo&| NIL NIL NIL |RetractableTo&| NIL NIL + NIL NIL NIL NIL |RetractableTo&| NIL |BasicType&| NIL)) + (CONS + (QUOTE + #((|IntegerNumberSystem|) (|EuclideanDomain|) + (|UniqueFactorizationDomain|) (|PrincipalIdealDomain|) + (|OrderedIntegralDomain|) (|GcdDomain|) (|IntegralDomain|) + (|Algebra| $$) (|Module| 12) (|LinearlyExplicitRingOver| 12) + (|Module| #0=#:G1062) (|LinearlyExplicitRingOver| #0#) + (|CharacteristicZero|) (|Module| #1=#:G106217) + (|LinearlyExplicitRingOver| #1#) (|DifferentialRing|) + (|OrderedRing|) (|CommutativeRing|) (|Module| |t#1|) + (|EntireRing|) (|Module| $$) (|BiModule| 12 12) + (|BiModule| #0# #0#) (|BiModule| #1# #1#) + (|OrderedAbelianGroup|) (|BiModule| |t#1| |t#1|) + (|BiModule| $$ $$) (|Ring|) (|RightModule| 12) + (|LeftModule| 12) (|RightModule| #0#) (|LeftModule| #0#) + (|RightModule| #1#) (|LeftModule| #1#) + (|OrderedCancellationAbelianMonoid|) (|RightModule| |t#1|) + (|LeftModule| |t#1|) (|LeftModule| $$) (|Rng|) + (|RightModule| $$) (|OrderedAbelianMonoid|) (|AbelianGroup|) + (|OrderedAbelianSemiGroup|) (|CancellationAbelianMonoid|) + (|AbelianMonoid|) (|Monoid|) (|PatternMatchable| 12) + (|PatternMatchable| #:G1065) (|StepThrough|) + (|PatternMatchable| #:G106220) (|OrderedSet|) + (|AbelianSemiGroup|) (|SemiGroup|) (|Logic|) (|RealConstant|) + (|SetCategory|) (|OpenMath|) (|CoercibleTo| #:G82356) + (|ConvertibleTo| 89) (|ConvertibleTo| 91) (|RetractableTo| 12) + (|ConvertibleTo| 12) (|ConvertibleTo| #:G1064) + (|ConvertibleTo| #:G1063) (|RetractableTo| #:G1061) + (|ConvertibleTo| #:G1060) (|ConvertibleTo| 87) + (|ConvertibleTo| 88) (|CombinatorialFunctionCategory|) + (|ConvertibleTo| #:G106219) (|ConvertibleTo| #:G106218) + (|RetractableTo| #:G106216) (|ConvertibleTo| #:G106215) + (|BasicType|) (|CoercibleTo| 29))) + (|makeByteWordVec2| 102 + (QUOTE + (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 82 0 83 1 0 0 0 1 1 0 22 0 1 2 0 0 0 0 1 2 0 86 + 0 0 1 3 0 0 0 0 0 73 1 0 0 0 1 1 0 99 0 1 2 0 22 0 0 1 1 0 + 12 0 1 2 0 0 0 0 70 0 0 0 1 1 0 92 0 1 1 0 12 0 1 2 0 0 0 0 + 59 1 0 26 27 28 2 0 75 27 76 77 1 0 86 0 1 1 0 84 0 1 1 0 + 22 0 1 1 0 85 0 1 1 0 0 0 81 0 0 0 80 2 0 0 0 0 58 1 0 93 + 94 1 1 0 22 0 1 3 0 0 0 0 0 1 2 0 0 0 0 78 1 0 22 0 1 2 0 0 + 0 0 1 3 0 90 0 89 90 1 1 0 22 0 1 1 0 22 0 64 1 0 0 0 42 1 + 0 86 0 1 1 0 22 0 74 2 0 95 94 0 1 3 0 0 0 0 0 71 0 0 0 39 + 2 0 0 0 0 67 0 0 0 38 2 0 0 0 0 66 1 0 0 0 1 1 0 0 0 69 1 0 + 0 94 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 68 1 0 102 0 1 2 0 100 100 100 1 1 0 0 94 1 2 0 0 0 + 0 62 1 0 0 0 1 1 0 99 0 1 2 0 96 0 0 1 3 0 98 0 0 0 1 2 0 86 + 0 0 1 2 0 95 94 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 87 0 1 1 0 88 0 + 1 1 0 89 0 1 1 0 91 0 1 1 0 12 0 32 1 0 0 12 79 1 0 0 0 1 1 + 0 0 12 79 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 72 1 0 0 0 63 2 0 0 0 56 1 2 0 + 0 0 101 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 101 1 + 2 0 0 0 0 55 2 0 0 12 0 34 2 0 0 56 0 1 2 0 0 101 0 1)))))) + (QUOTE |lookupComplete|))) + +(MAKEPROP (QUOTE |SingleInteger|) (QUOTE NILADIC) T) + +@ +\section{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. +@ +<<*>>= +<> + +<> +<> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} -- cgit v1.2.3