Simple algorithms for approximating all roots of a polynomial with real roots (Q757494)

Let p be a polynomial of degree n in \({\mathbb{Z}}[x]\) with n distinct real roots. Suppose that the coefficients of p are all in absolute value less than \(2^ m\). It is shown that the approximation of all roots of p, within precision \(2^{-\mu}\) is P-uniform \(NC^ 2\) and it can be solved by a sequential algorithm using only \(O(n^ 2(m+\mu)\log^ 6(m+n+\mu))\) bit operations. The algorithm makes use of a Sturm sequence for p that consists of orthogonal polynomials, with small coefficients.