Hello, boost-request.

Date: Mon, 07 May 2007 17:19:36 +0100 From: "Phil Endecott" <spam_from_boost_dev@chezphil.org> 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@gmail.com