Complexity of real root isolation using continued fractions

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 , and the bit-complexity of a formulation by Akritas and Strzeboński is ; here 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 .