HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Improved bounds for the CF algorithm

Elias Tsigaridas 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using the classic variant of the continued fraction algorithm (CF), introduced by Akritas. %% We compute a lower bound on the positive real roots of univariate polynomials using exponential search. This allows us to derive a worst case bound of $\sOB( d^4\tau^2)$ for isolating the real roots of a polynomial with integer coefficients using the {\em classic variant of CF}, where $d$ is the degree of the polynomial and $\tau$ the maximum bitsize of its coefficients. This improves the previous bound of Sharma by a factor of $d^3$ and matches the bound derived by Mehlhorn and Ray for another variant of CF which is combined with subdivision; it also matches the worst case bound of the classical subdivision-based solvers \func{sturm}, \func{descartes}, and \func{bernstein}.
Document type :
Journal articles
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download

Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Tuesday, January 15, 2013 - 11:42:43 AM
Last modification on : Friday, January 21, 2022 - 3:21:22 AM
Long-term archiving on: : Saturday, April 1, 2017 - 5:12:01 AM


Files produced by the author(s)


  • HAL Id : hal-00776230, version 1


Elias Tsigaridas. Improved bounds for the CF algorithm. Theoretical Computer Science, Elsevier, 2012, pp.1-12. ⟨hal-00776230⟩



Record views


Files downloads