the increments are zero relative to the chosen precision. Graeffe iteration The crucial step in this method is to find an annulus of relative width 4 in the complex plane that contains no zeros of p and contains approximately as many zeros of p inside as outside of it. Any annulus of this characteristic can be transformed, by translation and scaling of the polynomial, into the annulus between the radii 1/2 and 2 around the origin. But, not every polynomial admits such a splitting annulus. To remedy this situation, the Graeffe iteration is applied. It computes a sequence of polynomials where the roots of are the -th dyadic powers of the roots of the initial polynomial p. By splitting into even and odd parts, the succeeding polynomial is obtained by purely arithmetic operations as . The ratios of the absolute moduli of the roots increase by the same power and thus tend to infinity. Choosing j large enough one finally finds a splitting annulus of relative width 4 around the origin. The approximate factorization of is now to be lifted back to the original polynomial. To this end an alternation of Newton steps and Padé approximations is used. It is easy to check that holds. The polynomials on the left side are known in step j, the polynomials on the right side can be obtained as Padé approximants of the corresponding degrees for the power series expansion of the fraction on the left side. Finding a good circle Making use of the Graeffe iteration and any known estimate for the absolute value of the largest root one can find estimates R of this absolute value of any precision. Now one computes estimates for the largest and smallest distances of any root of p(x) to any of the five center points 0, 2R, −2R, 2Ri, −2Ri and selects the one with the largest ratio between the two. By this construction it can be guaranteed that for at least one center. For such a center there has to be a root-free annulus of relative width . After Graeffe iterations, the corresponding annulus of the iterated polynomial has a relative width greater than 11 > 4, as required for the initial splitting described above (see Schönhage (1982)). After Graeffe iterations, the corresponding annulus has a relative width greater than , allowing a much simplified initial splitting (see Malajovich/Zubelli (1997)) To locate the best