DIRECTORY Basics USING [Comparison], Rope USING [ROPE]; BigCardinals: CEDAR DEFINITIONS = BEGIN BigCARD: TYPE = RECORD [size: NAT ¬ 0, contents: REF BigCARDRec ¬ NIL]; BigCARDRec: TYPE = RECORD [PACKED SEQUENCE max: NAT OF CARD16]; Zero: BigCARD = [0, NIL]; BigFail: ERROR [subclass: ATOM ¬ $Unspecified]; BigAdd: PROC [in1, in2: BigCARD] RETURNS [BigCARD]; BigSubtract: PROC [large, small: BigCARD, reuse: BOOL ¬ FALSE] RETURNS [BigCARD]; BigMultiply: PROC [in1, in2: BigCARD] RETURNS [BigCARD]; BigDivMod: PROC [num, den: BigCARD, reuse: BOOL ¬ FALSE] RETURNS [quo, rem: BigCARD]; BigFromDecimalRope: PROC [in: Rope.ROPE] RETURNS [BigCARD]; BigToDecimalRope: PROC [in: BigCARD, reuse: BOOL ¬ FALSE] RETURNS [Rope.ROPE]; BigFromBinaryRope: PROC [in: Rope.ROPE] RETURNS [BigCARD]; BigToBinaryRope: PROC [in: BigCARD] RETURNS [Rope.ROPE]; BigFromRope: PROC[in: Rope.ROPE] RETURNS [out: BigCARD]; BigToRope: PROC [in: BigCARD] RETURNS [out: Rope.ROPE]; BigFromSmall: PROC [in: CARD16] RETURNS [BigCARD]; BigToSmall: PROC [in: BigCARD] RETURNS [CARD16]; BigFromCard: PROC [in: CARD] RETURNS [BigCARD]; BigToCard: PROC [in: BigCARD] RETURNS [CARD]; BigCopy: PROC [in: BigCARD] RETURNS [BigCARD]; BigCompare: PROC [in1, in2: BigCARD] RETURNS [Basics.Comparison]; BigZero: PROC [in: BigCARD] RETURNS [BOOL]; BigOne: PROC [in: BigCARD] RETURNS [BOOL]; BigOdd: PROC [in: BigCARD] RETURNS [BOOL]; MultiplyByDigit: PROC [big: BigCARD, small: CARD16, reuse: BOOL ¬ FALSE] RETURNS [BigCARD]; TwoToTheNth: PROC [n: NAT] RETURNS [BigCARD]; TimesTwoToTheNth: PROC [in: BigCARD, n: NAT] RETURNS [BigCARD]; FirstOneBit: PROC [bc: BigCARD] RETURNS [INT]; LowOrderZeros: PROC [bc: BigCARD] RETURNS [INT]; BigPowerOfTen: PROC [exponent: NAT] RETURNS [BigCARD]; BigPowerOfBase: PROC [base: BigCARD, exponent: NAT] RETURNS [BigCARD]; Shift: PROC [bc: BigCARD, bits: INT] RETURNS [BigCARD]; BigToREAL: PROC [in: BigCARD] RETURNS [REAL]; BigFactorial: PROC [x: NAT] RETURNS [BigCARD]; BigRandom: PROC [length: NAT ¬ 0, max, min: BigCARD ¬ Zero] RETURNS [BigCARD]; BigExponentiate: PROC [base, exponent, modulus: BigCARD, reuse: BOOL ¬ FALSE] RETURNS [BigCARD]; BigGCD: PROC [in1, in2: BigCARD] RETURNS [out: BigCARD]; BigInverse: PROC [in, modulus: BigCARD] RETURNS [out: BigCARD]; BigPrimeTest: PROC [prime: BigCARD, accuracy: NAT ¬ 20] RETURNS [BOOL]; END. \ BigCardinals.mesa Copyright Σ 1985, 1987, 1988, 1991 by Xerox Corporation. All rights reserved. Dan Greene, March March 6, 1984 4:35:06 pm Russ Atkinson (RRA) March 26, 1987 9:05:43 pm PST Swinehart, July 5, 1985 1:38:25 pm PDT Michael Plass, April 19, 1988 10:35:48 am PDT Data Structure Big cardinals are represented in a radix of 2^16. The digits are stored as a sequence of cardinals, with the low order digit at contents[0]. Zero is represented with size = 0. Notice that the assignment of two big cardinals, a _ b, will result in their sharing a sequence of digits. Normally the procedures below treat the sequences at immutable objects, so this will never create problems, however, the `reuse' flag allows procedures to modify sequences. The proper use of the `reuse' flag can be a headache, and since garbage collection is cheap, clients are discouraged from changing the `reuse' defaults. This is always used for a big fat zero. The sublass is one of $NegativeResult, $DivideByZero, or $TooLarge, as explained below. Basic Arithmetic If `reuse' is true, `large' is used for the output. BigSubtract can raise a BigFail ERROR with $NegativeResult if `large' is not larger than `small'. If `reuse' is TRUE then `num' is used for `quo', and `den' is used for scratch operations. BigDivMod will raise a BigFail ERROR with argument $DivideByZero when den = 0. Conversion Routines There are three kinds of conversion routines between Ropes and BigCardinals. If the word Decimal appears in the name then the Ropes involved are human readable strings of the digits 0..9, that is, the standard base 10 representation of a BigCardinal. If the word Binary appears in the name then the Ropes involved are machine readable strings of the bytes 0..255, with the most significant byte in rope.Fetch[0], that is, the base 256 representation of a BigCardinal. The third kind of conversion is a bijective mapping between BigCardinals and Ropes that uses the full character set of the Rope, and so is considerably more compact than decimal, but not particularly human readable (it is used in cryptographic routines). Special care must be taken to encode Null characters in the Rope that would become leading zeros of the BigCardinal. Details can be found in the implementation. This procedure can raise a BigFail ERROR with argument $TooLarge if `in' will not fit in a single cardinal. This procedure can raise a BigFail ERROR with argument $TooLarge if `in' will not fit in a single CARD. Copy and Comparison The input is copied into a sequence with maximum size 2 larger than current size. Unless the client sets `reuse' TRUE in some other procedure, or modifies sequences directly, there should be no need for this procedure. Some frequently used tests: Test if a BigCARD is the integer one. Exotic Functions Useful for repeated multiplications by small numbers. This procedure computes 2 ^ n. This procedure computes in * 2 ^ n. Returns the largest bit position where bc has a 1 bit. Returns -1 for bc = 0, 0 for bc = 1, 1 for bc = 2 or 3, and so forth. Useful for determining an approximation to Log2[bc]. Returns the number of low-order bit positions where bc has a 0 bit. Returns -1 for bc = 0, 0 for bc odd, 1 for bc = 2, and so forth. computes Floor[bc * 2^bits] Returns the factorial of x. BigRandom returns a random number in a range that is specified by one of two means: 1) If `length' is nonzero than the result has `length' digits of radix 2^16 2) If `length' is zero than the result is in the range [min, max] This procedure computes base ^ exponent MOD modulus. When reuse is TRUE the base is destroyed. If `in' and `modulus' are relatively prime then out * in = 1 MOD modulus. In general, out * in = GCD( in, modulus ) MOD modulus. If BigPrimeTest returns FALSE then `prime' is not a prime. If BigPrimeTest returns TRUE there is a very slight chance, less than 2 ^ accuracy, that the procedure is wrong. ΚŽ•NewlineDelimiter –(cedarcode) style™codešœ™Kšœ ΟeœC™NK™*KšœΟkœ™1Kšœ#ž™&K™-—˜šž ˜ Kšœžœ˜Kšœžœžœ˜——K˜KšΟn œžœž œž˜'K˜head2šœ™Kšœ―™―K˜Kš œ žœžœžœžœžœ˜GKšœ žœžœžœžœžœžœžœ˜?K˜K™°K˜šŸœžœ˜Kšœ'™'K™—šŸœžœ žœ˜/K™W——™šŸœžœžœ ˜3K˜—š Ÿ œžœ žœžœžœ ˜QK™3Kšœ žœ<™aK˜—šŸ œžœžœ ˜8K˜—š Ÿ œžœžœžœžœ˜UKšœžœH™ZKšœžœ*™N——™šœL™LK˜—KšŸœžœ žœžœ ˜;š Ÿœžœžœžœžœžœ˜NKšœ­™­K˜—KšŸœžœ žœžœ ˜:šŸœžœžœžœ˜8KšœΨ™ΨK˜—KšŸ œžœ žœžœ˜8šŸ œžœžœ žœ˜7Kšœ‘™‘K˜—K˜KšŸ œžœžœžœ ˜2šŸ œžœžœžœ˜0Kšœ#žœC™kK™—KšŸ œžœžœžœ ˜/šŸ œžœžœžœ˜-Kšœ#žœ:žœ™g——™šŸœžœžœ ˜.K™QKšœžœe™ˆK˜—KšŸ œžœžœ˜A—™šŸœžœžœžœ˜+K˜—šŸœžœžœžœ˜*Jšœ%™%K˜—KšŸœžœžœžœ˜*—™š Ÿœžœžœ žœžœžœ ˜[K™5K˜—šŸ œžœžœžœ ˜-Kšœ™K˜—šŸœžœžœžœ ˜?Kšœ#™#K˜—šŸ œžœžœžœ˜.šœ³™³K™——šŸ œžœžœžœ˜0šœ…™…K™——šŸ œžœ žœžœ ˜6K˜—šŸœžœžœžœ ˜FK˜—šŸœžœžœžœ ˜7Jšœ™K˜—šŸ œžœžœžœ˜-K˜—šŸ œžœžœžœ ˜.K™K˜—šŸ œžœ žœ žœ ˜NK™SK™KK™A—K˜š Ÿœžœ+žœžœžœ ˜`Kšœ)žœ ™5Kšœžœ™)K™—šŸœžœžœ˜8K˜—šŸ œžœžœ˜?Kšœ>žœ ™JKšœžœžœ ™7K˜—š Ÿ œžœžœžœžœ˜GKšœžœ6žœT™«K˜——Kšžœ˜—…— <&