Re: [boost] Infinite precision integer draft

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-05-30 17:19:25

"Rene Rivera" <grafik.list_at_[hidden]> wrote in message
news:447CACE0.20907_at_redshift-software.com...
> 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 get_sub of one bit or byte is O(1), but as the
maximum is the whole integer, it is specified as 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));"

The representation is a sign and the binary
representation of the absolute value.
That is what is mentioned in the design decisions.
But now I will add it as a requirement, because
indeed otherwise get_sub is undefined.

>
> 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.

But what should the iterator iterate over?
Bits? Bytes?
In my opinion get_sub of a bit or byte or whatever,
with a converter like to_unsigned_int, gives you the
O(1) access you require.
Perhaps the user can define an iterator
based on get_sub.
As mentioned I will add to the requirements that
the sign and the binary representation of the
absolute value should be stored separately,
which defines the behaviour of get_sub.
Is this what you require?

>
>
>
> -- 
> -- 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
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>