Avec R. Anton et F. Vigneron, nous proposons un nouveau algorithme d'évaluation rapide des polynômes. Il effectue d'abord une analyse des coefficients d'un polynôme P de degré d en temps O(d log d), indépendamment de la précision (et avec une petite constante multiplicative).
Ensuite, chaque évaluation de P avec précision p (chiffres significatifs en base 2) coûte en moyenne O(\sqrt{d(p+\log d)}) et utilise O(dp) de mémoire. La moyenne est calculée par rapport à l'aire de la sphère de Riemann. Dans le pire des cas, nous avons complexité O(d), celle du schéma classique de Horner.
La preuve repose sur une inégalité sur les fonctions concaves de l'intervalle.
