Skip to Main content Skip to Navigation
Journal articles

Improved bounds for the CF algorithm

Elias Tsigaridas 1
1 PolSys - Polynomial Systems
Inria Paris-Rocquencourt, LIP6 - Laboratoire d'Informatique de Paris 6
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

https://hal.inria.fr/hal-00776230
Contributor : Elias Tsigaridas <>
Submitted on : Tuesday, January 15, 2013 - 11:42:43 AM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Saturday, April 1, 2017 - 5:12:01 AM

File

et-improve-bd-cf.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00776230, version 1

Citation

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

Share

Metrics

Record views

305

Files downloads

340