Opened 3 years ago

Closed 3 years ago

#21993 closed defect (fixed)

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

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-8.0
Component: geometry Keywords: thursdaysbdx
Cc: novoselt, tscrim, vbraun, vdelecroix, tmonteil, jipilab Merged in:
Authors: Matthias Koeppe Reviewers: Sébastien Labbé
Report Upstream: N/A Work issues:
Branch: 76cd1ea (Commits) Commit: 76cd1ea370076c04901fe331760839d6c0166cf4
Dependencies: Stopgaps:

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

Change History (9)

comment:1 Changed 3 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:

bb9126021993: int -> long

comment:2 Changed 3 years ago by mkoeppe

  • Cc tmonteil added
  • Milestone changed from sage-7.5 to sage-8.0

comment:3 Changed 3 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 3 years ago by mkoeppe

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

comment:5 Changed 3 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:6 Changed 3 years ago by mkoeppe

  • Cc jipilab added

comment:7 Changed 3 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):)

comment:8 Changed 3 years ago by slabbe

  • Keywords thursdaysbdx added

comment:9 Changed 3 years ago by vbraun

  • Branch changed from u/mkoeppe/21993 to 76cd1ea370076c04901fe331760839d6c0166cf4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.