Improved complexity bounds for real root isolation using Continued Fractions

الأصل · EN

We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using (variants of) the continued fraction algorithm (CF). We introduce a novel way to compute a lower bound on the positive real roots of univariate polynomials. This allows us to derive a worst case bound of (d⁶ + d⁴τ² + d³τ²) for isolating the real roots of a polynomial with integer coefficients using the classic variant Akritas:implementation of CF, where d is the degree of the polynomial and τ the maximum bitsize of its coefficients. This improves the previous bound of Sharma sharma-tcs-2008 by a factor of d³ and matches the bound derived by Mehlhorn and Ray mr-jsc-2009 for another variant of CF; it also matches the worst case bound of the subdivision-based solvers.