develooper Front page | perl.perl5.porters | Postings from November 2000

Re: Math::BigInt* (2)

From:
Steffen Beyer
Date:
November 26, 2000 02:18
Subject:
Re: Math::BigInt* (2)
Message ID:
20001126111818.C21493@engelschall.com
Hello John Peacock, in a previous mail you wrote:

> The big issue I saw with the current Math::BigInt was that the data was 
> stored as an array of string and converted to and fro everytime anything
> was 
> done, not just when stringifying.  String ops are typically vastly
> slower 
> than integer ops (from the hardware standpoint).  I have forgotten too
> much 
> math theory to argue O(N) vs O(log N).  I just know that stringify at
> each
> step is VERY SLOW!!!!

Although using base 100,000. to represent numbers is a clever trick,
using strings to hold them is probably a major speed killer.
This is why I prefer a two's complement binary representation in a
native machine data type, which moreover can take advantage of machine
operations for all calculations carried out.
This is exactly what Bit::Vector (and hence Math::BigIntFast) does.

> I was planning on making the Math::BigInt datatype stored as an array of 
> Bit::Vector (machine word in length), but I was having some

This would be very inefficient because it would multiply the administrative
overhead by a large factor. Bit::Vectors already ARE arrays of machine words!

> implementation
> doubts with whether I should used signed vs unsigned, since Mr. Beyer
> was kind enough to provide routines to handle carries but only with
> unsigned
> ints.

Sorry, but you are mistaken here.

Most (basic) operations work for unsigned as well as for signed numbers,
since we are using two's complement binary representation, where it doesn't
make a difference whether you add or subtract a signed or an unsigned number!
Only the handling of the carry and overflow bits (= boolean return values)
after the operation in your code differs.

Operations like multiplication and division assume signed numbers, but:
If your numbers are unsigned and may have the most significant bit set,
simply make your bit vectors one bit larger (using Resize() at runtime,
if necessary, or better, right from the start when designing your code).

> I think that the overhead of splitting out the sign and carrying 
> that along with the array of vectors would outweigh the additional math
> needed.

No necessity to do such a thing. See above!

> You might think I was being overly cautious, but I had people write me
> after I released Math::FixedPrecision complaining that they could not
> add two numbers on the order of 10**100!  I wanted to make sure that
> there
> was no instance which could cause an overflow, even if it was ludecrous
> data that was being used.

By the way, using floating point representation in BigInt math is counter-
productive: After all, people are using BigInt math for the larger range
of numbers WITHOUT LOSS OF PRECISION!

Any fixed-length mantissa will inevitably eventually cause precision losses,
and a variable-length mantissa is unnecessary because you could simply use
larger integers in the first place!

> My complaints about M::BI go for M::MF as well.  It seems wasteful to 
> store the data as a string (with exponent) and then stringify at every
> opportunity.  I was planning on a structure of MANTISSA being a M::BI 
> variable and EXPONENT being just a number.  

Please see my comment immediately above.

> > One more comment: Mark Biggar (original author), liked the idea of a
> > Perl only version, even if there is a C version.
> 
> I agree, which is why I hoped to make M::BI use Bit::Vector if it was
> there, otherwise fall back on Perl-only.

Sounds like the optimal strategy to me.

Best regards,
-- 
    Steffen Beyer <sb@engelschall.com>
    http://www.engelschall.com/u/sb/whoami/ (Who am I)
    http://www.engelschall.com/u/sb/gallery/ (Fotos Brasil, USA, ...)
    http://www.engelschall.com/u/sb/download/ (Free Perl and C Software)



nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About