
Boost : 
Subject: Re: [boost] [Review Request] Multiprecision Arithmetic Library
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 20120403 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
>>>>> backends.
>>>> 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 metafunction
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 runtime, 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk