123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256 |
- 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?
|