Re: [boost] Boost::Bigint header draft - suggestions are welcome!

From: Arseny Kapoulkine (arseny.kapoulkine_at_[hidden])
Date: 2007-05-08 06:41:36

Hello, boost-request.

> Date: Mon, 07 May 2007 17:19:36 +0100
> From: "Phil Endecott" <spam_from_boost_dev_at_[hidden]>
> Subject: Re: [boost] Boost::Bigint header draft - suggestions are welcome!

> Looks good.  Some quick thoughts:

> - Have you considered conversions to/from floating-point?
Hmm, no. I'm putting it in the todo list, though this is not going to
be in the base part I think.

> - Have you considered using Boost.Operators?
Yes. Quoting discussion with my mentor:

>> See Boost.operators for a concept breakdown for Addable, Subtractable, etc.
> 
> I started working on the header draft, and looked at boost.operators.
> Am I correct if I say that they are not like traits (to be able to
> determine if a type can be added to another one, etc.), but instead
> provide implementation for all related operators if some basic ones
> are provided (+ if += exists, all comparison operators if < and ==
> exist, etc.)?
> 
> Because if that's true, the only thing I could use from it is the
> group of operators that relate to comparison.
> 
> The reason is simple - the suggested implementation for + in terms of
> +=
> (T nrv( lhs ); nrv += rhs; return nrv;)
> 
> is not as efficient as it could be even if compiler implements NRVO -
> this function still always has extra copy (T nrv(lhs)). I referred to
> it in my application btw. If I have a generic 3-register
> implementation of an operation (add(dest, src1, src2)), I can do the
> most efficient implementation.
> 
> My implementation for + could look like (or well, it already does :))
> 
>         bigint<I> result;
>         result.impl.add(lhs.impl, rhs.impl);
>         return result;
> 
> So it utilizes NRVO, but does not have extra copy if the
> implementation itself allows for it. So the call will have exactly the
> same overhead as the user might expect if he knows what implementation
> is used - there's no hidden overhead here, if the compiler implements
> NRVO of course. And this does not require a lot of extra work, I was
> planning to do 3-register implementations of every binary operation
> anyway.
> 
> As for <, <=, etc. - I don't see any benefit from boost operators for
> me either.
> 
> >= is implemented like this, for example:
> 
>         return lhs.impl.compare(rhs.impl) >= 0;
> 
> And this "compare" function is more or less the same as operator< in
> terms of implementation - not much harder.
> 
> Though perhaps here the situation is different - in theory, providing
> separate < and == allows the operations == and != be implemented
> faster (not that I'm planning to do it), than via compare() == 0 way.

So I guess the answer is - yes, I considered using Boost.Operators,
but the current decision is not to use them.

> - Are logical operations well defined for negative operands with 
> different numbers of bits? (e.g. -1 | 12345)  Also, what does ~ do?  
> Are different signed and unsigned types needed?
The semantics of logical operations for negative numbers is to be
defined, they will most likely work with negative numbers as the
2-complement of their magnitude (regardless of the underlying
implementation), either expanded at some amount of bits (max for bits
in both operands, perhaps more than that) or negative numbers will
just be treated as 2-complemented positive numbers with infinite
number of '1' as a sign extension (so about -1 | 5:
MSB first, LSB last

-1 is treated as 1...(infinite number)..1111
5 is treated as 0...(infinite number)...0101

Oring them produces

1..(infinite number)..1111

so that's -1

Xoring them produces

1..(infinite number)..1010

that's the complement for 101, so that's -5).

This will be outlined in the docs.

I don't think providing both signed and unsigned types is reasonable,
because without sign, special handling for underflows has to be
decided on, and generally I don't see 'unsigned bigint' as something
that should ever be used instead of 'signed' one.

> - I take it that this class dynamically allocated enough memory for the 
> value.  Can you quantify the performance penalty that this imposes 
> compared to declaring the number of bits in advance (e.g. bigint<256>) 
> and statically allocating that much memory?
'default' (pure C++ w/out third-party libraries)
implementation will be useful with any storage strategy (I will
include one based on std::vector, so it'll be possible to provide a
custom allocator, and a stack-based one with the specified maximum
number of bytes). 'gmp' one (based on GMP) is not customizable in this
way now, though this is a feature in a todo list for the second part
of the project (read: perhaps it will be implemented after all base
features are).

-- 
Best regards,
 Arseny                          mailto:arseny.kapoulkine_at_[hidden]