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ö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örner’s scheme, only faster. Our algorithm is implemented in a companion library, written in standard C and released as an open-source project (Mihalache and Vigneron, in: FPE library: a Fast Polynomial Evaluator, https://github.com/fvigneron/FastPolyEval, 2022). Our claims regarding complexity and accuracy are confirmed in practice by a set of comprehensive benchmarks.
