Complexity of real root isolation using continued fractions
Vikram Sharma · 2007
In this paper, we provide polynomial bounds on the worst case bit-complexity of two formulations of the continued fraction algorithm. In particular, for a square-free integer polynomial of degree $n$ with coefficients of bit-length $L$, we show that the bit-complexity of Akritas' formulation is $\wt{O}(n^8L^3)$, and the bit-complexity of a 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. We also propose a modification of the latter formulation that achieves a bit-complexity of $\wt{O}(n^5L^2)$.