  The algorithms of Pan (1995) and(2002) approximate the roots of a complex
univariate polynomial in nearly optimal arithmetic and Boolean time but require
precision of computing that exceeds the degree of the polynomial. This causes
numerical stability problems when the degree is large. We observe, however,
that such a difficulty disappears at the initial stage of the algorithms, and
in our present paper we extend this stage to root-finding within a nearly
optimal arithmetic and Boolean complexity bounds provided that some mild
initial isolation of the roots of the input polynomial has been ensured.
Furthermore our algorithm is nearly optimal for the approximation of the roots
isolated in a fixed disc, square or another region on the complex plane rather
than all complex roots of a polynomial. Moreover the algorithm can be applied
to a polynomial given by a black box for its evaluation (even if its
coefficients are not known); it promises to be of practical value for
polynomial root-finding and factorization, the latter task being of interest on
its own right. We also provide a new support for a winding number algorithm,
which enables extension of our progress to obtaining mild initial
approximations to the roots. We conclude with summarizing our algorithms and
their extension to the approximation of isolated multiple roots and root
clusters.
