Beryl Morrison, 4 June 1982
BigNum Structure and "Constants"
The current PSL bignum package was written using vectors of "Big Digits" or
"Bigits". The first element of each vector is either BIGPOS or BIGNEG,
depending whether the number is positive or negative. A bignum of the form
[BIGPOS a b c d]
has a value of
a + b * bbase!* + c * bbase!* ** 2 + d * bbase!* ** 3
BBase!* is a fluid variable which varies from one machine to another. For the
VAX and the DEC-20, it is calculated as follows:
bbits!* := (n-1)/2;
bbase!* := 2 ** bbits!*;
"n" is the total number of bits per word on the given machine. On the DEC-20,
n is 36, so bbits!* is 17 and bbase!* is 131072. On the VAX, n is 32, so
bbits!* is 15 and bbase!* is 32768.
There are some other constants used in the system as well. The sources are in
pu:bigbig.red on the DEC-20, /u/benson/psl-dist/util/bigbig.red on the VAX.
Starting BigNums
"Load Big;" will bring in the bignum package. A file called big.lap loads
arith.b which provides an interface via tags for when inum functions
and when bignum functions should be used; (sources are in
test-arith.red)
vector-fix.b which provides a means of truncating vectors without copying
them;
bigbig.b which provides the bignum versions of functions as required by
arith.b;
bigface.b which provides the final interface between bigbig.b and
arith.b.
The order of loading the files must remain as shown; arith and vector-fix may
be swapped, but otherwise function definitions must be presented in the order
given.
Building the BigNum Package
Each of the individual files may be rebuilt (to form a new *.b file)
separately. A file XXX.red may be rebuilt as follows:
[1] faslout "YYY";
[2] in "XXX.red"$
2
[3] faslout;
On the DEC-20, the resulting YYY.b file is put on the directory pl:; on the
VAX, it is put on the connected directory. They should be on pl: on the DEC-20
for public access, and on /usr/local/lib/psl on the VAX.
The Functions in BigBig
The functions defined by BigBig for bignums are as follows:
BLOr Takes two BigNum arguments, returning a bignum. Calls BSize,
GtPos, PosIfZero.
BLXOr Takes two BigNum arguments, returning a bignum. Calls BSize,
GtPos, TrimBigNum1.
BLAnd Takes two BigNum arguments, returning a bignum. Calls BSize,
GtPos, TrimBigNum1.
BLNot Takes one BigNum argument, returning a bignum. Calls BMinus,
BSmallAdd.
BLShift Takes two BigNum arguments, returning a bignum. Calls BMinusP,
BQuotient, BTwoPower, BMinus, BTimes2.
BMinus Takes one BigNum argument, returning a bignum. Calls BZeroP,
BSize, BMinusP, GtPos, GtNeg.
BMinusP Takes one BigNum argument, returning a bignum or NIL.
BPlus2 Takes two BigNum arguments, returning a bignum. Calls BMinusP,
BDifference2, BMinus, BPlusA2.
BDifference BZeroP, BMinus, BMinusP, BPlusA2, BDifference2.
BTimes2 Takes two BigNum arguments, returning a bignum. Calls BSize,
BMinusP, GtPos, GtNeg, BDigitTimes2, PosIfZero, TrimBigNum1.
BDivide Takes two BigNum arguments, returning a pair of bignums. Calls
BSize, GtPos, BSimpleDivide, BHardDivide.
BGreaterP Takes two BigNum arguments, returning a bignum or NIL. Calls
BMinusP, BDifference.
BLessP Takes two BigNum arguments, returning a bignum or NIL. Calls
BMinusP, BDifference.
BAdd1 Takes a BigNum argument, returning a bignum. Calls BSmallAdd.
BSub1 Takes a BigNum argument, returning a bignum. Calls
BigSmallDiff.
3
FloatFromBigNum Takes a bignum, returning a float. Calls BZeroP, BGreaterP,
BLessP, BSize, BMinusP.
BChannelPrin2 Calls BigNumP, NonBigNumError, BSimpleDivide, BSize, BZeroP.
BRead Calls GtPos, BReadAdd, BMinus.
BigFromFloat Takes a float and converts to a bignum. Calls BNum, BPlus2,
BTimes2, BTwoPower, FloatFromBigNum, BMinus, PosIfZero.
The following functions are support functions for those given above.
SetBits Takes as an argument the total number of bits per word on a
given machine; sets some fluid variables accordingly. NOTE:
FloatHi!* must be changed separately from this procedure by
hand when moving to a new machine both in bigbig.red and in
bigface.red. Calls TwoPower, BNum, BMinus, BSub1, BTwoPower,
BAdd1.
BigNumP Checks if the argument is a bignum. Calls no special
functions.
NonBigNumError Calls no special functions.
BSize Gives size of a bignum, i.e. total number of bigits (the tag
"BIGPOS" or "BIGNEG" is number 0). Calls BigNumP.
PosIfZero Takes a bignum; if it is a negative zero, it is converted to a
positive zero. Calls BPosOrNegZeroP, BMinusP.
BPosOrNegZeroP Takes a BigNum; checks if magnitude is zero. Calls BSize.
GtPos Takes an inum/fixnum. Returns a vector of size of the
argument; first (i.e.0th) element is BIGPOS, others are NIL.
GtNeg Takes an inum/fixnum. Returns a vector of size of the
argument; first (i.e.0th) element is BIGNEG, others are NIL.
TrimBigNum Takes a BigNum as an argument; truncates any trailing "NIL"s.
Calls BigNumP, NonBigNumError, TrimBigNum1, BSize.
TrimBigNum1 Does dirty work for TrimBigNum, with second argument the size
of the BigNum.
Big2Sys Calls BLessP, BGreaterP, BSize, BMinusP.
TwoPower Takes and returns a fix/inum. 2**n.
BTwoPower Takes a fix/inum or bignum, returns a bignum of value 2**n.
Calls BigNumP, Big2Sys, GtPos, TwoPower, TrimBigNum1.
BZeroP Checks size of BigNum (0) and sign. Calls BSize, BMinusP.
4
BOneP Calls BMinusP, BSize.
BAbs Calls BMinusP, BMinus.
BGeq Calls BLessP.
BLeq Calls BGreaterP.
BMax Calls BGeq.
BMin Calls BLeq.
BExpt Takes a BigNum and a fix/inum. Calls Int2B, BTimes2,
BQuotient.
AddCarry Support for trapping the carry in addition.
BPlusA2 Does the dirty work of addition of two BigNums with signs
pre-checked and identical. Calls BSize, GtNeg, GtPos,
AddCarry, PosIfZero, TrimBigNum1.
SubCarry Mechanism to get carry in subtractions.
BDifference2 Does the dirty work of subtraction with signs pre-checked and
identical. Calls BSize, GtNeg, GtPos, SubCarry, PosIfZero,
TrimBigNum1.
BDigitTimes2 Multiplies the first argument (BigNum) by a single Bigit of the
second BigNum argument. Returns the partially completed
result. Calls no special functions.
BSmallTimes2 Takes a BigNum argument and a fixnum argument, returning a
bignum. Calls GtPos, BMinusP, GtNeg, PosIfZero, TrimBigNum1.
BQuotient Takes two BigNum arguments, returning a bignum. Calls BDivide.
BRemainder Takes two BigNum arguments, returning a bignum. Calls BDivide.
BSimpleQuotient Calls BSimpleDivide.
BSimpleRemainder
Calls BSimpleDivide.
BSimpleDivide Used to divide a BigNum by an inum. Returns a dotted pair of
quotient and remainder, both being bignums. Calls BMinusP,
GtPos, GtNeg, PosIfZero, TrimBigNum1.
BHardDivide Used to divide two "true" BigNums. Returns a pair of bignums.
Algorithm taken from Knuth. Calls BMinusP, GtPos, GtNeg, BAbs,
BSmallTimes2, BSize, BDifference, BPlus2, TrimBigNum1,
BSimpleQuotient, PosIfZero.
5
BReadAdd Calls BSmallTimes2, BSmallAdd.
BSmallAdd Adds an inum to a BigNum, returning a bignum. Calls BZeroP,
BMinusP, BMinus, BSmallDiff, BSize, GtPos, AddCarry, PosIfZero,
TrimBigNum1.
BNum Takes an inum and returns a BigNum of one bigit; test that the
inum is less than bbase!* is assumed done. Calls GtPos, GtNeg.
BSmallDiff Calls BZeroP, BMinusP, BMinus, BSmallAdd, GtPos, SubCarry,
PosIfZero, TrimBigNum1.
int2b Takes a fix/inum and converts to a BigNum. Calls BNum, BRead.
Problems
- Should the "vectors" be changed to hwords?
- Should there be primitives so that each bigit uses almost the whole
word instead of almost half the word? This would involve writing
"overflow" functions, checking and trapping overflow in operations
such as multiplication. This would allow integers to be returned as
inums or fixnums if they are geq the current bbase!* and lessp 2 **
(n-1). Currently, anything bbase!* or larger is kept as a bignum
once the bignum package is loaded.
- Make the constants real constants instead of fluids: bbase!*,
bbits!*, floathi!*, floatlow!*, logicalbits!*, wordhi!*, wordlow!*,
syshi!*, syslo!*, digit2letter!*. Carry!* should be a fluid.
- Try to make the whole package loaded as one *.b file.
- Change arith.b so that divide is used for the interface instead of
quotient and remainder. As it stands, doing a "Divide" when bignums
are loaded would mean doing the quotient and then the remainder
separately, although Knuth's algorithm computes them together.
- Get rid of superfluous functions.
- Put in more calls to NonBigNumError for greater safety?