Re: [boost] [Review Request] Multiprecision Arithmetic Library

Subject: Re: [boost] [Review Request] Multiprecision Arithmetic Library
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2012-04-03 16:30:46

Le 03/04/12 20:07, Andrii Sydorchuk a écrit :
> On Tue, Apr 3, 2012 at 1:13 PM, Neal Becker<ndbecker2_at_[hidden]>  wrote:
>
>> Vicente J. Botet Escriba wrote:
>>
>>> Le 02/04/12 10:53, John Maddock a écrit :
>>>>> I'm wondering if the following compiles and what is the type of c
>>>>>
>>>>> mp_uint128_t a;
>>>>> mp_uint256_t  b;
>>>>> auto c = a + b;
>>>>>
>>>>>  From the documentation I have the impression that we can not mix
>>>>> back-ends.
>>>> Correct, it's a compiler error.
>>>>
>>>> Allowing mixed type arithmetic opens up a whole can of worms it seems
>>>> to me, plus I don't even want to think about how complex the operator
>>>> overloads would have to be to support that!
>>>>
>>>> So for now, if you want to conduct mixed arithmetic, you must
>>>> explicitly cast one of the types.
>>> Humm, casting seems to be not the good option for fixed point
>>> arithmetic. The type of a fixed_point operation depends on the
>>> quantization of its arguments.
>>>
>>> With fixed_point arithmetic the type of fixed_point<7,0>  +
>>> fixed_point<8,0>  is fixed_point<9,0>. Note that no overflow is needed as
>>> the resulting type has enough range.
>>>
>>> Another example
>>>
>>> fixed_point<10,2>  a;
>>> fixed_point<2,3>  b;
>>> fixed_point<2,2>  c;
>>> auto d = (a + b) * c;
>>>
>> I have implemented my own fixed_point, and I debated whether the result of
>> operations should automatically be a wider type.  In the end, I decided it
>> was
>> best to use explicit casting.  Explicit is better than implicit.  It's a
>> bit
>> more verbose, but I can live with that.
>>
>> Would you advocate that in C++, int8 * int8 ->  int16??
>
> I would say that the result of the expression should not grow
> automatically. Consider example of summation of 1000 int32.
> The result value would have 1031 bits size, while the actual value it holds
> would be at most int42.
Well all this depends on how you write the summation. Just note that

int32+int32+int32+int32+int32+int32+int32+int32

could be written as

((int32+int32)+(int32+int32))+((int32+int32)+(int32+int32))

and in this case has type int35 instead of int39.

This is where maybe expression templates could help.
> There is also another template trick that allows resulting type to be at
> least as big as each of the operands:
>
> template<int N, int M>
> big_int<(N>M?N:M)>  add(const big_int<N>&  a, const big_int<M>&  b) {
>    big_int<(N>M?N:M)>  result;
>    // Implementation follows.
>    return result;
> }
> I used this approach for my personal fixed int routines.
>
> The main point of a fixed integer type is its performance. It allows user
> to write complex math formulas without thinking about slow memory
> allocations.
I agree. My library doesn't provide arbitrary ranges, so at the end I 
need to fix a bound. What is the result type of operator+ on this upper 
bound range? Currently the compiler fails. I will explore your idea to 
saturate the result range to this upper bound. Note that operator+= do 
already something similar in my library, but the user needs to know 
which has the larger range.
> I would say that users are responsible to ensure that fixed int doesn't
> overflow. If somebody is not satisfied with such behavior they could
> use big integer types with dynamic memory allocation.
I agree that the user must master overflow. This doesn't means that the 
library can not help him to make the good decisions. My fixed_point 
class has a overflow template parameter that the user can set to ignore 
when is know that overflow can not occur. See example below.

I recognize that writing a loop summing 1000 int32 (when the result of 
the operator+ grows is not so evident). The question is what would be 
the range of the result.

   fixed_point<32,0> v[1000];
   fixed_point<range,0> sum;
   // ...
   for (int i=0; i<1000;++i)
     sum+=v[i];

When the size of the vector is know at compile time range is around 
log2(1000)+32 in this case. A library could provide a meta-function 
giving the correct type as for example

   accumulate<fixed_point<32,0>, 1000 /*times*>::type sum;

The problem with the previous code is that overflow will be check at 
every addition. With the ignore overflow template parameter
   std::array<fixed_point<32,0>,1000> v;
   fixed_point<range,0,overflow::ignore> sum;

A less friendly function could also be used to request no overflow check

   for (int i=0; i<1000;++i)
     sum.add(no_overflow_check,v[i]);

Note that the library could check for overflow however in debug mode.

If the size of the collection is know only at run-time, you will need to 
use a compile time size and overflow checking will manage the issue.

   std::vector<fixed_point<32,0>> v;
   fixed_point<64,0> sum;
   // ...
   for (int i=0; i<v.size();++i)
     sum+=v[i];

I hope this answers to your argument against arithmetic operators 
growing automatically the range of the result.

Best,
Vicente