#10803: critical bug in real_roots
--------------------------------------+-------------------------------------
Reporter: zimmerma | Owner: jason, jkantor
Type: defect | Status: needs_review
Priority: critical | Milestone: sage-5.1
Component: numerical | Resolution:
Keywords: real roots, sd40.5 | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Paul Zimmermann | Merged in:
Dependencies: | Stopgaps:
--------------------------------------+-------------------------------------
Comment (by dsm):
Given how sensitive the problem is I think we're going to need to know why
whatever we find fixes the problem before we're confident that we've fixed
it. Here I'm not sure that it does. Digging up some of my old notes,
even with the patch, we have problems we shouldn't:
{{{
sage: from sage.rings.polynomial.real_roots import real_roots
sage: R.<x> = ZZ[]
sage: f = 535944*x^12 - 3312356*x^11 + 8042902*x^10 - 9521317*x^9 +
5204589*x^8 - 461471*x^7 - 682572*x^6 + 174775*x^5 + 25797*x^4 - 5793*x^3
- 473*x^2 + 17*x + 1
sage: len(f.roots(RR))
12
sage: len(real_roots(f, seed=1))
12
sage: # but..
sage: f.roots(RR)
[(-0.279345282327294, 1), (-0.169895157384578, 1), (-0.0836442589128367,
1), (-0.0391184461806829, 1), (0.0525277889691767, 1), (0.217266273158562,
1), (0.608742206578326, 1), (0.743349076348040, 1), (0.955058967243006,
1), (0.956604779629507, 1), (1.40057197815310, 1), (1.81829644637645, 1)]
sage: [len(real_roots(f, seed=1, bounds=(-1, 7+1/2**k))) for k in
[0..200]]
[12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12,
10, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10,
12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12,
12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10,
12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12,
12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10,
12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12,
12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10,
12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12,
12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10,
12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12, 12, 10, 12, 12,
12, 10, 12]
}}}
And we see a clearly periodic pattern. For me real_roots.pyx takes a long
time to compile so I got frustrated chasing this clue, but changing the
bounds like this -- outside the range of all of the roots! -- should have
no effect. If we could figure out why this happens I think we'd have it.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10803#comment:19>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
