Opened 4 years ago

Last modified 8 days ago

#26957 needs_work defect

bug in polynomial real root (bis)

Reported by: Vincent Delecroix Owned by:
Priority: major Milestone: sage-9.8
Component: algebra Keywords:
Cc: ​cwitty, Marc Mezzarobba Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/chapoton/26957 (Commits, GitHub, GitLab) Commit: 3d9551de860522f6bb9ca1ada7905f8bdf669031
Dependencies: Stopgaps:

Status badges

Description (last modified by Vincent Delecroix)

A maximum recursion depth RuntimeError is obtained with

l = [1, 0, 3, 2, -1, 0, 1, 2, -2, 0, 0, 27, 1, -1, -1, 1,
     1, 0, -2, 1, 1, 1, -2, 0, -176, -3, -1, 116, 2, -1,
     0, 0, -2, 8, 8, 34, 3, 1, 0, -1, -6, 1]
p = ZZ['x'](l)
p.roots(AA)

The full traceback is

RuntimeError                              Traceback (most recent call last)
<ipython-input-303-35d8367cd398> in <module>()
      1 l = list(p)
----> 2 ZZ['x'](l).roots(AA)

/usr/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.roots (build/cythonized/sage/rings/polynomial/polynomial_element.c:62263)()
   7748 
   7749                 if is_AlgebraicRealField(L):
-> 7750                     rts = real_roots(self, retval='algebraic_real')
   7751                 else:
   7752                     diam = ~(ZZ(1) << L.prec())

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.real_roots (build/cythonized/sage/rings/polynomial/real_roots.c:44168)()
   4053 
   4054             oc = ocean(ctx, bernstein_polynomial_factory_ratlist(b), linear_map(left, right))
-> 4055             oc.find_roots()
   4056             oceans.append((oc, factor, exp))
   4057 

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.ocean.find_roots (build/cythonized/sage/rings/polynomial/real_roots.c:33037)()
   3069         """
   3070         while not self.all_done():
-> 3071             self.refine_all()
   3072             self.increase_precision()
   3073 

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.ocean.refine_all (build/cythonized/sage/rings/polynomial/real_roots.c:33332)()
   3114         while isle is not self.endpoint:
   3115             if not isle.done(self.ctx):
-> 3116                 isle.refine(self.ctx)
   3117             isle = isle.rgap.risland
   3118 

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.island.refine (build/cythonized/sage/rings/polynomial/real_roots.c:35647)()
   3367         self.shrink_bp(ctx)
   3368         try:
-> 3369             self.refine_recurse(ctx, self.bp, self.ancestors, [], True)
   3370         except PrecisionError:
   3371             pass

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.island.refine_recurse (build/cythonized/sage/rings/polynomial/real_roots.c:37473)()
   3515                         return
   3516                 else:
-> 3517                     self.refine_recurse(ctx, p1, ancestors, history, False)
   3518                     assert(self.lgap.upper == p2.lower)
   3519                     bp = p2

... last 1 frames repeated, from the frame below ...

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.island.refine_recurse (build/cythonized/sage/rings/polynomial/real_roots.c:37473)()
   3515                         return
   3516                 else:
-> 3517                     self.refine_recurse(ctx, p1, ancestors, history, False)
   3518                     assert(self.lgap.upper == p2.lower)
   3519                     bp = p2

RuntimeError: maximum recursion depth exceeded while calling a Python object

Other examples (one by line)

[-1, 7, -2, 6, -1, -16, 1, 3, -1, -1, -6, 10, 1, -3, 3, 1, 10, -1, 0, 1, 1, 1, 0, -1, 1, 4, -1, 1, 1, 158, -12, -1, 1, -1, 1, 1, 1, 3, 0, 2, 0, 2, -1, -1, 1, -1, 3, 1]

(See also #26955 for another bug)

Change History (18)

comment:1 Changed 4 years ago by Vincent Delecroix

Description: modified (diff)

comment:2 Changed 4 years ago by Erik Bray

Milestone: sage-8.6sage-8.7

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

comment:3 Changed 4 years ago by Erik Bray

Milestone: sage-8.7sage-8.8

Moving all blocker/critical issues from 8.7 to 8.8.

comment:4 Changed 3 years ago by Erik Bray

Milestone: sage-8.8sage-8.9

Moving open critical and blocker issues to the next release milestone (optimistically).

comment:5 Changed 3 years ago by Erik Bray

Milestone: sage-8.9sage-9.1

Ticket retargeted after milestone closed

comment:6 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.1sage-9.2

comment:7 Changed 2 years ago by Ben Livingston

Status: newneeds_review

Like its sister ticket (#26955), this appears to be fixed in Sage 9.2.beta12, if not earlier.

comment:8 Changed 2 years ago by Marc Mezzarobba

But #20390 is still present. Strange.

comment:9 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-duplicate/invalid/wontfix

comment:10 Changed 2 years ago by Samuel Lelièvre

Milestone: sage-duplicate/invalid/wontfixsage-9.2
Priority: criticalmajor

Please let's add a doctest.

comment:11 Changed 2 years ago by Samuel Lelièvre

Status: needs_reviewneeds_work

comment:12 Changed 2 years ago by Frédéric Chapoton

Branch: u/chapoton/26957
Commit: 3d9551de860522f6bb9ca1ada7905f8bdf669031

not fixed in 9.2.rc0 for me


New commits:

3d9551dtrac 26957 not fixed

comment:13 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:14 Changed 20 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:15 Changed 13 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:16 Changed 9 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:17 Changed 5 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:18 Changed 8 days ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.