Real root isolation using Continued Fractions

concerning real root isolation of integer univariate polynomials
using the continued fraction expansion of real algebraic numbers.
We improve the previously known bound by a factor of $d \tau$,
where $d$ is the polynomial degree and $\tau$ bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is
$O~(d4 \tau2)$ using the standard bound on the expected bitsize of the integers in the continued fraction expansion.
Moreover, using the measure theory of the continued fractions we present a variant of the algorithm that has expected complexity $O~( d3 \tau)$.

The continued fraction algorithm depends heavily on the quality of the bounds for the positive real roots of polynomials. We present the state-of-art in this area and our work towards unifying and improving the known approaches.