bug in polynomial real root

[vdelecroix]

l = [1, -1, 0, 1, 0, 1, -14, 6, 1, 12, 0,
     2, -4, 0, -1, 0, 0, -1188, -12, 1, 1,
     -6, -1, -1, 18, 0, -1, 15, 0, 1, 1, -1,
     1, 1, 2, -1, -8, -2, -2, 2, 1, -1, 4, 0,
     -2, -2, 122, 0, 0, 1, -1, -1, 2, 0, 0, -1,
    -2, 1]
p = ZZ['x'](l)
p.roots(AA)

leads to

AssertionError                            Traceback (most recent call last)
<ipython-input-11-31650a84a6a3> in <module>()
      6     -Integer(2), Integer(1)]
      7 p = ZZ['x'](l)
----> 8 p.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:33063)()
   3070         while not self.all_done():
   3071             self.refine_all()
-> 3072             self.increase_precision()
   3073 
   3074     def roots(self):

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.ocean.increase_precision (build/cythonized/sage/rings/polynomial/real_roots.c:34225)()
   3205                 targets += [(isle.lgap, isle.rgap, isle.bp.scale_log2)]
   3206                 self.ctx.dc_log_append(('splitting', (isle.lgap.lower, isle.lgap.upper), (isle.rgap.lower, isle.rgap.upper), isle.bp.scale_log2))
-> 3207             bps = split_for_targets(self.ctx, p, targets)
   3208             for i in range(len(active_islands)):
   3209                 bp = bps[i]

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.split_for_targets (build/cythonized/sage/rings/polynomial/real_roots.c:31094)()
   2880     split = wordsize_rational(split_targets[best_index][0], split_targets[best_index][1], ctx.wordsize)
   2881 
-> 2882     (p1_, p2_, ok) = bp.de_casteljau(ctx, split, msign=split_targets[best_index][2])
   2883     assert(ok)
   2884 

/usr/lib/python2.7/site-packages/sage/rings/polynomial/real_roots.pyx in sage.rings.polynomial.real_roots.interval_bernstein_polynomial_integer.de_casteljau (build/cythonized/sage/rings/polynomial/real_roots.c:9195)()
    728             msign = sign
    729         elif sign != 0:
--> 730             assert(msign == sign)
    731 
    732         cdef Rational absolute_mid = self.lower + mid * (self.upper - self.lower)

AssertionError: 

Other examples (one by line)

[1, 1, 0, -63, 1, 1, 0, 1, 0, 0, -70, 0, 5, -3, 0, 5, -6, -1, 0, 0, 1, 2, -1, -2, -1, 1, 9, 1, 1, -1, 1, -19, 0, 0, -2771, -6, 2, -4, 6, 2]
[-1, -2, 2, 1, 0, -1, 1, -1, 1, -1, 1, -1, -1, -2, 2, 0, -1, 0, -1, -1, -1, 0, -1, 62, 1, 0, 2, 44, 3, 5, -3, -1, -1, 11, 1]
[-1, 1, 1, -2, 0, 1, -1, 14, 1, 1, -1, 0, -2, -1, -2, -1, -1, -2, -9, 0, 0, 0, -6, -14, -1, -1, 2, -86, -20, 1]

(see also #26957 for another bug)

[embray]

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]

Moving all blocker/critical issues from 8.7 to 8.8.

[embray]

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

[embray]

Ticket retargeted after milestone closed

[gh-DaveWitteMorris]

test for the bugs in #26955 and #26957

[gh-DaveWitteMorris]

In case it is useful information: The bugs in this ticket and #26957 seem to be gone in 9.0(Py3) (tested on CoCalc) and 9.1b6(Py3) (tested on my computer - Mac 10.15.1). However, the bug reappears when I doctest with ./sage -t. (I discovered this after I wrote a doctest to show that the bugs are gone, and was very surprised to see the errors again when I ran the doctest. At first, I thought I must have been running 8.9 by mistake.)

If I run ./sage 26955text.pyx on the attached file, I get good output. However, if I run ./sage -t 26955text.pyx, then I get the errors. Thus, it appears to me (a very naive observer) that some change made by the -t option is a part of the problem. I hope this information will be useful to an expert, even though it doesn't mean anything to me.

[vdelecroix]

Replying to gh-DaveWitteMorris:

In case it is useful information: The bugs in this ticket and #26957 seem to be gone in 9.0(Py3) (tested on CoCalc) and 9.1b6(Py3) (tested on my computer - Mac 10.15.1). However, the bug reappears when I doctest with ./sage -t. (I discovered this after I wrote a doctest to show that the bugs are gone, and was very surprised to see the errors again when I ran the doctest. At first, I thought I must have been running 8.9 by mistake.)

If I run ./sage 26955text.pyx on the attached file, I get good output. However, if I run ./sage -t 26955text.pyx, then I get the errors. Thus, it appears to me (a very naive observer) that some change made by the -t option is a part of the problem. I hope this information will be useful to an expert, even though it doesn't mean anything to me.

Thanks for testing this. I don't understand how ./sage -t 26955text.pyx could trigger an error since the file does not contain any doctest.

[gh-DaveWitteMorris]

It seems that ./sage -t <filename> executes all of the code in the file, not just the doctests. For example, if I put print("*** hello ***") in a file, then the result of running ./sage -t on that file is

too many failed tests, not using stored timings
Running doctests with ID 2020-03-13-13-46-22-4cbd34d1.
Git branch: develop
Using --optional=build,ccache,dochtml,fricas,sage
Doctesting 1 file.
*** hello ***
sage -t /Users/dmorris/tmp/hello.py
    [0 tests, 0.00 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.0 seconds
    cpu time: 0.0 seconds
    cumulative wall time: 0.0 seconds

[vdelecroix]

Replying to gh-DaveWitteMorris:

It seems that ./sage -t <filename> executes all of the code in the file, not just the doctests. For example, if I put print("*** hello ***") in a file, then the result of running ./sage -t on that file is

too many failed tests, not using stored timings
Running doctests with ID 2020-03-13-13-46-22-4cbd34d1.
Git branch: develop
Using --optional=build,ccache,dochtml,fricas,sage
Doctesting 1 file.
*** hello ***
sage -t /Users/dmorris/tmp/hello.py
    [0 tests, 0.00 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.0 seconds
    cpu time: 0.0 seconds
    cumulative wall time: 0.0 seconds

True, the code is executed (as the doctests could depend on it). There is an argument --force-lib to sage -t to avoid that automatic execution.

[mjo]

This is essentially a duplicate of #20390, although I think the failing test case here is a bit nicer. You can also turn this example into a recursion error (see #26957, too) by increasing the precision as I've remarked on #20390.