Real Root Isolation Using Continued Fractions

a formulation of the continued fraction algorithm for real root isolation.
In particular, for a square-free integer polynomial of degree $n$ and
coefficients of bit-length $L$ we show that the bit-complexity
of a recent formulation by Akritas and Strzebo\'nski is $\wt{O}(n^7L^2)$;
here $\wt{O}$ indicates that we are omitting logarithmic factors.
The analyses use a bound by Hong to compute
the floor of the smallest positive root of a polynomial, which is a crucial
step in the continued fraction algorithm.