Re: [boost] [xint] Boost.XInt formal review

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Ivan Sorokin (sorokin_at_[hidden])
Date: 2011-03-05 18:10:50

On 02.03.2011 13:58, Vladimir Prus wrote:

I believe that arbitrary precision arithmetic library is very useful. 
But I don't think that in it's current status XInt is appropriate for boost.

Below is the list of features which I believe should be improved. The 
list is sorted by importance.

1. Parametrize with container type.

Currently the library uses several options like fixedlength, secure, 
threadsafe, etc. I am sure it would be better to add template parameter 
"container" to integer_t. The container will take care about how to 
store data. So one can have
* integer_t<std::vector> (for generic implementation),
* integer_t<boost::array> (for fixed-length),
* integer_t<vector_fixed_capacity>,
* integer_t<very_secure_vector> (for very secure arithmetic),
* integer_t<copy_on_write_vector> (if one want copy on write optimisation)
* etc

This solution requires the container interface to be extended through 
global functions(see below), but I think that finally we get very 
extensible and easy to use integer_t.

For example:

xint::push_back is used in operator+ and operator- when we need to add 
most significant digit.
* for std::vector it does simple push_back
* for boost::array it may do nothing (silent overflow behavior) or throw 
an exception (if we don't want overflow to happen)

xint::trim is used when we need to trim most significant zeros.
* for std::vector it does resize
* for boost::array it does nothing

Another option could be wrapping containers into some entity with 
interface suitable for integer_t needs.

One more thought about "secure" option. There are no standard containers 
with this option. I think either both standard containers and integer_t 
should have such option or both shouldn't have. This is yet another 
argument for container parametrization.

2. Signed Zero.

I'm sure that long integer arithmetic should behave as close to native 
integer numbers as possible. Native integer types don't have negative 
zero. As the documentation mentions, this is done "for use in a planned 
future unlimited-precision floating point library". Although the only 
function that behaves differently on negative and positive zero is 
sign(true), I still believe that this is redundant and planned floating 
point library should use it's own sign bit.

3. Alternative representation of negative numbers

Currently integer_t supports bit arithmetic, but its result differ from 
one of native integer types:

template <typename Integer>
void f()
{
     Integer a = 1;
     Integer b = -1;

     std::cout << a << " " << b << " " << (a ^ b) << std::endl;
}

f<boost::xint::integer>() prints

1 -1 0

But f<int>() prints

1 -1 -2

I propose the following solution. Currently integer_t stores the sign 
bit and value bits (absolute value). Instead of the sign bit let 
integer_t hold a bit "inverse_value" with the following meaning:

True inverse_value means that all "value" bits are inverted. Even bits, 
higher than the most significant value bit.

For example: We want to represent -3 (decimal):

binary representation for -3 is "...111...101" (unlimited number of 1 in 
high bits), it corresponds to setting inverse_value bit to 1 and 
inverting all representation value bits, that is "...000...010" or 
simple "10".

So
* for negative number inverse_value is set to 1, and container store its 
bitwise not,
* for positive number inverse_value is set to 0, and container store its 
value as is.

The implementation of addition and subtraction for this representation 
is not more complicatedthan for current one. But it allows bit 
arithmetic to work in the same fashion as it works with native integer 
types.

4. About options naming.

The option name "threadsafe" is misleading as it implies something about 
concurrency. Instead it means just disabling copy-on-write. So I think 
it's better to rename it to something like "no_copy_on_write" or 
"copy_on_write<false>" or something like that.

xint::nothrow_integer really is "xint::integer or nan". Maybe the name 
that reflects "integer or nan" representation is better?