# 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(n

computational experience with

the algorithm.

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(n

^{4}(log(1/ρ) + τ)^{2}) bit operations. We also report oncomputational experience with

the algorithm.