Re: [boost] Infinite precision integer draft

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-05-31 12:28:25

"Andras Erdei" <aerdei_at_[hidden]> wrote in message
news:7fe28deb0605310758v59be5dbex545b04a8f7a08ce3_at_mail.gmail.com...
> 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.

For a portable implementation we can
use unsigned int 32-bit access, and use the
64-bit unsigned long long or unsigned __int64
and use these to have a 32-bit additive
or multiplicative carry.
This assumes of course that a 32-bit and 64-bit
unsigned are available, which must be checked
somehow during compilation.
This is of course slower than assembler.

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

The requirement is only that the sign and the binary
representation of the absolute value are stored separately
so that bit access (get_sub) has uniquely defined behaviour.
So the binary representation will never be negative.
Indeed this restricts the range of representations to this one.

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