Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

New bounds for the Descartes method


Krandick,  Werner
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Krandick, W., & Mehlhorn, K. (2006). New bounds for the Descartes method. Journal of Symbolic Computation, 41(1), 49-66. doi:10.1016/j.jsc.2005.02.004.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2384-C
We give a new bound for the number of recursive subdivisions in the Descartes
method for polynomial real root isolation. Our proof uses Ostrowski’s theory of
normal power series from 1950 which has so far been overlooked in the
literature. We combine Ostrowski’s results with a theorem of Davenport from
1985 to obtain our bound. We also characterize normality of cubic polynomials
by explicit conditions on their roots and derive a generalization of one of
Ostrowski’s theorems.