Skip to Main content Skip to Navigation

On the complexity of real root isolation using Continued Fractions

Abstract : We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We improve the previously known bound by a factor of $d \tau$, where $d$ is the polynomial degree and $\tau$ bounds the coefficient bit size, thus matching the current record complexity for real root isolation by exact methods (Sturm, Descartes and Bernstein subdivision). Namely our complexity bound is $\sOB(d^4 \tau^2)$ using a standard bound on the expected bit size of the integers in the continued fraction expansion. Moreover, using a homothetic transformation we improve the expected complexity bound to $\sOB( d^3 \tau)$ under the assumption that $d = \OO( \tau)$. We compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source \texttt{C++} implementation and illustrate its completeness and efficiency as compared to other available software. For this we use polynomials with coefficient bit size up to 8000 bits and degree up to 1000.
Document type :
Complete list of metadatas
Contributor : Elias Tsigaridas <>
Submitted on : Monday, December 11, 2006 - 12:11:18 PM
Last modification on : Thursday, August 27, 2020 - 3:40:04 PM
Long-term archiving on: : Friday, September 24, 2010 - 1:56:19 PM


Files produced by the author(s)


  • HAL Id : inria-00116990, version 6



Elias P. Tsigaridas, Ioannis Emiris. On the complexity of real root isolation using Continued Fractions. [Research Report] RR-6059, INRIA. 2006, pp.22. ⟨inria-00116990v6⟩



Record views


Files downloads