A Deterministic Descartes Algorithm for Real Polynomials
Kurt Mehlhorn, Michael Sagraloff · 2008
We describe a Descartes algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients of the polynomial can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is deterministic and has almost the same asymptotic complexity as the randomized bitstream-Descartes algorithm of~\\citet{BitstreamDescartes}. Besides being deterministic, the algorithm is also somewhat simpler to analyze.