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

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

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

88

Files downloads

136