<<>> <> <> <> <> <> <> DIRECTORY Basics USING [CompareCard, Comparison, HighHalf, LongNumber, LowHalf], BigCardinals USING [BigCARD, BigCARDRec, Zero], Convert USING [RopeFromCard], IO USING [PutChar, RopeFromROS, ROS, STREAM], Basics16 USING [BITAND, BITNOT, BITOR, BITSHIFT, LongDiv, LongDivMod, LongMult], Random USING [ChooseInt, Create, RandomStream], Real USING [FScale], Rope USING [ActionType, Concat, Equal, Fetch, FromChar, FromProc, Map, ROPE, Size, SkipOver, Substr]; BigCardinalsImpl: CEDAR PROGRAM IMPORTS Basics, Convert, IO, Basics16, Random, Real, Rope EXPORTS BigCardinals = BEGIN OPEN BigCardinals, Basics16; Digit: TYPE = CARD16; ROPE: TYPE = Rope.ROPE; STREAM: TYPE = IO.STREAM; highBit: Digit = (LAST[Digit]-LAST[Digit]/2); lastPlus: CARD = CARD32[LAST[Digit]]+1; -- 200000B bitsPerChar: NAT = BITS[CHAR]; bitsPerDigit: NAT = BITS[Digit]; bytesPerDigit: NAT = BYTES[Digit]; useNewRopeEncoding: BOOL ¬ TRUE; <> <<>> BigFail: PUBLIC ERROR [subclass: ATOM ¬ $Unspecified] = CODE; <> CheckOp: TYPE ~ MACHINE DEPENDENT { AddDigit, BigAdd, BigDivMod, BigDivModResult, BigMultiply, BigSubtract, DivideByDigit, MulMod, MultiplyByDigit, Shift, in2 }; Check: PROC [op: CheckOp, in1, in2: BigCARD] = INLINE {}; CheckBigLittle: PROC [op: CheckOp, in1: BigCARD, in2: Digit] = INLINE {}; CheckLittle: PROC [little: Digit] = INLINE {}; CheckResult: PROC [op: CheckOp, out: BigCARD] = INLINE {}; <> BigAdd: PUBLIC PROC [in1, in2: BigCARD] RETURNS [out: BigCARD] ~ { smaller: BigCARD; addResults: CARD; carry: Digit ¬ 0; Check[$BigAdd, in1, in2]; IF in1.size < in2.size THEN {smaller ¬ in1; out ¬ in2} ELSE {smaller ¬ in2; out ¬ in1}; out ¬ BigCopy[out]; IF (out.size = 0) OR (smaller.size = 0) THEN RETURN; FOR index: NAT IN [0..smaller.size) DO addResults ¬ CARD32[out.contents[index]] + CARD32[smaller.contents[index]] + carry; out.contents[index] ¬ Basics.LowHalf[addResults]; carry ¬ Basics.HighHalf[addResults]; ENDLOOP; FOR index: NAT IN [smaller.size..out.size) DO addResults ¬ CARD32[out.contents[index]] + carry; out.contents[index] ¬ Basics.LowHalf[addResults]; carry ¬ Basics.HighHalf[addResults]; ENDLOOP; IF carry > 0 THEN { IF out.size >= out.contents.max THEN out ¬ BigCopy[out]; --Expand `out' if necessary out.contents[out.size] ¬ carry; out.size ¬ out.size + 1; }; CheckResult[$BigAdd, out]; }; BigSubtract: PUBLIC PROC [large, small: BigCARD, reuse: BOOL ¬ FALSE] RETURNS [out: BigCARD] ~ { borrow: CARD ¬ 0; subResults: CARD ¬ 0; Check[$BigSubtract, large, small]; IF large.size < small.size THEN ERROR BigFail[$NegativeResult]; IF reuse THEN out ¬ large ELSE out ¬ BigCopy[large]; <> FOR index: NAT IN [0..small.size) DO subResults ¬ CARD32[out.contents[index]] - CARD32[small.contents[index]] + borrow; out.contents[index] ¬ Basics.LowHalf[subResults]; borrow ¬ LOOPHOLE[INT32[LOOPHOLE[Basics.HighHalf[subResults], INT16]], CARD]; <> ENDLOOP; FOR index: NAT IN [small.size..out.size) DO subResults ¬ CARD32[out.contents[index]] + borrow; out.contents[index] ¬ Basics.LowHalf[subResults]; borrow ¬ LOOPHOLE[INT32[LOOPHOLE[Basics.HighHalf[subResults], INT16]], CARD]; ENDLOOP; out ¬ StripLeadingZeros[out]; CheckResult[$BigSubtract, out]; }; StripLeadingZeros: PROC [in: BigCARD] RETURNS [out: BigCARD] ~ { out ¬ in; FOR index: NAT DECREASING IN [0..in.size) DO IF out.contents[index] > 0 THEN RETURN; out.size ¬ out.size - 1; ENDLOOP; out.contents ¬ NIL; }; BigMultiply: PUBLIC PROC [in1, in2: BigCARD] RETURNS [out: BigCARD ¬ []] ~ { carry: Digit ¬ 0; Check[$BigMultiply, in1, in2]; IF in1.size = 0 OR in2.size = 0 THEN RETURN; out.size ¬ in1.size + in2.size; out.contents ¬ NEW[BigCARDRec[out.size]]; FOR index1: NAT IN [0..in1.size) DO FOR index2: NAT IN [0..in2.size) DO product: CARD ¬ LongMult[in1.contents[index1], in2.contents[index2]] + CARD32[out.contents[index1+index2]]+carry; out.contents[index1+index2] ¬ Basics.LowHalf[product]; carry ¬ Basics.HighHalf[product]; ENDLOOP; out.contents[index1+in2.size] ¬ carry; carry ¬ 0; ENDLOOP; out ¬ StripLeadingZeros[out]; CheckResult[$BigMultiply, out]; }; BigDivMod: PUBLIC PROC [num, den: BigCARD, reuse: BOOL ¬ FALSE] RETURNS [quo, rem: BigCARD] ~ { highDen, nextDen: Digit; smallNum, readyToShift: CARD; carry, subtract, borrow, multResults, subResults, addResults: CARD; normalize, remainder: Digit; oldNumSize: NAT ¬ num.size; leftShiftedDigit: Basics.LongNumber ¬ [pair[hi: 0, lo: 0]]; Check[$BigDivMod, num, den]; IF den.size=0 THEN ERROR BigFail[$DivideByZero]; IF den.size=1 THEN { [quo, remainder] ¬ DivideByDigit[num, den.contents[0], reuse]; rem ¬ BigFromSmall[remainder]; Check[$BigDivModResult, quo, rem]; RETURN; }; IF NOT reuse THEN num ¬ BigCopy[num]; IF den.size > num.size THEN {rem ¬ num; Check[$BigDivModResult, quo, rem]; RETURN}; normalize ¬ den.contents[den.size - 1]; CheckLittle[normalize]; SELECT normalize FROM 0 => ERROR; >= LAST[Digit]/2 => normalize ¬ 1; ENDCASE => { normalize ¬ LongDiv[lastPlus, normalize+1]; CheckLittle[normalize]; num ¬ MultiplyByDigit[num, normalize, TRUE]; }; IF num.size = oldNumSize THEN { IF num.size >= num.contents.max THEN num ¬ BigCopy[num]; num.contents[num.size] ¬ 0; num.size ¬ num.size + 1; }; IF normalize # 1 THEN den ¬ MultiplyByDigit[den, normalize, reuse]; highDen ¬ den.contents[den.size - 1]; nextDen ¬ den.contents[den.size - 2]; quo.size ¬ num.size - den.size; quo.contents ¬ NEW[BigCARDRec[quo.size]]; FOR quoIndex: NAT DECREASING IN [0..quo.size) DO <> guess: Digit ¬ Digit.LAST; leftShiftedDigit.hi ¬ num.contents[quoIndex + den.size]; smallNum ¬ leftShiftedDigit.card + num.contents[quoIndex + den.size - 1]; IF highDen # leftShiftedDigit.hi THEN guess ¬ LongDiv[smallNum, highDen]; <> WHILE TRUE DO readyToShift ¬ smallNum - LongMult[guess, highDen]; IF readyToShift >= lastPlus THEN EXIT; leftShiftedDigit.hi ¬ readyToShift; IF leftShiftedDigit.card+num.contents[quoIndex + den.size - 2] >= LongMult[guess, nextDen] THEN EXIT; guess ¬ guess - 1; ENDLOOP; <> carry ¬ borrow ¬ 0; FOR denIndex: NAT IN [0..den.size) DO multResults ¬ LongMult[den.contents[denIndex], guess] + carry; carry ¬ Basics.HighHalf[multResults]; subtract ¬ Basics.LowHalf[multResults]; <<>> <> subResults ¬ CARD32[num.contents[quoIndex + denIndex]] - subtract + borrow; CheckLittle[quoIndex]; CheckLittle[denIndex]; num.contents[quoIndex + denIndex] ¬ Basics.LowHalf[subResults]; CheckLittle[num.contents[quoIndex + denIndex]]; borrow ¬ LOOPHOLE[INT32[LOOPHOLE[Basics.HighHalf[subResults], INT16]], CARD]; ENDLOOP; <> IF carry - borrow > num.contents[quoIndex + den.size] THEN { carry ¬ 0; FOR denIndex: NAT IN [0..den.size) DO addResults ¬ CARD32[den.contents[denIndex]] + num.contents[quoIndex + denIndex] + carry; carry ¬ Basics.HighHalf[addResults]; CheckLittle[quoIndex]; CheckLittle[denIndex]; num.contents[quoIndex + denIndex] ¬ Basics.LowHalf[addResults]; CheckLittle[num.contents[quoIndex + denIndex]]; ENDLOOP; guess ¬ guess - 1; }; CheckLittle[quoIndex]; CheckLittle[guess]; quo.contents[quoIndex] ¬ guess; ENDLOOP; quo ¬ StripLeadingZeros[quo]; CheckLittle[num.size]; num.size ¬ den.size; [rem, remainder] ¬ DivideByDigit[num, normalize, TRUE]; Check[$BigDivModResult, quo, rem]; }; <> BigFromDecimalRope: PUBLIC PROC [in: Rope.ROPE] RETURNS [out: BigCARD] ~ { action: Rope.ActionType = { <<[c: CHAR] RETURNS [quit: BOOL _ FALSE]>> IF pos = 0 THEN SELECT c FROM '0, ' => RETURN; ENDCASE; SELECT c FROM IN ['0..'9] => { pos ¬ pos + 1; chunk ¬ chunk * 10 + CARDINAL[c-'0]; IF (Basics.LowHalf[pos] MOD 4) = 0 THEN { out ¬ MultiplyByDigit[out, 10000, TRUE]; out ¬ AddDigit[out, chunk, TRUE]; chunk ¬ 0; }; }; ENDCASE => BigFail[$InvalidDecimalNumber]; }; pos: CARD ¬ 0; chunk: Digit ¬ 0; [] ¬ Rope.Map[base: in, action: action]; SELECT (Basics.LowHalf[pos] MOD 4) FROM 0 => RETURN; 1 => out ¬ MultiplyByDigit[out, 10, TRUE]; 2 => out ¬ MultiplyByDigit[out, 100, TRUE]; 3 => out ¬ MultiplyByDigit[out, 1000, TRUE]; ENDCASE => ERROR; out ¬ AddDigit[out, chunk, TRUE]; }; StoreBCByte: PROC [bc: BigCardinals.BigCARD, i: CARD, byte: BYTE] ~ { q: CARDINAL ~ i / bytesPerDigit; r: CARDINAL ~ i MOD bytesPerDigit; bc.contents[q] ¬ Basics16.BITOR[Basics16.BITAND[Basics16.BITNOT[Basics16.BITSHIFT[255, (8*r)]], bc.contents[q]], Basics16.BITSHIFT[byte, (8*r)]]; }; BigFromBinaryRope: PUBLIC PROC [in: ROPE] RETURNS [BigCardinals.BigCARD] ~ { nBytes: CARD ~ Rope.Size[in]; IF nBytes = 0 THEN { RETURN [BigCardinals.Zero] } ELSE { nDigits: CARDINAL ~ (nBytes+(bytesPerDigit-1))/bytesPerDigit; bc: BigCardinals.BigCARD ¬ [size: nDigits, contents: NEW[BigCardinals.BigCARDRec[nDigits]]]; index: CARD ¬ nBytes; Action: PROC [c: CHAR] RETURNS [quit: BOOL ¬ FALSE] ~ { StoreBCByte[bc, index ¬ index - 1, ORD[c]] }; bc.contents[nDigits-1] ¬ 0; [] ¬ Rope.Map[base: in, action: Action]; RETURN [bc] }; }; FetchBCByte: PROC [in: BigCardinals.BigCARD, i: CARD] RETURNS [BYTE] ~ { q: NAT ~ i / bytesPerDigit; r: NAT ~ i MOD bytesPerDigit; RETURN [VAL[Basics16.BITSHIFT[in.contents[q], -(8*r)] MOD 256]] }; BigToBinaryRope: PUBLIC PROC [in: BigCardinals.BigCARD] RETURNS [ROPE] ~ { length: CARD ¬ CARD32[in.size]*bytesPerDigit; WHILE length # 0 AND FetchBCByte[in, length-1] = 0 DO length ¬ length - 1 ENDLOOP; { index: CARD ¬ length; P: PROC RETURNS [CHAR] ~ { RETURN [VAL[FetchBCByte[in, index ¬ index - 1]]] }; RETURN [Rope.FromProc[len: length, p: P]] }; }; BigFromRope: PUBLIC PROC [in: Rope.ROPE] RETURNS [out: BigCARD ¬ []] ~ { IF useNewRopeEncoding THEN { len: INT ¬ Rope.Size[in]; IF len # 0 THEN { pos: INT ¬ Rope.SkipOver[in, 0, "\000"]; IF pos < len THEN { bits: INT ¬ (len-pos) * BITS[CHAR]; outlen: NAT ¬ LongDiv[bits+bitsPerDigit-1, bitsPerDigit]; index: NAT ¬ outlen-1; action: Rope.ActionType = { <<[c: CHAR] RETURNS [quit: BOOL _ FALSE]>> w: Digit ¬ Basics16.BITSHIFT[ORD[c], shift ¬ shift - BITS[CHAR]]; out.contents[index] ¬ out.contents[index] + w; IF shift = 0 AND index # 0 THEN {shift ¬ bitsPerDigit; index ¬ index - 1}; }; delta: CARD ¬ len - pos; shift: NAT ¬ bitsPerDigit - (delta MOD bytesPerDigit)*NAT[BITS[CHAR]]; out.contents ¬ NEW[BigCARDRec[outlen]]; out.size ¬ outlen; [] ¬ Rope.Map[in, pos, delta, action]; out ¬ Shift[out, pos+1]; }; IF pos # 0 THEN { <> ones: BigCARD ¬ BigSubtract[Shift[BigFromSmall[1], pos], BigFromSmall[1], TRUE]; out ¬ BigAdd[out, ones]; }; }; } ELSE { x, y: INT ¬ 0; trailingOnes: BigCARD ¬ BigFromSmall[1]; j: INT ¬ Rope.Size[in] - 1; i: NAT; <> UNTIL j < 0 OR in.Fetch[j] ~= '\000 DO j ¬ j-1; x ¬ x + 1; ENDLOOP; in ¬ Rope.Substr[in, 0, j+1]; <> out.size ¬ (j + 2)/2; out.contents ¬ NEW[BigCARDRec[out.size]]; IF ~BigZero[out] THEN { i ¬ j ¬ 0; UNTIL j > Rope.Size[in] - 3 DO out.contents[i] ¬ (in.Fetch[j] - 0C); j ¬ j + 1; out.contents[i] ¬ Basics16.BITOR[out.contents[i], (Rope.Fetch[in, j] - 0C)*256]; j ¬ j + 1; i ¬ i + 1; ENDLOOP; IF j = Rope.Size[in]-2 THEN out.contents[out.size-1] ¬ (Rope.Fetch[in, j+1] - 0C)*256 + (Rope.Fetch[in, j] - 0C) ELSE out.contents[out.size - 1] ¬ (Rope.Fetch[in, j] - 0C); }; <> UNTIL y = x DO trailingOnes ¬ BigMultiply[trailingOnes, BigFromSmall[2]]; y ¬ y + 1; ENDLOOP; out ¬ BigMultiply[out, BigMultiply[trailingOnes, BigFromSmall[2]]]; out ¬ BigAdd[out, BigSubtract[trailingOnes, BigFromSmall[1]]]; }; }; MultiplyByDigit: PUBLIC PROC [big: BigCARD, small: Digit, reuse: BOOL ¬ FALSE] RETURNS [out: BigCARD] ~ { multResults: CARD; carry: Digit ¬ 0; CheckBigLittle[$MultiplyByDigit, big, small]; IF reuse THEN out ¬ big ELSE out ¬ BigCopy[big]; SELECT small FROM 0 => { FOR index: NAT IN [0..out.size) DO out.contents[index] ¬ 0; ENDLOOP; }; 1 => { carry ¬ 0; -- for placing counting breakpoints }; 2 => { cc: Digit ¬ 0; FOR index: NAT IN [0..out.size) DO c: CARD ¬ CARD[out.contents[index]]*2+cc; out.contents[index] ¬ Basics.LowHalf[c]; cc ¬ Basics.HighHalf[c]; ENDLOOP; carry ¬ cc; }; 4 => { cc: Digit ¬ 0; FOR index: NAT IN [0..out.size) DO c: CARD ¬ CARD[out.contents[index]]*4+cc; out.contents[index] ¬ Basics.LowHalf[c]; cc ¬ Basics.HighHalf[c]; ENDLOOP; carry ¬ cc; }; ENDCASE => { FOR index: NAT IN [0..out.size) DO multResults ¬ LongMult[out.contents[index], small] + carry; out.contents[index] ¬ Basics.LowHalf[multResults]; carry ¬ Basics.HighHalf[multResults]; ENDLOOP; }; IF carry > 0 THEN { IF out.size >= out.contents.max THEN out ¬ BigCopy[out]; out.contents[out.size] ¬ carry; out.size ¬ out.size + 1 }; CheckResult[$MultiplyByDigit, out]; }; AddDigit: PROC [in: BigCARD, digit: Digit, reuse: BOOL] RETURNS [BigCARD] = { CheckBigLittle[$AddDigit, in, digit]; IF in.size = 0 THEN RETURN [BigFromSmall[digit]]; IF NOT reuse THEN in ¬ BigCopy[in]; IF digit = 0 THEN RETURN [in]; FOR i: NAT IN [0..in.size) DO addResults: CARD ¬ CARD32[in.contents[i]] + digit; in.contents[i] ¬ Basics.LowHalf[addResults]; digit ¬ Basics.HighHalf[addResults]; IF digit = 0 THEN RETURN [in]; ENDLOOP; <> in ¬ BigCopy[in]; in.contents[in.size] ¬ digit; in.size ¬ in.size + 1; CheckResult[$AddDigit, in]; RETURN [in]; }; Shift: PUBLIC PROC [bc: BigCARD, bits: INT] RETURNS [BigCARD] = { new: BigCARD ¬ []; Check[$Shift, bc, []]; IF bits = 0 THEN {CheckResult[$Shift, bc]; RETURN [bc]}; IF bc.size # 0 THEN { bcBits: INT ¬ CARD32[bc.size]*bitsPerDigit + bits; hiWord: Digit ¬ bc.contents[bc.size-1]; hiLim: Digit ¬ Digit.LAST - Digit.LAST/2; IF hiWord = 0 THEN ERROR; WHILE hiWord < hiLim DO hiWord ¬ hiWord + hiWord; bcBits ¬ bcBits - 1; ENDLOOP; IF bcBits > 0 THEN { loWord: Digit ¬ 0; mod: INTEGER ¬ LOOPHOLE[bits, CARD] MOD bitsPerDigit; loShift: INTEGER ¬ 0; hiShift: INTEGER ¬ 0; srcIndex: NAT ¬ 0; dstIndex: NAT ¬ 0; newSize: NAT ¬ (bcBits+bitsPerDigit-1)/bitsPerDigit; new.contents ¬ NEW[BigCARDRec[newSize]]; new.size ¬ newSize; SELECT bits FROM < 0 => { <> div: Digit ¬ LongDiv[-bits, bitsPerDigit]; srcIndex ¬ div; IF mod = 0 THEN { <> FOR i: NAT IN [0..newSize) DO new.contents[dstIndex+i] ¬ bc.contents[srcIndex+i] ENDLOOP; } ELSE { <> loShift ¬ mod-bitsPerDigit; hiShift ¬ mod; loWord ¬ bc.contents[srcIndex]; THROUGH [1..newSize) DO srcIndex ¬ srcIndex + 1; hiWord ¬ bc.contents[srcIndex]; new.contents[dstIndex] ¬ Basics16.BITSHIFT[hiWord, hiShift] + Basics16.BITSHIFT[loWord, loShift]; dstIndex ¬ dstIndex + 1; loWord ¬ hiWord; ENDLOOP; hiWord ¬ 0; IF srcIndex+1 < bc.size THEN hiWord ¬ bc.contents[srcIndex+1]; new.contents[dstIndex] ¬ Basics16.BITSHIFT[hiWord, hiShift] + Basics16.BITSHIFT[loWord, loShift]; }; }; > 0 => { <> div: Digit ¬ LongDiv[bits, bitsPerDigit]; nwords: NAT ¬ newSize - div + 1; dstIndex ¬ div; IF mod = 0 THEN { <> FOR i: NAT IN [0..bc.size) DO new.contents[dstIndex+i] ¬ bc.contents[srcIndex+i] ENDLOOP; } ELSE { <> loShift ¬ mod-bitsPerDigit; hiShift ¬ mod; loWord ¬ 0; THROUGH [0..bc.size) DO hiWord ¬ bc.contents[srcIndex]; srcIndex ¬ srcIndex + 1; new.contents[dstIndex] ¬ Basics16.BITSHIFT[hiWord, hiShift] + Basics16.BITSHIFT[loWord, loShift]; dstIndex ¬ dstIndex + 1; loWord ¬ hiWord; ENDLOOP; loWord ¬ Basics16.BITSHIFT[loWord, loShift]; IF loWord # 0 THEN new.contents[dstIndex] ¬ loWord; }; }; ENDCASE => ERROR; new ¬ StripLeadingZeros[new]; }; }; CheckResult[$Shift, new]; RETURN [new]; }; MulMod: PROC [x, y, mod: BigCARD] RETURNS [bc: BigCARD ¬ []] = { Check[$MulMod, x, y]; IF x.size # 0 AND y.size # 0 AND mod.size # 0 THEN { SELECT BigCompare[x, mod] FROM equal => RETURN; greater => {x ¬ BigDivMod[x, mod].rem; IF x.size = 0 THEN RETURN}; ENDCASE; SELECT BigCompare[y, mod] FROM equal => RETURN; greater => {y ¬ BigDivMod[y, mod].rem; IF y.size = 0 THEN RETURN}; ENDCASE; IF x.size = 1 AND y.size = 1 THEN { <> prod: CARD ¬ LongMult[x.contents[0], y.contents[0]]; IF mod.size < 3 THEN prod ¬ prod MOD BigToCard[mod]; RETURN [BigFromCard[prod]]; }; bc ¬ BigMultiply[x, y]; SELECT TRUE FROM bc.size < mod.size => RETURN; bc.size = mod.size AND bc.contents[bc.size-1] < mod.contents[bc.size-1] => RETURN; ENDCASE; bc ¬ BigDivMod[bc, BigCopy[mod], TRUE].rem; }; CheckResult[$MulMod, bc]; }; TwoToTheNth: PUBLIC PROC [n: NAT] RETURNS [bc: BigCARD] = { <> mod: NAT ¬ n MOD bitsPerDigit; words: NAT ¬ (n+bitsPerDigit) / bitsPerDigit; bit: Digit ¬ Basics16.BITSHIFT[1, mod]; bc.size ¬ words; bc.contents ¬ NEW[BigCARDRec[words]]; -- initialized to all zeros by the allocator? bc.contents[words-1] ¬ bit; }; TimesTwoToTheNth: PUBLIC PROC [in: BigCARD, n: NAT] RETURNS [BigCARD] = { <> RETURN [Shift[in, n]]; }; BigPowerOfBase: PUBLIC PROC [base: BigCARD, exponent: NAT] RETURNS [BigCARD] ~ { power: BigCARD ¬ BigFromSmall[1]; IF exponent = 0 THEN RETURN [power]; <<-- Exponentiation by repeated squaring.>> WHILE exponent > 1 DO IF exponent MOD 2 = 1 THEN power ¬ BigMultiply[power, base]; exponent ¬ exponent / 2; base ¬ BigMultiply[base, base]; ENDLOOP; power ¬ BigMultiply[power, base]; RETURN [power]; }; BigPowerOfTen: PUBLIC PROC [exponent: NAT] RETURNS [BigCARD] ~ { RETURN [BigPowerOfBase[BigFromSmall[10], exponent]]; }; BigToREAL: PUBLIC PROC [in: BigCARD] RETURNS [REAL] ~ { real: REAL ¬ 0.0; scale: INTEGER ¬ 0; IF BigZero[in] THEN RETURN [real]; FOR index: NAT IN [0..in.size) DO real ¬ real + Real.FScale[REAL[in.contents[index]], scale]; scale ¬ scale + BITS[Digit]; ENDLOOP; RETURN [real] }; BigOne: PUBLIC PROC [in: BigCARD] RETURNS [BOOL] ~ { <> IF in.size = 1 THEN RETURN [in.contents[0] = 1] ELSE RETURN [FALSE] }; FirstOneBit: PUBLIC PROC [bc: BigCARD] RETURNS [exp: INT ¬ -1] = { IF bc.size > 0 THEN { temp: Digit ¬ bc.contents[bc.size-1]; exp ¬ CARD[bc.size-1]*CARD[BITS[Digit]]; IF temp = 0 THEN ERROR; DO temp ¬ temp / 2; IF temp = 0 THEN EXIT; exp ¬ exp + 1; ENDLOOP; }; }; LowOrderZeros: PUBLIC PROC [bc: BigCARD] RETURNS [INT] = { IF bc.size > 0 THEN { FOR i: NAT IN [0..bc.size) DO w: Digit ¬ bc.contents[i]; IF w # 0 THEN { n: INT ¬ INT[i]*BITS[Digit]; WHILE (w MOD 16 = 0) DO w ¬ w / 16; n ¬ n + 4 ENDLOOP; WHILE (w MOD 2 = 0) DO w ¬ w / 2; n ¬ n + 1 ENDLOOP; RETURN [n] }; ENDLOOP; }; RETURN [-1] }; BigFactorial: PUBLIC PROC [x: NAT] RETURNS [out: BigCARD] = { <> bc: BigCardinals.BigCARD ¬ BigFromSmall[x]; exp: NAT ¬ 0; WHILE x > 1 DO digit: Digit ¬ x ¬ x-1; WHILE (digit MOD 2) = 0 DO digit ¬ digit / 2; exp ¬ exp + 1; ENDLOOP; IF digit # 1 THEN bc ¬ MultiplyByDigit[bc, digit, TRUE]; ENDLOOP; IF exp # 0 THEN bc ¬ TimesTwoToTheNth[bc, exp]; <> RETURN [bc]; }; BigToDecimalRope: PUBLIC PROC [in: BigCARD, reuse: BOOL ¬ FALSE] RETURNS [out: Rope.ROPE ¬ NIL] ~ { SELECT in.size FROM 0 => RETURN ["0"]; 1 => RETURN [Convert.RopeFromCard[in.contents[0]]]; ENDCASE => { chunk: Digit; ros: STREAM ¬ IO.ROS[]; pos: INT ¬ 0; fetch: PROC RETURNS [CHAR] = { RETURN [Rope.Fetch[out, pos ¬ pos - 1]]; }; IF NOT reuse THEN in ¬ BigCopy[in]; UNTIL in.size = 0 DO [in, chunk] ¬ DivideByDigit[in, 10, TRUE]; IO.PutChar[ros, '0 + chunk]; ENDLOOP; out ¬ IO.RopeFromROS[ros]; pos ¬ Rope.Size[out]; RETURN [Rope.FromProc[pos, fetch]]; }; }; BigToRope: PUBLIC PROC [in: BigCARD] RETURNS [out: Rope.ROPE ¬ NIL] ~ { IF useNewRopeEncoding THEN { <> IF in.size # 0 THEN { trailingOnes: INT ¬ 0; total: INT ¬ trailingOnes+1; index: NAT ¬ 0; sample: Digit ¬ 0; shift: INTEGER ¬ 0; eachChar: PROC RETURNS [c: CHAR] = { IF trailingOnes > 0 THEN {trailingOnes ¬ trailingOnes - 1; RETURN [0C]}; c ¬ VAL[Basics16.BITSHIFT[sample, shift] MOD 256]; IF shift = 0 THEN { IF index = 0 THEN RETURN; index ¬ index - 1; sample ¬ in.contents[index]; shift ¬ -bitsPerDigit; }; shift ¬ shift + BITS[CHAR]; }; FOR i: NAT IN [0..in.size) DO digit: Digit ¬ in.contents[i]; IF digit # Digit.LAST THEN { WHILE (digit MOD 2) = 1 DO trailingOnes ¬ trailingOnes + 1; digit ¬ digit / 2; ENDLOOP; EXIT; }; trailingOnes ¬ trailingOnes + BITS[Digit]; ENDLOOP; total ¬ trailingOnes; in ¬ Shift[in, -1-trailingOnes]; IF in.size # 0 THEN { chars: INT ¬ in.size * bytesPerDigit; index ¬ in.size-1; sample ¬ in.contents[index]; shift ¬ -bitsPerDigit; WHILE shift # 0 DO <> shift ¬ shift + BITS[CHAR]; IF Basics.LowHalf[Basics16.BITSHIFT[sample, shift]] # 0 THEN EXIT; chars ¬ chars - 1; ENDLOOP; total ¬ total + chars; }; out ¬ Rope.FromProc[total, eachChar]; }; } ELSE { x, y: INT ¬ 0; nonTrailingOnes: BigCARD; i: INT; trailingOnes: BigCARD ¬ BigFromSmall[1]; trailingNulls, nonTrailingNulls: Rope.ROPE ¬ NIL; i ¬ 0; UNTIL i = in.size DO mask: Digit ¬ 1B; thisBit: Digit ¬ Basics16.BITAND[in.contents[i], mask]; <> WHILE mask > 0B AND thisBit = mask DO x ¬ x + 1; mask ¬ mask * 2; thisBit ¬ Basics16.BITAND[in.contents[i], mask]; ENDLOOP; <> IF x = 0 OR thisBit = 0 THEN i ¬ in.size ELSE i ¬ i + 1; ENDLOOP; UNTIL y = x DO trailingOnes ¬ BigMultiply[trailingOnes, BigFromSmall[2]]; trailingNulls ¬ Rope.Concat[trailingNulls, Rope.FromChar['\000]]; y ¬ y + 1; ENDLOOP; nonTrailingOnes ¬ BigSubtract[in, BigSubtract[trailingOnes, BigFromSmall[1]]]; nonTrailingOnes ¬ BigDivMod[nonTrailingOnes, BigMultiply[trailingOnes, BigFromSmall[2]]].quo; IF ~BigZero[nonTrailingOnes] THEN { FOR i IN [0 .. nonTrailingOnes.size - 1) DO nonTrailingNulls ¬ Rope.Concat[nonTrailingNulls, Rope.FromChar[nonTrailingOnes.contents[i] MOD 256 + 0C]]; nonTrailingNulls ¬ Rope.Concat[nonTrailingNulls, Rope.FromChar[nonTrailingOnes.contents[i] / 256+ 0C]]; ENDLOOP; nonTrailingNulls ¬ Rope.Concat[nonTrailingNulls, Rope.FromChar[nonTrailingOnes.contents[nonTrailingOnes.size - 1] MOD 256 + 0C]]; IF nonTrailingOnes.contents[nonTrailingOnes.size - 1] > 257 THEN nonTrailingNulls ¬ Rope.Concat[nonTrailingNulls, Rope.FromChar[nonTrailingOnes.contents[nonTrailingOnes.size -1] / 256 + 0C]]; }; out ¬ Rope.Concat[nonTrailingNulls, trailingNulls]; }; }; DivideByDigit: PROC [num: BigCARD, den: Digit, reuse: BOOL ¬ FALSE] RETURNS [quo: BigCARD, rem: Digit ¬ 0] ~ { quotient: Digit; leftShiftedRem: Basics.LongNumber ¬ [pair[hi: 0, lo: 0]]; CheckBigLittle[$DivideByDigit, num, den]; IF reuse THEN quo ¬ num ELSE quo ¬ BigCopy[num]; SELECT den FROM 1 => { quotient ¬ 0; }; 2 => { high: Digit ¬ 0; FOR index: NAT DECREASING IN [0..quo.size) DO c: Digit ¬ quo.contents[index]; rem ¬ c MOD 2; quo.contents[index] ¬ c/2 + high; high ¬ rem * highBit; ENDLOOP; }; 4 => { high: Digit ¬ 0; FOR index: NAT DECREASING IN [0..quo.size) DO c: Digit ¬ quo.contents[index]; rem ¬ c MOD 4; quo.contents[index] ¬ c/4 + high; high ¬ rem * (highBit/2); ENDLOOP; }; ENDCASE => { FOR index: NAT DECREASING IN [0..quo.size) DO leftShiftedRem.hi ¬ rem; [quotient, rem] ¬ LongDivMod[quo.contents[index]+leftShiftedRem.card, den]; quo.contents[index] ¬ quotient; ENDLOOP; }; quo ¬ StripLeadingZeros[quo]; CheckResult[$DivideByDigit, quo]; }; BigFromSmall: PUBLIC PROC [in: Digit] RETURNS [out: BigCARD ¬ []] ~ { IF in # 0 THEN { out.contents ¬ NEW[BigCARDRec[1]]; out.size ¬ 1; out.contents[0] ¬ in; }; }; BigToSmall: PUBLIC PROC [in: BigCARD] RETURNS [out: Digit] ~ { SELECT in.size FROM 0 => RETURN [0]; 1 => RETURN [in.contents[0]]; ENDCASE => ERROR BigFail[$TooLarge]; }; BigFromCard: PUBLIC PROC [in: CARD] RETURNS [out: BigCARD] ~ { ln: Basics.LongNumber ¬ [card[in]]; SELECT TRUE FROM ln.hi # 0 => { out.size ¬ 2; out.contents ¬ NEW[BigCARDRec[2]]; out.contents[0] ¬ ln.lo; out.contents[1] ¬ ln.hi; }; ln.lo # 0 => { out.size ¬ 1; out.contents ¬ NEW[BigCARDRec[1]]; out.contents[0] ¬ ln.lo; }; ENDCASE => out.size ¬ 0; }; BigToCard: PUBLIC PROC [in: BigCARD] RETURNS [out: CARD] ~ { ln: Basics.LongNumber ¬ [pair[hi: 0, lo: 0]]; SELECT in.size FROM 0 => {}; 1 => ln.lo ¬ in.contents[0]; 2 => {ln.lo ¬ in.contents[0]; ln.hi ¬ in.contents[1]}; ENDCASE => ERROR BigFail[$TooLarge]; RETURN [ln.card]; }; <> copyOver: NAT ¬ 4; BigCopy: PUBLIC PROC [in: BigCARD] RETURNS [out: BigCARD] ~ { out.size ¬ in.size; out.contents ¬ NEW[BigCARDRec[in.size + copyOver]]; IF in.size > 0 THEN { FOR i: NAT IN [0..in.size) DO out.contents[i] ¬ in.contents[i]; ENDLOOP; <> }; }; BigCompare: PUBLIC PROC [in1, in2: BigCARD] RETURNS [Basics.Comparison] ~ { IF in1.size = in2.size AND in1.size # 0 THEN { FOR i: NAT DECREASING IN [0..in1.size) DO IF in1.contents[i] # in2.contents[i] THEN RETURN [Basics.CompareCard[in1.contents[i], in2.contents[i]]]; ENDLOOP; RETURN [equal]; }; RETURN [Basics.CompareCard[in1.size, in2.size]]; }; BigZero: PUBLIC PROC [big: BigCARD] RETURNS [BOOL] ~ { RETURN [big.size = 0] }; BigOdd: PUBLIC PROC [in: BigCARD] RETURNS [BOOL] ~ { RETURN [in.size # 0 AND in.contents[0] MOD 2 = 1]; }; <> BigRandom: PUBLIC PROC [length: NAT ¬ 0, max, min: BigCARD ¬ [0, NIL] ] RETURNS [out: BigCARD] ~ { minMatters, maxMatters: BOOL ¬ TRUE; lower: Digit ¬ 0; upper: Digit ¬ 177777B; IF length > 0 THEN {out.size ¬ length; maxMatters ¬ minMatters ¬ FALSE} ELSE out.size ¬ max.size; out.contents ¬ NEW[BigCARDRec[out.size]]; FOR index: NAT DECREASING IN [0..out.size) DO IF maxMatters THEN upper ¬ max.contents[index]; IF minMatters AND index < min.size THEN lower ¬ min.contents[index]; out.contents[index] ¬ Random.ChooseInt[rs: markov, min: lower, max: upper]; IF out.contents[index] < upper THEN {maxMatters ¬ FALSE; upper ¬ 177777B}; IF out.contents[index] > lower THEN {minMatters ¬ FALSE; lower ¬ 0}; ENDLOOP; out ¬ StripLeadingZeros[out]; }; BigExponentiate: PUBLIC PROC [base, exponent, modulus: BigCARD, reuse: BOOL ¬ FALSE] RETURNS [out: BigCARD] ~ { <> out ¬ BigFromSmall[1]; IF exponent.size # 0 THEN { IF base.size >= modulus.size THEN base ¬ BigDivMod[base, modulus, FALSE].rem; FOR index: NAT IN [0..exponent.size) DO temporary: Digit ¬ exponent.contents[index]; THROUGH [0..bitsPerDigit) DO IF (temporary MOD 2) = 1 THEN out ¬ MulMod[out, base, modulus]; temporary ¬ temporary / 2; IF temporary = 0 AND index+1 = exponent.size THEN RETURN; base ¬ MulMod[base, base, modulus]; ENDLOOP; ENDLOOP; }; }; BigGCD: PUBLIC PROC [in1, in2: BigCARD] RETURNS [out: BigCARD] ~ { oneLarger: BOOL ¬ (BigCompare[in1, in2] = greater); DO IF in1.size = 0 OR in2.size = 0 THEN EXIT; IF oneLarger THEN in1 ¬ BigDivMod[in1, in2].rem ELSE in2 ¬ BigDivMod[in2, in1].rem; oneLarger ¬ NOT oneLarger; ENDLOOP; out ¬ IF oneLarger THEN in1 ELSE in2; }; BigInverse: PUBLIC PROC [in, modulus: BigCARD] RETURNS [out: BigCARD] ~ { <> sign: INTEGER; sign1, sign2: INTEGER ¬ 1; temp1: BigCARD ¬ BigFromSmall[0]; temp2: BigCARD ¬ BigFromSmall[1]; quo, addOrSub: BigCARD; out ¬ modulus; IF BigCompare[in, out] = greater THEN in ¬ BigDivMod[in, modulus].rem; IF in.size # 0 THEN DO [quo, out] ¬ BigDivMod[out, in]; IF out.size = 0 THEN {out ¬ temp2; sign ¬ sign2; EXIT}; addOrSub ¬ BigMultiply[temp2, quo]; SELECT TRUE FROM sign1 # sign2 => temp1 ¬ BigAdd[temp1, addOrSub]; BigCompare[temp1, addOrSub] = greater => temp1 ¬ BigSubtract[temp1, addOrSub]; ENDCASE => {sign1 ¬ -sign1; temp1 ¬ BigSubtract[addOrSub, temp1]}; [quo, in] ¬ BigDivMod[in, out]; IF in.size = 0 THEN {out ¬ temp1; sign ¬ sign1; EXIT}; addOrSub ¬ BigMultiply[temp1, quo]; SELECT TRUE FROM sign1 # sign2 => temp2 ¬ BigAdd[temp2, addOrSub]; BigCompare[temp2, addOrSub] = greater => temp2 ¬ BigSubtract[temp2, addOrSub]; ENDCASE => {sign2 ¬ -sign2; temp2 ¬ BigSubtract[addOrSub, temp2]}; ENDLOOP; IF sign = -1 THEN out ¬ BigSubtract[modulus, out]; }; BigPrimeTest: PUBLIC PROC [prime: BigCARD, accuracy: NAT ¬ 20] RETURNS [BOOL] ~ { one: BigCARD ¬ BigFromSmall[1]; two: BigCARD ¬ BigFromSmall[2]; primeMinusOne: BigCARD ¬ BigSubtract[prime, one]; q: BigCARD ¬ BigCopy[primeMinusOne]; x, y: BigCARD; j: NAT; k: NAT ¬ 0; IF BigOdd[q] THEN RETURN [FALSE]; UNTIL BigOdd[q] DO q ¬ DivideByDigit[q, 2, TRUE].quo; k ¬ k + 1; ENDLOOP; THROUGH [0..accuracy/2) DO <> x ¬ BigRandom[max: primeMinusOne, min: two]; y ¬ BigExponentiate[x, q, prime]; j ¬ 0; <> <<>> IF NOT BigCompare[y, one] = equal THEN DO IF BigCompare[y, primeMinusOne] = equal THEN EXIT; j ¬ j+1; y ¬ BigExponentiate[y, two, prime]; -- Now y = x­ (q 2­j) IF (j = k) OR BigCompare[y, one] = equal THEN RETURN [FALSE]; ENDLOOP; ENDLOOP; RETURN [TRUE]; }; <> Test: PROC [invTimes: NAT ¬ 10, primeTest: BOOL ¬ TRUE] RETURNS [NAT] ~ { one: BigCARD = BigFromSmall[1]; op1: BigCARD ¬ BigFromDecimalRope["222222222222222222"]; op2: BigCARD ¬ BigFromDecimalRope["18446744073709551556"]; op3: BigCARD ¬ BigFromDecimalRope["18446744073709551557"]; res1: BigCARD ¬ BigExponentiate[op1, op2, op3]; res2, res3: BigCARD; hits, primes: NAT ¬ 0; IF BigCompare[res1, one] # equal THEN ERROR; FOR index: NAT IN [0..invTimes) DO op1 ¬ BigRandom[length: 50]; op2 ¬ BigRandom[length: 40]; res1 ¬ BigSubtract[op1, op2]; res2 ¬ BigAdd[res1, op2]; IF BigCompare[op1, res2] # equal THEN ERROR; [res1, res2] ¬ BigDivMod[op1, op2]; res3 ¬ BigMultiply[op2, res1]; res3 ¬ BigAdd[res2, res3]; IF BigCompare[op1, res3] # equal THEN ERROR; IF BigCompare[BigGCD[op1, op2], one] = equal THEN { hits ¬ hits + 1; res1 ¬ BigInverse[op2, op1]; res2 ¬ BigMultiply[res1, op2]; res3 ¬ BigDivMod[res2, op1].rem; IF BigCompare[one, res3] # equal THEN ERROR; }; ENDLOOP; IF primeTest THEN { <> op1 ¬ BigFromDecimalRope["8297644387"]; op2 ¬ BigFromDecimalRope["4180566390"]; WHILE BigPrimeTest[op1] DO primes ¬ primes + 1; op1 ¬ BigAdd[op1, op2]; ENDLOOP; IF NOT primes = 19 THEN ERROR; }; RETURN [hits] }; TestRopeEncoding: PROC [pow2Times: NAT ¬ 100, randomRopes: NAT ¬ 100, randomBigs: NAT ¬ 100] = { <> <> <> <> one: BigCARD = BigFromSmall[1]; FOR i: NAT IN [0..pow2Times) DO x: BigCARD ¬ TwoToTheNth[i]; xm: BigCARD ¬ BigSubtract[x, one]; xr: ROPE ¬ BigToRope[x]; xmr: ROPE ¬ BigToRope[xm]; IF BigCompare[x, xm] # greater THEN ERROR; IF BigCompare[x, BigFromRope[xr]] # equal THEN ERROR; IF BigCompare[xm, BigFromRope[xmr]] # equal THEN ERROR; IF BigCompare[x, BigFromDecimalRope[BigToDecimalRope[x]]] # equal THEN ERROR; IF BigCompare[xm, BigFromDecimalRope[BigToDecimalRope[xm]]] # equal THEN ERROR; ENDLOOP; FOR i: NAT IN [0..randomRopes) DO eachChar: PROC RETURNS [CHAR] = { RETURN [VAL[BYTE[Random.ChooseInt[rs: markov, min: 0, max: 255]]]]; }; zeroChar: PROC RETURNS [CHAR] = { RETURN [0C]; }; r: ROPE ¬ Rope.FromProc[len: Random.ChooseInt[rs: markov, min: 0, max: 256], p: eachChar]; z: ROPE ¬ Rope.FromProc[len: Random.ChooseInt[rs: markov, min: 1, max: 256], p: zeroChar]; rz: ROPE ¬ Rope.Concat[z, r]; IF NOT Rope.Equal[r, BigToRope[BigFromRope[r]]] THEN ERROR; IF NOT Rope.Equal[z, BigToRope[BigFromRope[z]]] THEN ERROR; IF NOT Rope.Equal[rz, BigToRope[BigFromRope[rz]]] THEN ERROR; ENDLOOP; FOR i: NAT IN [0..randomBigs) DO bc: BigCARD ¬ BigRandom[ length: Random.ChooseInt[rs: markov, min: 0, max: 256], max: [], min: TwoToTheNth[Random.ChooseInt[rs: markov, min: 0, max: 1024]]]; bcr: ROPE ¬ BigToRope[bc]; bcbc: BigCARD ¬ BigFromRope[bcr]; IF BigCompare[bc, bcbc] # equal THEN ERROR; ENDLOOP; }; Time: PROC [] RETURNS [Rope.ROPE] ~ { bc1: BigCARD ¬ BigFromDecimalRope["12345678901234567890123456789012345678901234567890123456789012345678901234567220123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"]; bc2: BigCARD ¬ BigFromDecimalRope["12345678901234567890123456789012345678901234567890123456789012345678901234522220123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"]; bc3: BigCARD ¬ BigFromDecimalRope["1234567890994567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"]; RETURN [ BigToDecimalRope[BigExponentiate[bc1, bc2, bc3 ] ] ]; }; markov: Random.RandomStream ¬ Random.Create[range: 0, seed: -1]; END.