Based on my experence on implementing the original Big* packages for perl, I have some suggestions after reading pdd 14.
I suggest that instead of storing the mantissa of a Bignum as a BCD string of nibbles that it be stored as a string of 16 bit values each holding 0..9999. Note that this gives you the same bit/digit density (4 digits in 16 bits) as the BCD format and the potential extra byte needed will be lost in the memory alocator noise. This base 10000 storage format has several advantages over a BCD format:
1: unless the hardware supports BCD math directly the implementation of the operator functions is simpler. You don't need to either unpacking the nibbles or deal with middle-of-the-byte nibble carry problem.
2: math operation efficienty. Assuming again that the hardware does not directly support BCD math: add/subtract takes 1/4 the hardware ops and mul/div takes 1/16 even ignoring the overhead from point 1 above.
3: the cost to convert to a decimal string value is not significantly greater.
4: in addition the divide operation is signifficantly more efficient the bigger the base you are working with. The multi-precision divide algorithm used in BigInt.pm (adapted from algorithm D in Knuth Vol 2) selects the next quotiant digit using an guessing method based on the first several digits of the divisor and the partially processed dividend. Sometimes it guesses a value 1 too big and must correct things by doing the equivalent of a multi-precesion add op. The probabily this is necessary is 1/base, thus it happens about 1/10 of the time for each bcd digit in the dividend and only 1/10000 of the time, if you use base 10000.
Other issues:
The only difference between a BigInt and a BigFloat is a restriction on the stored exponent. If you place the decimal point at the right end of the mantissa, then all numbers with non-negative exponents are integers, otherwise you must look at the mantissa length as well as the exponent to determine this.
There should be a builtin GCD operator as that makes defining rational types easy.
Some discussion of how bignums work with the printf formating facility would be nice.
The current BigFloat.pm uses length(divisor)+length(dividend)+2 for the maximum precesion of the result of a divide as opposed to max(divisor, dividend) stated in the pdd.
-- Mark Biggar [EMAIL PROTECTED] [EMAIL PROTECTED]
