  Evaluating or finding the roots of a polynomial $f(z) = f_0 + \cdots + f_d
z^d$ with floating-point number coefficients is a ubiquitous problem. By using
a piecewise approximation of $f$ obtained with a careful use of the Newton
polygon of $f$, we improve state-of-the-art upper bounds on the number of
operations to evaluate and find the roots of a polynomial. In particular, if
the coefficients of $f$ are given with $m$ significant bits, we provide for the
first time an algorithm that finds all the roots of $f$ with a relative
condition number lower than $2^m$, using a number of bit operations
quasi-linear in the bit-size of the floating-point representation of $f$.
Notably, our new approach handles efficiently polynomials with coefficients
ranging from $2^{-d}$ to $2^d$, both in theory and in practice.
