polynomial real root isolation by differentiation
A new algorithm is described, for the isolation of the real roots of a real polynomial. This algorithm utilizes the sequence of derivatives of the given polynomial, relying on Rolle's theorem and a tangent construction to decide whether an interval contains two roots or none. The algorithm is carefully compared, both analytically and empirically, with an algorithm based on Sturm's theorem, and is found to be significantly faster in general. It also requires less memory, and produces isolating intervals for the derivatives as a cost-free by-product.
polynomial isolates algorithm sequence interval general memorialized product cost