bug in polynomial real root (bis)

[videlec]

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)

CC: @sagetrac-cwitty @mezzarobba

Component: algebra

Branch/Commit: u/chapoton/26957 @ 3d9551d

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

[embray]

comment:2

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.

[embray]

comment:3

Moving all blocker/critical issues from 8.7 to 8.8.

[embray]

comment:4

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

[embray]

comment:5

Ticket retargeted after milestone closed

[bmlivin]

comment:7

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

[mezzarobba]

comment:8

But #20390 is still present. Strange.

[slel]

comment:10

Please let's add a doctest.

[fchapoton]

comment:12

not fixed in 9.2.rc0 for me

---

New commits:

3d9551d

trac 26957 not fixed

[fchapoton]

Branch: u/chapoton/26957

[fchapoton]

Commit: 3d9551d

[mkoeppe]

comment:14

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