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 n x n + ... + q 0 with root separation ρ, coefficients |q n | ≥ 1 and |q i | ≤ 2 τ , it needs coefficient approximations to O(n(log(1/ρ) + τ)) bits after the binary point and has an expected cost of O(n 4 (log(1/ρ) + τ) 2 ) bit operations.
Eigenwillig et al. REF extended the Descartes algorithm for isolating real roots of polynomials to bit-stream coefficients.
A descartes algorithm for polynomials with bit-stream coefficients
In CASC, volume 3718 of LNCS
Computer Science Mathematics