Integer Arithmetic Algorithms for Polynomial Real Zero Determination
Lee E. Heindel · Journal of the ACM · 1971
This paper discusses a set of algorithms which given a univariate polynomial with integer coefficients (with possible multiple zeros) and a positive rational error bound, uses infinite-precision integer arithmetic and Sturm's theorem to compute intervals containing the real zeros of the polynomial and whose lengths are less than the given error bound.The algorithms also provide a simple means of determining the number of real zeros in any interval.Theoretical computing time bounds are developed for the algorithms and some empirical results are reported.