Videos

The Bitstream Descartes Method

Presenter
May 29, 2007
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) 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.