Opened 5 years ago

Closed 5 years ago

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

Reported by: Owned by: mkoeppe major sage-8.0 geometry thursdaysbdx novoselt, tscrim, vbraun, vdelecroix, tmonteil, jipilab Matthias Koeppe Sébastien Labbé N/A 76cd1ea 76cd1ea370076c04901fe331760839d6c0166cf4

### Description

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

### comment:1 Changed 5 years ago by slabbe

• Branch set to u/slabbe/21993
• Commit set to bb912600c0f96279db35b7d93664cbd5d2be72f0

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

New commits:

 ​bb91260 `21993: int -> long`

### comment:2 Changed 5 years ago by mkoeppe

• Milestone changed from sage-7.5 to sage-8.0

### comment:3 Changed 5 years ago by mkoeppe

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.

### comment:4 Changed 5 years ago by mkoeppe

• Branch changed from u/slabbe/21993 to u/mkoeppe/21993

### comment:5 Changed 5 years ago by mkoeppe

• Authors set to Matthias Koeppe
• Commit changed from bb912600c0f96279db35b7d93664cbd5d2be72f0 to 76cd1ea370076c04901fe331760839d6c0166cf4
• Status changed from new to needs_review

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`

### comment:7 Changed 5 years ago by slabbe

• Reviewers set to Sébastien Labbé
• Status changed from needs_review to positive_review

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):)