Re: [boost] [review] Multiprecision review scheduled for June 8th - 17th, 2012

Subject: Re: [boost] [review] Multiprecision review scheduled for June 8th - 17th, 2012
From: Marc Glisse (marc.glisse_at_[hidden])
Date: 2012-05-31 20:31:17

By the way, I should probably have started by this:

I am commenting because this library looks very interesting, and I highly 
encourage you to continue.

On Thu, 31 May 2012, John Maddock wrote:

>> * the version of gmpxx in the repository hasn't used any temporary for the 
>> example given in the introduction for a while, it is only because of a slow 
>> release cycle that you haven't seen it yet (will be in 5.1).
>
> OK.  I guess the problem with such comparisons is they're out of date as soon 
> as they're written.

Or even before... I know, that's a pain.

>  I can only test what's been released though.

So you can't test your own code? ;-)
(gmp's repository is public)

>> * the example about using 0 vs 11 temporaries doesn't mention what happens 
>> to the boost package if we disable expression template. Does it use a 
>> single temporary (using rvalue-references) or plenty?
>
> Plenty, haven't measured how many, but I'd expect it to be the same as for 
> mpclass.  I guess I should cover that.

I think you really want to investigate using rvalue references, in that 
case. Which reminds me: there is some overlap with boost/operators.hpp (I 
heard someone was rewriting it?), so the rvalue reference techniques could 
be the same, and the documentation could say something about the relation 
between the 2.

>> * you could get good results with a backend that uses gmp's mpn_* functions 
>> but not the mpz_t type.
>
> Maybe, but I'm not sure what that gains us other than memory allocation 
> control?
>
> It seems to me that we would basically be re-inventing the mpz_* gmp 
> functions, which seems like a bad idea.

For large numbers, the cost of operations dominates, and gmp is hard to 
beat. For small numbers, allocation dominates the cost. mpz_t is quite bad 
there as it always allocates. Even default and move constructors can't be 
efficient with mpz_t for that reason.

Things like your mixed backend (fixed allocation for small sizes and 
dynamic for larger sizes) are very interesting. I am also wondering about 
the possibility to use a different type for temporaries. As much as 
possible, you'd want to avoid allocation for temporaries, using fixed 
arrays or even alloca/VLA where available. But that doesn't mean your 
number type itself should contain an array. gmp's addmul function (kind of 
like FMA) should be useless, but it is actually interesting because it 
bypasses the allocation for the intermediate result, which makes it fast.

So there is quite a bit of potential there. But that's just a suggestion, 
it doesn't have to be done now, or by you.

>> * what about infinite precision floats? By that I mean something like 
>> bigint*2^n, where operations + - * are computed exactly. It can be quite a 
>> bit faster than rationals, when it is sufficient.
>
> Wouldn't those get horribly large very quickly?

You can see them as a special case of rationals where the denominator is 
always a power of 2, so they grow more slowly than rationals.

> Off hand I know of no other library that implements such a beast?

CGAL. If you want to evaluate exactly the sign of a polynomial of double, 
your best bets are this or a sum-of-double representation, depending on 
the degree.

>> * if I want reference-counting, I guess that should be done in a back-end.
>
> That's a touchy subject ;-)
>
> Reference counting seems to have gone out of favor in recent years for 
> "string like objects" on the grounds that it causes more issues than it 
> solves,

The more functionality you have, the more painful reference counting 
becomes. Strings have iterators. I expect numbers to be opaque.

> hunch is probably not much - purely because most operations are so dominated 
> by multiply and divide times that a small number of extra copies just doesn't 
> matter much (compared to say the massive number of temporaries you get 
> without expression templates).

It could be helpful for storage purposes, when the same number is stored 
in a number of places. Or for badly written code that copies things a 
lot :-(

On Thu, 31 May 2012, Christopher Kormanyos wrote:

>>> * having an implicit narrowing conversion from double to bigint is a bad idea,
>>> it should be explicit (it isn't completely obvious from the doc if that is the case).
>
>
>> It's pretty hard to have some constructor conversions implicit and others explicit.
>> Might be possible with enable_if though.  Will investigate.
>
> It's a good comment. You know, a third of the people want it
> one way, another third want it the other way and the others
> don't care.

I still think it is worth a try. I have already made the conversions 
mpf->mpq, mpf->mpz and mpq->mpz explicit in gmpxx, and I am considering 
doing it as well for double->mpz (I am a bit afraid of breaking some 
people's code though...). The implicit/explicit character of a conversion 
is useful for meta-programming. I have code where I receive a number of 
some unknown type, and if that number is implicitly convertible to 
mpz_class I'll use that and if not I'll use an mpq_class.

> In fact, I believe that Boost.Math already set the bar on this
> one because when using Boost.Math with an extended precision
> type (this is possible), all implicit conversions to/from the built-in
> types are supported.
>
> I believe it would be incorrect to treat interaction with built-in
> types behave one way in Boost.Math and a different way in a
> potential Boost.Multiprecision.

Isn't Boost.Math about floating point (I haven't used it so I don't know)? 
It makes sense to allow conversions from double to bigfloat but not from 
double to bigint...

-- 
Marc Glisse