DagSemProc.06021.3.pdf
- Filesize: 211 kB
- 12 pages
Document
A Descartes Algorithms for Polynomials with Bit-Stream Coefficients
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6021
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-09-13
Cite AsGet BibTex
Kurt Mehlhorn, Arno Eigenwillig, Lutz Kettner, Werner Krandick, Susanne Schmitt, and Nicola Wolpert. A Descartes Algorithms for Polynomials with Bit-Stream Coefficients. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06021.3
https://doi.org/10.4230/DagSemProc.06021.3
Abstract
The Descartes method is an algorithm for isolating the
real roots of square-free polynomials with real coefficients. We assume
that coefficients are given as (potentially infinite) bit-streams. In other
words, coefficients can be approximated to any desired accuracy, but are not
known exactly. We show that
a variant of the Descartes algorithm can cope with bit-stream
coefficients. To isolate the real roots of a
square-free real polynomial $q(x) = q_nx^n+ldots+q_0$ with root
separation $
ho$, coefficients $abs{q_n}ge1$ and $abs{q_i} le 2^ au$,
it needs coefficient approximations to $O(n(log(1/
ho) + au))$
bits after the binary point and has an expected cost of
$O(n^4 (log(1/
ho) + au)^2)$ bit operations.
Keywords
- Root Isolation
- Interval Arithmetic
- Descartes Algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads