# On the complexity of real root isolation using Continued Fractions

1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Keywords :
Document type :
Reports

https://hal.inria.fr/inria-00116990
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

### File

RR-6059.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00116990, version 6

### Citation

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