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-02 18:04:00

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;

The type of d should be something like fixed_ponit<13,5>. If the 
pixed_point operation works only with parameters with the same range and 
resolution the overflow problem appears on temporaries.
Using cast the expression result in something unreadable

auto d = (fixed_ponit<13,5>(a) + fixed_ponit<13,5>(b)) * 
fixed_ponit<13,5>(c);

Overflow and rounding is needed only when you assign types with 
different quantizations. For example

fixed_point<12, 4> d = (a + b) * c;

will need to round from 5 to 4 resolution bits and to reduce the scale 
from 13 to 12.

>
>
>> It seems to me that fixed precision and allocation are orthogonal 
>> features. Why the fixed precision types can not use an allocator?
>
> Good question.  It seemed to me that the most common use case for 
> fixed precision types was for types "just a bit wider than long long", 
> where it was important not to be allocating memory.  Plus if you're 
> going to allow memory allocation, wouldn't it be safer to use the 
> arbitary precision type and avoid the risk of overflow altergether?
Knowing the range and resolution (i.e. precision) at compile time is a 
must in some domains. In the context I could use this, I will not use 
the allocator as the size stay reasonale, but for me the interface 
should let the choice to the user.
>
>
>> I'm working on a fixed_point library (see the sandbox code, sorry, 
>> but there is no doc yet but 
>> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html is 
>> quite close ).
>
> That paper is interesting, particularly in it's allowance of 
> mixed-mode arithmetic.
>
>> I would like to see if your front-end could also improve the 
>> performances in this case. I will try to adapt it to the back-end 
>> constraints soon.
>
> Unless your number types perform memory allocation, the chances are 
> that expression templates may well not be an optimization (or even a 
> slight dis-optimization).  Even when memory allocation is performed 
> and temporaries are expensive to construct, subjectively, the big 
> performance gains only really happen when the system is under load - 
> makes sense when you think about it - not sure how to go about 
> quantifying that though :-(
are you saying that the front_end is not useful for cpp_int when no 
allocator is used?

Note also that some processors could offer intrinsics for (a + b) * c. 
But this may be out of the scope of your library.

> BTW, it's not documented, and may be slightly out of date now, but 
> there's a trivial adapter template in 
> boost/multiprecision/arithmetic_backend.hpp that allows any type with 
> the usual arithmetic operators to be used with the expression template 
> front end, so use would be:
>
> mp_number<arithmetic_backend<YourType> >
>
> It certainly won't give you optimized performance, but it may give you 
> a quick and dirty idea as to whether writing a proper backend is 
> worthwhile.
>
>
I'll think a little bit more on how and if expression templates could 
improve the performances of fixed_point arithmetic that don't use memory 
allocation.

I'll study your expression templates work to see if adapting it to mixed 
range+resolution could be an option.

Best,
Vicente