-------- Original Message -------- Subject: Re: [PPL-devel] PPL: Problem with Checked-Ints Date: Tue, 20 Feb 2007 11:00:41 +0100 From: Didier Lime Didier.Lime@irccyn.ec-nantes.fr To: Roberto Bagnara bagnara@cs.unipr.it References: 9F1730A5-0443-4D9A-B958-C33EC329191C@irccyn.ec-nantes.fr 45DA0CEF.8040107@cs.unipr.it

Dear Roberto,

First, thanks your for quick and thorough answer!

I have checked. The overflow is genuine: the statement `cout << P << endl;' checks whether `P' is empty in order to print `false' in case it is. To do so, it calls a conversion routine that, at some stage, multiplies 46342 by 46341, and this gives an overflow on 32-bit integers (46342*46341 = 2147534622 > 2147483647).

OK. I had not anticipated this kind of operations, especially since in my particular application, coefficients are supposed to always decrease.

I guess I should be using arbitrary length integers anyway! But for now, I will take my chance with 64 bit checked integers (they should still be more efficient even on 32 bit computers).

...

I hope it is not just a misuse from me... Please ask if you need some more information.

I think your surprise is due to the PPL internal computations: your problem does no seem to have big enough coefficients to justify an overflow with 32-bit integers, but in fact it has.

Indeed! 46342 does not sound like big when dealing with 32 bit integers (though I now understand it actually is!)

A few further annotations: I had to change two `using' directives in your program so as to read

using namespace Parma_Polyhedra_Library;
using namespace Parma_Polyhedra_Library::IO_Operators;

OK. I actually got lazy when typing my sample code (and PPL seemed OK when browsing the source code of the library).

If you change the output statement to

cout << P.constraints() << endl;

the conversion routine is not called and you will see the right result being printed.

If I remember well, in the real application, I had this overflow in remove_space_dimensions (in the conversion routine called by some minimize function, if I remember my stack frames correctly). Maybe due to the same emptiness test.

Note also that C_Polyhedron objects are significantly more efficient than NNC_Polyhedron objects: so, if you don't need to work with non-closed polyhedra (i.e., don't need strict inequalities) you may consider to use the former for efficiency.

Good idea but, in Romeo, I actually need those non-strict inequalities so this is not an option.

Finally, the new paper BagnaraHZ06TR (BibTeX enty below the signature) can give you other indications about how to best use the PPL.

Thanks again for your answer and more generally, I must say I do appreciate programming with this library. From my point of view, you have really done a great piece of work!

Best wishes,

Didier

-- Dr. Didier Lime Maître de Conférences IRCCyN / École Centrale de Nantes Nantes, France

http://www.irccyn.ec-nantes.fr/~lime