fmpz_poly_isolate_real_roots, fmpz_poly_isolate_positive_roots

Three algorithms are used. For polynomials of large degree, bisection with a Sturm sequence is tried first; the sequence is computed as a primitive remainder sequence and evaluated at each bisection point in O(n) operations using the pseudo-quotients. This is much faster than VCA when the Sturm sequence has small coefficients and there are many real roots (classical orthogonal polynomials) or clusters of close roots (sparse polynomials). Otherwise, if the polynomial appears to have only real roots (Newton's inequalities hold and the numbers of sign variations of f(x) and f(-x) add up to the degree) spread over many orders of magnitude, as for Eulerian polynomials, sign changes are located by evaluating at dyadic points in ball arithmetic, and the result is certified by checking that the number of sign changes equals the number of sign variations. This avoids the huge coefficients that VCA produces for such polynomials. If these methods do not apply or fail, the Vincent–Collins–Akritas algorithm is used.