Artifact 50a96777acf029a18be08a78952856c25fea340f474d3b568c6f4394c8f46194:
- File
psl-1983/3-1/help/big.doc
— part of check-in
[eb17ceb7f6]
at
2020-04-21 19:40:01
on branch master
— Add Reduce 3.0 to the historical section of the archive, and some more
files relating to version sof PSL from the early 1980s. Thanks are due to
Paul McJones and Nelson Beebe for these, as well as to all the original
authors.git-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/historical@5328 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: arthurcnorman@users.sourceforge.net, size: 10214) [annotate] [blame] [check-ins using] [more...]
- File
psl-1983/help/big.hlp
— part of check-in
[eb17ceb7f6]
at
2020-04-21 19:40:01
on branch master
— Add Reduce 3.0 to the historical section of the archive, and some more
files relating to version sof PSL from the early 1980s. Thanks are due to
Paul McJones and Nelson Beebe for these, as well as to all the original
authors.git-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/historical@5328 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: arthurcnorman@users.sourceforge.net, size: 10214) [annotate] [blame] [check-ins using]
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?