some comments on pdd 14 Big Numbers
Mark Biggar
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
ma...@biggar.org
mark.a...@attbi.com
Benjamin Goldberg
Perhaps this might sound like a foolish suggestion, but...
Wouldn't it be better (for some definition of better) to design our
BigInt type so that we can replace the math engine with a different math
engine? Eg, so we could plug in GMP, or PARI, or Miracl, etc.?
(With a fallback to our own math code)
Something like Perl5's Math::BigInt does.
That way, if someone has a faster math engine, they can use by simply
changing a configuration option (which backend BigInt will use), rather
than having to change the code which creates the bigints.
--
$a=24;split//,240513;s/\B/ => /for@@=qw(ac ab bc ba cb ca
);{push(@b,$a),($a-=6)^=1 for 2..$a/6x--$|;print "$@[$a%6
]\n";((6<=($a-=6))?$a+=$_[$a%6]-$a%6:($a=pop @b))&&redo;}