Opened 7 years ago

Last modified 3 years ago

## #17895 closed defect

# Computing all roots is faster than computing a single one — at Initial Version

Reported by: | gagern | Owned by: | |
---|---|---|---|

Priority: | major | Milestone: | sage-8.9 |

Component: | number fields | Keywords: | qqbar polynomial_root roots performance |

Cc: | sbrandhorst | Merged in: | |

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | Stopgaps: |

### Description

The following example comes from comment:27:ticket:16964 via comment:2:ticket:17886.

sage: x,y = polygens(QQ,"x,y") sage: p1 = x^5 + 6*x^4 - 42*x^3 - 142*x^2 + 467*x + 422 sage: p2 = p1(x=(x-1)^2) sage: p3 = p2(x=x*y).resultant(p2,x).univariate_polynomial() sage: p4, = [f[0] for f in p3.factor() if f[0].degree() == 80] sage: ival = CIF((0.77, 0.78), (-0.08, -0.07)) sage: %time z1, = [r for r in p4.roots(QQbar, False) if r in ival] CPU times: user 1.43 s, sys: 195 ms, total: 1.62 s Wall time: 1.47 s sage: %time z2 = QQbar.polynomial_root(p4, ival) CPU times: user 1min 5s, sys: 212 ms, total: 1min 5s Wall time: 1min 5s

The computation for `z1`

works reasonably well and completes in under 2 seconds, but the one for `z2`

takes over a minute on my system. Which I find really strange, since computing all roots and then choosing the right one should be *more* work, not *less* than just computing a single one. Should we change `QQbar.polynomial_root`

to go via the list of all roots, or is there a better solution?

**Note:**See TracTickets for help on using tickets.