Polyhedron.integral_points(): OverflowError: value too large to convert to int

[mkoeppe]

I noticed the following bug in Sage:

sage: %timeit (Polyhedron(vertices=((0, 0), (1789345,37121))) + 1/1000*polytopes.hypercube(2)).integral_points()
...
/Users/mkoeppe/s/sage/sage-rebasing/yet/another/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in integral_points(self, threshold)
   4357                 box_points<threshold:
   4358             from sage.geometry.integral_points import rectangular_box_points
-> 4359             return rectangular_box_points(box_min, box_max, self)
   4360 
   4361         # for more complicate polytopes, triangulate & use smith normal form

/Users/mkoeppe/s/sage/sage-rebasing/src/sage/geometry/integral_points.pyx in sage.geometry.integral_points.rectangular_box_points (build/cythonized/sage/geometry/integral_points.c:6809)()
    552     v = vector(ZZ, d)
    553     if not return_saturated:
--> 554         for p in loop_over_rectangular_box_points(box_min, box_max, inequalities, d, count_only):
    555             #  v = vector(ZZ, orig_perm.action(p))   # too slow
    556             for i in range(0,d):

/Users/mkoeppe/s/sage/sage-rebasing/src/sage/geometry/integral_points.pyx in sage.geometry.integral_points.loop_over_rectangular_box_points (build/cythonized/sage/geometry/integral_points.c:7772)()
    601     while True:
    602         sig_check()
--> 603         inequalities.prepare_inner_loop(p)
    604         i_min = box_min[0]
    605         i_max = box_max[0]

/Users/mkoeppe/s/sage/sage-rebasing/src/sage/geometry/integral_points.pyx in sage.geometry.integral_points.InequalityCollection.prepare_inner_loop (build/cythonized/sage/geometry/integral_points.c:14134)()
   1256         """
   1257         for ineq in self.ineqs_int:
-> 1258             (<Inequality_int>ineq).prepare_inner_loop(p)
   1259         for ineq in self.ineqs_generic:
   1260             (<Inequality_generic>ineq).prepare_inner_loop(p)

/Users/mkoeppe/s/sage/sage-rebasing/src/sage/geometry/integral_points.pyx in sage.geometry.integral_points.Inequality_int.prepare_inner_loop (build/cythonized/sage/geometry/integral_points.c:10574)()
    938         cdef int j
    939         if self.dim>1:
--> 940             self.cache = self.cache_next + self.coeff_next*p[1]
    941         else:
    942             self.cache = self.cache_next

OverflowError: value too large to convert to int

(Note that this example would not get far with the code in Sage anyway because the code tries to use the rectangle bounding box method for all non-integral polytopes.)

CC: @novoselt @tscrim @vbraun @videlec @sagetrac-tmonteil @jplab

Component: geometry

Keywords: thursdaysbdx

Author: Matthias Koeppe

Branch/Commit: 76cd1ea

Reviewer: Sébastien Labbé

Issue created by migration from https://trac.sagemath.org/ticket/21993

[seblabbe]

comment:1

Do you have a doctest to propose that takes less time to run?

---

New commits:

bb91260

21993: int -> long

[seblabbe]

Branch: u/slabbe/21993

[seblabbe]

Commit: bb91260

[mkoeppe]

comment:3

I don't think this is the correct fix -- after all, Inequality_int is supposed to be a fast implementation for the case that everything fits in an int. Just checking it (in Inequality_int.__cinit__) seems buggy.

[mkoeppe]

Changed branch from u/slabbe/21993 to u/mkoeppe/21993

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

Changed commit from bb91260 to 76cd1ea

[mkoeppe]

comment:5

Here's a fix (with doctest) for the actual bug.
Needs review.

---

New commits:

773c43a	#21993: Add doctest
76cd1ea	#21993: Fix test for possible overflow during enumeration

[seblabbe]

comment:7

It works. The command

sage: %timeit (Polyhedron(vertices=((0, 0), (1789345,37121))) + 
....: 1/1000*polytopes.hypercube(2)).integral_points()

now takes forever (without error in the first minutes):)

[seblabbe]

Reviewer: Sébastien Labbé

[seblabbe]

Changed keywords from none to thursdaysbdx

[vbraun]

Changed branch from u/mkoeppe/21993 to 76cd1ea