Re: [boost] Infinite precision integer draft

From: Andras Erdei (aerdei_at_[hidden])
Date: 2006-05-31 10:58:34

On 5/30/06, Rene Rivera <grafik.list_at_[hidden]> wrote:

> > const integer get_sub( size_type startbit, size_type nbits ) const;
> > Complexity: O(N)
>
> There are a few problems with using those for "binary" access:
>
> * It is not optimal. Using the above would result in an O(N^2) algo for
> something that most of the time would be an O(1) operation (depending on
> the internal representation, at worse would be O(N)).
>
> * The representation that get_sub, highest_bit, lowest_bit, operate on
> is not defined. I don't see such a definition in the document either,
> AFAICT. So one couldn't even use the faster "int x =
> to_int(I.get_sub(0,16));"
>
> I don't care that much what the form of access looks like. The important
> aspect is having a *defined representation* that users can convert to
> and from. For example other access methods might be:

What can that defined representation be?
I think it's the same question as: How would one represent an integer
internally?
(Earlier in this thread you mentioned that you would like to have this kind
of access for performance reasons: eficiently implementing operations
not supported by a stock integer.)

For a high performance assembly implementation on an intel uP it can be a
block of 32 bit words.

For a resonably portable C++ implementation targeting the same uP it would
be the same, except that only 31 bits are used, because in C(++) you do not
have access to the carry flag, so you pay with memory for speed.

Chosing any of these as the standardized one would force the other to
create an O(N) interface for your "implementation access".

If your operations are complex enough, and you can live with the above
O(N) functions, let's go further:

How about a negabinary (base -2 instead of base 2) representation?
How about a non-binary representation with O(M(N)*logn(N)) access?
How about a non positional representation with O(N^3) access?

Either you seriously restrict the range of representations, and possibly
render the best ones non-standard, or you end up with an "implementation
access" that is unusable for your purpose.

// Iterators, like std::string::data:
> std::pair<word_type const *, word_type const *> integer::data() const;

This also raises memory handling issues: i suppose the pair would contain
an begin and an end pointer -- who would own the memory? What about
integers with user-defined allocators?

br,
andras