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.
Type de document :
[Research Report] RR-6059, INRIA. 2006, pp.22
Liste complète des métadonnées

Contributeur : Elias Tsigaridas <>
Soumis le : lundi 11 décembre 2006 - 12:11:18
Dernière modification le : mercredi 17 octobre 2018 - 17:02:02
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 13:56:19


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers