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

On Fri, 1 Jun 2012, John Maddock wrote:

...

...

* 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.

rvalue references and move semantics are already supported.

You have a move constructor, but I haven't seen anything like: number operator+(number&& a, number const&b){return move(a+=b);} which would bring the number of allocations down to 1 for types with a good move constructor (I may have missed it, I can't easily test anything these days). (returning a number&& is tempting, especially for types with a bad move constructor, but is not very safe)

Nod. Support for fused multiply-add is on my TODO list.

;-) My point was actually that FMA shouldn't have anything special. What makes it interesting in GMP is that malloc is replaced with alloca for the temporary. Otherwise, it is a plain mul and add. The same optimization could just as well have been done for addadd (a+b+c) instead. With expression templates, there should be enough information to do that for any combination, not just a+b*c. It may get quite complicated though, and not so useful for a backend like cpp_int. What happens when you try to mix numbers, say z+q where z is an integer and q a rational? I imagine that z is converted to a rational and the user can't provide an optimized version of the operation (maybe for a future version?). -- Marc Glisse

On Sat, 2 Jun 2012, Vicente J. Botet Escriba wrote:

Le 02/06/12 18:24, Marc Glisse a écrit :

...

You have a move constructor,

I've missed it. Please, could you point me where it is defined

Look for BOOST_NO_RVALUE_REFERENCES in http://svn.boost.org/svn/boost/sandbox/big_number/boost/multiprecision/mp_nu...

and documented?

Does it need to be? mp_number is documented as copy constructible, and the move constructor is just an optimization. -- Marc Glisse

On Sun, 3 Jun 2012, Vicente J. Botet Escriba wrote:

Le 03/06/12 00:10, Marc Glisse a écrit :

...

Does it need to be? mp_number is documented as copy constructible, and the move constructor is just an optimization.

Well, I think so. It is an optimization that follows a given protocol, e.g. the use of std::move and std::forward. If no documented we can not use these functions, or can we?

Uh? Copying from a prvalue (say, a temporary) will automatically use that function instead of the regular copy constructor. You can also force its use by making an xvalue (move), but that's secondary.

In addition the backend developers should be aware of this.

Hmm, maybe you're right, it is an optimization of the copy constructor, but it can make sense to let developers know that if they provide it, it will be used. -- Marc Glisse

On Fri, 1 Jun 2012, John Maddock wrote:

Support for fused multiply-add is on my TODO list.

Consider the case of modular arithmetic, where you use an int64_t to do the operations, and then reduce modulo some 30 bit prime number. When you perform many operations in a row, it is interesting to avoid computing the modulo every time but only do it often enough that there won't be an overflow. FMA is a special case where it will remove one modulo. But in a sum of a dozen numbers, you would want a single modulo at the end. Expression templates should be able to help, but I guess this is a wrong fit for this library (which is completely fine, I just thought I'd mention it). (in the special case where we compute modulo 2^30 instead of a prime number, and use an uint32_t for the computation, a finalization function would be enough) --------- I just had a look at the updated introduction, and I realize I said something wrong about the example with 11 temporaries: the optimization to get 0 temporary in gmp-5.1 is only for mpz and mpq, not mpf. Sorry for the misunderstanding. I may try to add the same optimization for mpf some time (mixed precisions give me headaches when I try to handle that code), but that's not really a plan. -- Marc Glisse

On Thu, May 31, 2012 at 5:31 PM, Marc Glisse <marc.glisse@inria.fr> wrote: [...]

On Thu, 31 May 2012, John Maddock wrote:

[...]

* 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.

I want to echo Marc's comment that algorithms and numeric types where you only perform ring operations are common in computational geometry. You can often bound the size of your expression tree (as a function of your spatial dimension), hence bound the size of your rationals. It might be worth considering this application within the scope of (proposed) Boost.Multiprecision. Indeed, I've used a C++ implementation of Jonathan Shewchuck's exact arithmetic algorithms [1] for such purposes. [1] http://www.cs.cmu.edu/~quake/robust.html - Jeff

On Tue, Jun 5, 2012 at 10:06 AM, John Maddock <boost.regex@virgin.net>wrote:

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.

