Re: What about big integers in Ada 2005?

[Robert A Duff <bobduff@shell01.TheWorld.com>]

clubley@remove_me.eisner.decus.org-Earth.UFP (Simon Clubley) writes:

> > I think the only reason to use BCD these days (instead of binary) is to
> > interface to something that uses BCD.  In the old days, another reason
> > was to avoid the cost of converting strings to binary integers and
> > vice-versa, but that seems like an obsolete reason at this 
> > 
> > Am I right?
> 
> How would you choose to implement big number packages ?

I have implemented such a thing, and I used all manner of low-level
trickery to make it efficient.  Of course what's "efficient" depends on
typical usage patterns, such as:

    1. Almost all numbers are small (fit comfortably in one machine
       word).

    2. Extremely large numbers are common.  Lots of arithmetic,
       comparisons, etc.

    3. Not so much arithmetic, etc.  Lots of conversions back and forth
       to human-readable text strings.

My scanario was number 1.  I won't go into all the details, but
basically a big int is a word, containing a small number, plus
some flag bits, or a pointer to a big number, plus some flag bits.
The pointer points to a heap-allocated array of "super digits".
Each super digit is half a 32-bit word.  In other words,
we're using base 2**16.

It would be more efficient to use base 2**32, but that would have
required non-portable machine code inserts or something, because Ada
doesn't give access to the necessary machine instructions (double-length
multiply, for example).

For scenario 2, I suppose the small-int hack would be a waste -- just
make it a pointer to the array.

For scenario 3, base 1_000_000_000 would be more efficient.
Or base 10_000, if you're doing the half-word thing.

I still don't see a really good reason to use base 10.

- Bob