Re: [boost] Infinite precision integer draft

From: Rene Rivera (grafik.list_at_[hidden])
Date: 2006-05-30 16:36:48

Maarten Kronenburg wrote:
> Rene,
> In the meantime the get_sub has been
> added for bit access, see below.

Yes, I saw that before I sent the email. Hence I don't think it's 
sufficient.

> This is not an iterator, but it may be
> sufficient for access of the binary
> representation.
> Is this also usefull for you?
> 
> size_type highest_bit() const;
> Complexity: O(N)
> 
> size_type lowest_bit() const;
> Complexity: O(N)
> 
> 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:

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

// Inserter, like std::string::copy:
template <typename OutputIterator>
void integer::copy(OutputIterator) const;

// Stream like:
template <typename Container>
operator << (Container &, integer const &);

Of course there would need to be a corresponding constructor to have the 
data round trip.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo