  We propose an algorithm for quickly evaluating polynomials. It pre-conditions
a complex polynomial $P$ of degree $d$ in time $O(d\log d)$, with a low
multiplicative constant independent of the precision. Subsequent evaluations of
$P$ computed with a fixed precision of $p$ bits are performed in average
arithmetic complexity $O\big(\sqrt{d(p+\log d)}\big)$ and memory $O(dp)$. The
average complexity is computed with respect to points $z \in \mathbb{C}$,
weighted by the spherical area of $\overline{\mathbb{C}}$. The worst case does
not exceed the complexity of H{\"o}rner's scheme. In particular, our algorithm
performs asymptotically as $O(\sqrt{d\log d})$ per evaluation. For many classes
of polynomials, in particular those with random coefficients in a bounded
region of $\mathbb{C}$, or for sparse polynomials, our algorithm performs much
better than this upper bound, without any modification or parameterization.The
article contains a detailed analysis of the complexity and a full error
analysis, which guarantees that the algorithm performs as well as H\''orner's
scheme, only faster. Our algorithm is implemented in a companion library,
written in standard C and released as an open-source project [MV22].Our claims
regarding complexity and accuracy are confirmed in practice by a set of
comprehensive benchmarks.
