Opened 2 years ago

Closed 7 months ago

#26955 closed defect (duplicate)

bug in polynomial real root

Reported by: vdelecroix Owned by:
Priority: critical Milestone: sage-duplicate/invalid/wontfix
Component: algebra Keywords:
Cc: ​cwitty, mmezzarobba, mjo Merged in:
Authors: Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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)

Attachments (1)

26955test.pyx (1.3 KB) - added by gh-DaveWitteMorris 13 months ago.
test for the bugs in #26955 and #26957

Download all attachments as: .zip

Change History (17)

comment:1 Changed 2 years ago by vdelecroix

  • Description modified (diff)

comment:2 Changed 2 years ago by vdelecroix

  • Description modified (diff)

comment:3 Changed 2 years ago by vdelecroix

  • Description modified (diff)

comment:4 Changed 2 years ago by vdelecroix

  • Description modified (diff)

comment:5 Changed 2 years ago by embray

  • Milestone changed from sage-8.6 to sage-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:6 Changed 2 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Moving all blocker/critical issues from 8.7 to 8.8.

comment:7 Changed 22 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

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

comment:8 Changed 16 months ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

Changed 13 months ago by gh-DaveWitteMorris

test for the bugs in #26955 and #26957

comment:9 follow-up: Changed 13 months ago by 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.

comment:10 in reply to: ↑ 9 Changed 13 months ago by 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.

comment:11 follow-up: Changed 13 months ago by 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

comment:12 in reply to: ↑ 11 Changed 13 months ago by 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.

comment:13 Changed 11 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

comment:14 Changed 7 months ago by mjo

  • Cc mjo added
  • Milestone changed from sage-9.2 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

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.

comment:15 Changed 7 months ago by mmezzarobba

  • Reviewers set to Marc Mezzarobba
  • Status changed from needs_review to positive_review

comment:16 Changed 7 months ago by chapoton

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.