The Bitstream Descartes Method

Tuesday, May 29, 2007 - 9:15am - 10:05am
EE/CS 3-180
Kurt Mehlhorn (Max-Planck-Institut für Informatik)
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) of degree n, root separation
ρ, coefficients bounded by
2 to the τ, and leading coefficient at least one, the
algorithm needs coefficient approximations
with O(n(log(1/ρ) + τ)) bits after the binary point and has
an expected cost of
O(n4 (log(1/ρ) + τ)2) bit operations. We also report on
computational experience with
the algorithm.