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: |
Description (last modified by )
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)
Change History (17)
comment:1 Changed 2 years ago by
- Description modified (diff)
comment:2 Changed 2 years ago by
- Description modified (diff)
comment:3 Changed 2 years ago by
- Description modified (diff)
comment:4 Changed 2 years ago by
- Description modified (diff)
comment:5 Changed 2 years ago by
- Milestone changed from sage-8.6 to sage-8.7
comment:6 Changed 2 years ago by
- 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
- 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
- Milestone changed from sage-8.9 to sage-9.1
Ticket retargeted after milestone closed
comment:9 follow-up: ↓ 10 Changed 13 months ago by
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
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: ↓ 12 Changed 13 months ago by
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
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 putprint("*** hello ***")
in a file, then the result of running./sage -t
on that file istoo 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
- Milestone changed from sage-9.1 to sage-9.2
comment:14 Changed 7 months ago by
- Cc mjo added
- Milestone changed from sage-9.2 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
comment:15 Changed 7 months ago by
- Reviewers set to Marc Mezzarobba
- Status changed from needs_review to positive_review
comment:16 Changed 7 months ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
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.