Opened 2 years ago

Closed 7 months ago

# bug in polynomial real root

Reported by: Owned by: vdelecroix critical sage-duplicate/invalid/wontfix algebra ​cwitty, mmezzarobba, mjo Marc Mezzarobba N/A

```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)
```

```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]
```

### 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: ↓ 10 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

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 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

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

• 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.