[PPL-devel] [Fwd: Re: PPL: Problem with Checked-Ints]

[Roberto Bagnara]

-------- 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 at irccyn.ec-nantes.fr>
To: Roberto Bagnara <bagnara at cs.unipr.it>
References: <9F1730A5-0443-4D9A-B958-C33EC329191C at irccyn.ec-nantes.fr> <45DA0CEF.8040107 at 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




-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it