Improved bounds for the CF algorithm

We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using the classic variant of the continued fraction algorithm (CF), introduced by Akritas. We compute a lower bound on the positive real roots of univariate polynomials using an exponential search. This allows us to derive a worst-case bound of for isolating the real roots of a polynomial with integer coefficients using the classic variant of CF, where d is the degree of the polynomial and τ the maximum bitsize of its coefficients. This improves the previous bound of Sharma by a factor of d3 and matches the bound derived by Mehlhorn and Ray for another variant of CF which is combined with subdivision; it also matches the worst-case bound of the classical subdivision-based solvers sturm, descartes, and bernstein.