Basics USING [BITAND, BITOR, BITSHIFT, Comparison, HighByte, HighHalf, LongDiv, LongDivMod, LongMult, LongNumber, LowByte, LowHalf],

BigCardinals,

Convert USING [CardFromRope, RopeFromCard],

IO USING [PutChar, RopeFromROS, ROS, STREAM],

PrincOpsUtils USING [LongCopy],

Random USING [Create, ChooseInt, RandomStream],

Rope USING [Concat, Fetch, FromChar, FromProc, Length, ROPE, Substr];

smaller: BigCARD;

addResults: CARD; carry: CARDINAL ← 0;

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: CARDINAL IN [0..smaller.size) DO

FOR index: CARDINAL IN [smaller.size..out.size) DO

IF carry > 0 THEN {

};

borrow, subResults: CARD ← 0;

IF large.size < small.size THEN ERROR BigFail[$NegativeResult];

IF reuse THEN out ← large ELSE out ← BigCopy[large];

In abuse of type, borrow is conceptually an INT in what follows.

FOR index: CARDINAL IN [0..small.size) DO

FOR index: CARDINAL IN [small.size..out.size) DO

out ← StripLeadingZeros[out];

};

out ← in;

FOR index: CARDINAL DECREASING IN [0..in.size) DO

out.contents ← NIL;

};

carry: CARDINAL ← 0;

IF BigZero[in1] OR BigZero[in2] THEN RETURN;

out.size ← in1.size + in2.size;

out.contents ← NEW[BigCARDRec[out.size]];

FOR index1: CARDINAL IN [0..in1.size) DO

out ← StripLeadingZeros[out];

};

highDen, nextDen: CARDINAL;

smallNum, readyToShift: CARD;

carry, subtract, borrow, multResults, subResults, addResults: CARD;

guess, normalize, remainder: CARDINAL;

oldNumSize: CARDINAL ← num.size;

leftShiftedDigit: Basics.LongNumber ← [lc[0]];

IF den.size=0 THEN ERROR BigFail[$DivideByZero];

IF den.size=1 THEN {

IF NOT reuse THEN num ← BigCopy[num];

IF den.size > num.size THEN {rem ← num; RETURN};

normalize ← den.contents[den.size - 1];

SELECT normalize FROM

IF num.size = oldNumSize THEN {

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: CARDINAL DECREASING IN [0..quo.size) DO

quo ← StripLeadingZeros[quo];

num.size ← den.size;

[rem, remainder] ← DivideByDigit[num, normalize, TRUE];

};

excess: INT ← Rope.Length[in] MOD 4;

chunk: Rope.ROPE ← Rope.Substr[in,0,excess];

temporary: CARD ← IF excess > 0 THEN Convert.CardFromRope[chunk] ELSE 0;

in ← Rope.Substr[in, excess];

out ← BigFromSmall[ temporary ];

UNTIL Rope.Length[in] = 0 DO

};

excess: INT ← Rope.Length[in] MOD 3;

chunk: Rope.ROPE ← Rope.Substr[in,0,excess];

temporary: CARD ← IF excess > 0 THEN Convert.CardFromRope[chunk, 16] ELSE 0;

in ← Rope.Substr[in, excess];

out ← BigFromSmall[ temporary ];

UNTIL Rope.Length[in] = 0 DO

};

x, y: INT ← 0;

trailingOnes: BigCARD ← BigFromSmall[1];

j: INT ← Rope.Length[in] - 1;

i: CARDINAL;

First count (x) and strip off trailing nulls.

UNTIL j < 0 OR in.Fetch[j] ~= '\000 DO j ← j-1; x ← x + 1; ENDLOOP;

in ← Rope.Substr[in, 0, j+1];

size of bigcardinal is ceiling((1/2)*number of non-trailing-null chars in rope).

out.size ← (j + 2)/2;

out.contents ← NEW[BigCARDRec[out.size]];

IF ~BigZero[out] THEN {

Now append one 0 and x 1's to the end of this bigcardinal.

UNTIL y = x DO

out ← BigMultiply[out, BigMultiply[trailingOnes, BigFromSmall[2]]];

out ← BigAdd[out, BigSubtract[trailingOnes, BigFromSmall[1]]];

};

multResults: CARD;

carry: CARDINAL ← 0;

IF reuse THEN out ← big ELSE out ← BigCopy[big];

SELECT small FROM

IF carry > 0 THEN {

};

This procedure computes 2 ^ n.

mod: CARDINAL ← n MOD bitsPerWord;

words: CARDINAL ← n / bitsPerWord + (IF mod # 0 THEN 1 ELSE 0);

bc.size ← words;

IF words # 0 THEN {

};

This procedure computes in * 2 ^ n.

mod: CARDINAL ← n MOD bitsPerWord;

modNotZero: CARDINAL ← IF mod # 0 THEN 1 ELSE 0;

words: CARDINAL ← n / bitsPerWord + modNotZero;

out.size ← 0;

IF words # 0 AND in.size # 0 THEN {

};

