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