Re: [boost] Infinite precision integer draft

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-05-31 09:23:21

Rene,
Also I will change the complexity
of get_sub into:
O(1)-O(N) depending on the value of nbits
and add to the requirements:
The internal representation is such that
the sign and the binary representation of
the absolute value are stored separately.
This means that the bit access function get_sub
is sign independent
Regards, Maarten.

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