2010/10/11 by Tsigaridas, Elias
#FOS: Computer and information sciences #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.1010.2006
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 \sOB(d6 + d4τ2 + d3τ2) for isolating the real roots of a polynomial with integer coefficients using the classic variant \citeAkritas: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 \citesharma-tcs-2008 by a factor of d3 and matches the bound derived by Mehlhorn and Ray \citemr-jsc-2009 for another variant of CF; it also matches the worst case bound of the subdivision-based solvers.