Polynomial real root isolation using Descarte's rule of signs
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Uspensky's 1948 book on the theory of equations presents an algorithm, based on Descartes' rule of signs, for isolating the real roots of a squarefree polynomial with real coefficients, which proves to be a strong competitor of the recently discovered algorithm of Collins and Loos.
Abstract
Uspensky's 1948 book on the theory of equations presents an algorithm, based on Descartes' rule of signs, for isolating the real roots of a squarefree polynomial with real coefficients. Programmed in SAC-1 and applied to several classes of polynomials with integer coefficients, Uspensky's method proves to be a strong competitor of the recently discovered algorithm of Collins and Loos. It is shown, however, that it's maximum computing time is exponential in the coefficient length. This motivates a modification of the Uspensky algorithm which is quadratic in the coefficient length and which also performs well in the practical test cases.