Opened 3 years ago
Closed 2 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
- Branch set to u/slabbe/21993
- Commit set to bb912600c0f96279db35b7d93664cbd5d2be72f0
comment:2 Changed 2 years ago by
- Cc tmonteil added
- Milestone changed from sage-7.5 to sage-8.0
comment:3 Changed 2 years ago by
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 2 years ago by
- Branch changed from u/slabbe/21993 to u/mkoeppe/21993
comment:5 Changed 2 years ago by
- Commit changed from bb912600c0f96279db35b7d93664cbd5d2be72f0 to 76cd1ea370076c04901fe331760839d6c0166cf4
- Status changed from new to needs_review
comment:6 Changed 2 years ago by
- Cc jipilab added
comment:7 Changed 2 years ago by
- 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 2 years ago by
- Keywords thursdaysbdx added
comment:9 Changed 2 years ago by
- 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.
Do you have a doctest to propose that takes less time to run?
New commits:
21993: int -> long