I want to echo Marc's comment that algorithms and numeric types where you only perform ring operations are common in computational geometry. You can often bound the size of your expression tree (as a function of your spatial dimension), hence bound the size of your rationals. It might be worth considering this application within the scope of (proposed) Boost.Multiprecision. Indeed, I've used a C++ implementation of Jonathan Shewchuck's exact arithmetic algorithms [1] for such purposes.

[1] http://www.cs.cmu.edu/~quake/**robust.html<http://www.cs.cmu.edu/%7Equake/robust.html>

OK, clearly it's not a field I'm familiar with - for that reason I'd prefer not to be the one to write a backend for that - or at least I would need some considerable help - but I see no real obstacles to supporting such a type providing you don't want the transcendental functions. If someone were willing to be the guinea pig, then it might make a good test case for seeing how easy it is for someone other than me to extend the library?

This is something I would be willing to contribute but probably not until after the formal review. - Jeff

On Tue, Jun 5, 2012 at 10:26 AM, John Maddock <boost.regex@virgin.net>wrote:

OK, clearly it's not a field I'm familiar with - for that reason I'd

...

...

prefer not to be the one to write a backend for that - or at least I would need some considerable help - but I see no real obstacles to supporting such a type providing you don't want the transcendental functions. If someone were willing to be the guinea pig, then it might make a good test case for seeing how easy it is for someone other than me to extend the library?

This is something I would be willing to contribute but probably not until after the formal review.

Nod, thanks. Also just realized that while a simple adapter backend:

template <class BigInteger> class exact_float;

Would be more or less trivial as far as the arithmetic goes, other stuff like string conversion would be *much* more complex, exactly which conversions and/or string formatting should be supported would require some careful thought.

Yes, agreed regarding the trickiness of string conversions :( I guess if one doesn't want or need to implement such facilities, one could just throw on such overloads. For many computational geometry applications, the inputs are built-in floating point types, which I would imagine would be trivially (or, at least, straightforwardly) convertible to the desired exact floating point type, so string conversion may not be necessary. - Jeff

...

On Tue, Jun 5, 2012 at 10:26 AM, John Maddock <boost.regex@virgin.net>wrote:

...

Also just realized that while a simple adapter backend:

template <class BigInteger> class exact_float;

Would be more or less trivial as far as the arithmetic goes, other stuff like string conversion would be *much* more complex, exactly which conversions and/or string formatting should be supported would require some careful thought.

Yes, agreed regarding the trickiness of string conversions :( I guess if one doesn't want or need to implement such facilities, one could just throw on such overloads.

Actually, one could see it as a weakness of the library that so many of the requirements are compulsory and not optional.

Actually, there isn't a huge list of compulsory requirements, and even then the term "compulsory" might need revising - maybe more like "non-synthesizable". So if you want all of mp_number's documented operations to work, then you need to implement all of the "non-synthesizable" requirements. However, for a type like a ring, you wouldn't implement eval_divide even though it's one of the "compulsory" requirements - the result would be that the divide operator for mp_number<my_ring> wouldn't instantiate, but everything else you've implemented would. John.

...

...

...

* 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.

This is why creating generic libraries is hard. mp_number is a generic class that should provide whatever implicit/explicit constructor the backend supports. I expect enable_if to allow to define such interface. I'm not saying I have a complete solution already. In general, I will not provide implicit conversions when there is a lost of information. Whether this is a major feature for your library is something we can discuss.

<snip>

...

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 have no experience with Boot.Math, but I suspect that there are cases where these implicit conversions are not desired, e.g when information is lost.

I understand.

...

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.

This is my opinion. Others will have different opinions.

I suspect that I need to see how Boost.Math works :-) Best, Vicente

As far as I know, when you use Boost.Math with any properly wrapped big-float type, the templates expect seamless interaction between the wrapped floating-point type and all built-in data types such as char, short, int, float, double, etc. Now as far as a potential Boost.Multiprecision is concerned, I would recommend that whatever Boost.Math needs for floating-point types should be satisfied by Boost.Multiprecision. Narrowing conversions of built-in floating-point types and big integers do not arise in Boost.Math (as far as I know). And there have been some comments suggesting to forbid these in Boost.Multiprecision. I suspect we can sort all of this out in the review. But my initial feeling is that we have Boost.Multiprecision in a relatively *boost-compatible* state because we have thousands of tests already based on Boost.Math. We will sort this out in review, I hope. Thanks again, Vicente. Best regards, Chris.