A deterministic algorithm for isolating real roots of a real polynomial (Q607163)

A bisection algorithm for root isolation of polynomials with real coefficients is described. The work consists of six sections. The section 1 is an introduction. In section 2 the related works are disscussed. In section 3 the authors review Descartes' rule of sign and the classical Vincent-Collins-Akritas bisection algorithm. In section 4 the extension to real polynomials with bitstream coefficients are discussed. Section 5 deals with a partial extension to polynomials with multiple roots. In section 6 some conclusions are given. The proposed algorithm is simpler, deterministic and has better asymptotic complexity than the randomized algorithm suggested earlier.