Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk