Near optimal tree size bounds on a simple real root isolation algorithm

Abstract

The problem of isolating all real roots of a square-free integer polynomial f(X) inside any given interval I0 is a fundamental problem. EVAL is a simple and practical exact numerical algorithm for this problem: it recursively bisects I0, and any sub-interval I ⊆ I0, until a certain numerical predicate C0(I) V C1(I) holds on each I. We prove that the size of the recursion tree is