Returns the factorial of x.

bc: BigCardinals.BigCARD ← BigFromSmall[x];

exp: CARDINAL ← 0;

WHILE x > 1 DO

IF exp # 0 THEN bc ← TimesTwoToTheNth[bc, exp];

RETURN [bc];

};

SELECT in.size FROM

};

SELECT in.size FROM

};

x, y: INT ← 0;

nonTrailingOnes: BigCARD;

i: INT;

trailingOnes: BigCARD ← BigFromSmall[1];

trailingNulls, nonTrailingNulls: Rope.ROPE ← NIL;

i ← 0;

UNTIL i = in.size DO

UNTIL y = x DO

nonTrailingOnes ← BigSubtract[in, BigSubtract[trailingOnes, BigFromSmall[1]]];

nonTrailingOnes ← BigDivMod[nonTrailingOnes, BigMultiply[trailingOnes, BigFromSmall[2]]].quo;

IF ~BigZero[nonTrailingOnes] THEN {

out ← Rope.Concat[nonTrailingNulls, trailingNulls];

};

quotient: CARDINAL;

leftShiftedRem: Basics.LongNumber ← [lc[0]];

IF reuse THEN quo ← num ELSE quo ← BigCopy[num];

SELECT den FROM

quo ← StripLeadingZeros[quo];

};

IF in = 0

};

SELECT in.size FROM

};

ln: Basics.LongNumber ← [lc[in]];

SELECT TRUE FROM

};

ln: Basics.LongNumber ← [lc[0]];

SELECT in.size FROM

RETURN [ln.lc];

};

out.size ← in.size;

out.contents ← NEW[BigCARDRec[in.size + 2]];

IF in.size > 0 THEN TRUSTED {

};

IF in1.size > in2.size THEN RETURN [greater];

IF in1.size < in2.size THEN RETURN [less];

FOR index: CARDINAL DECREASING IN [0..in1.size) DO

RETURN [equal];

};

RETURN [big.size = 0]

};

RETURN [in.size # 0 AND in.contents[0] MOD 2 = 1];

};

minMatters, maxMatters: BOOL ← TRUE;

lower: CARDINAL ← 0;

upper: CARDINAL ← 177777B;

IF length > 0

out.contents ← NEW[BigCARDRec[out.size]];

FOR index: CARDINAL DECREASING IN [0..out.size) DO

out ← StripLeadingZeros[out];

};

temporary: CARDINAL;

out ← BigFromSmall[1];

IF BigZero[exponent] THEN RETURN;

IF NOT reuse THEN base ← BigCopy[base];

Exponentiation by repeated squaring.

FOR index: CARDINAL IN [0..exponent.size) DO

};

oneLarger: BOOL ← (BigCompare[in1, in2] = greater);

DO

out ← IF oneLarger THEN in1 ELSE in2;

};

This is 1/2 of an extended GCD algorithm. Since the intermediate results can be negative, signs must be maintained: sign1 for temp1 and sign2 for temp2.

sign: INTEGER;

sign1, sign2: INTEGER ← 1;

temp1, quo, addOrSub: BigCARD;

temp2: BigCARD ← BigFromSmall[1];

out ← modulus;

IF BigCompare[in, out] = greater THEN in ← BigDivMod[in, modulus].rem;

DO

IF sign = -1 THEN out ← BigSubtract[modulus, out];

};

one: BigCARD ← BigFromSmall[1]; two: BigCARD ← BigFromSmall[2];

primeMinusOne: BigCARD ← BigSubtract[prime, one];

q: BigCARD ← BigCopy[primeMinusOne];

x, y: BigCARD;

j: CARDINAL;

k: CARDINAL ← 0;

IF BigOdd[q] THEN RETURN [FALSE];

UNTIL BigOdd[q] DO

THROUGH [0..accuracy/2) DO

RETURN [TRUE];

};

op1, op2, op3, res1, res2, res3, one: BigCARD;

hits, primes: CARDINAL ← 0;

one ← BigFromSmall[1];

op1 ← BigFromDecimalRope["222222222222222222"];

op2 ← BigFromDecimalRope["18446744073709551556"];

op3 ← BigFromDecimalRope["18446744073709551557"];

res1 ← BigExponentiate[op1, op2, op3];

IF NOT(BigCompare[res1, one] = equal) THEN ERROR;

FOR index: CARDINAL IN [0..iterations) DO

A long arithmetic progression of primes found by Paul Pritchard of Cornell

op1 ← BigFromDecimalRope["8297644387"];

op2 ← BigFromDecimalRope["4180566390"];

WHILE BigPrimeTest[op1] DO

IF NOT primes = 19 THEN ERROR;

RETURN [hits]

};

RETURN [ BigToDecimalRope[BigExponentiate[BigFromDecimalRope["12345678901234567890123456789012345678901234567890123456789012345678901234567220123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"], BigFromDecimalRope["12345678901234567890123456789012345678901234567890123456789012345678901234522220123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"], BigFromDecimalRope["1234567890994567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"] ] ] ]

};