Évaluation de polynômes

Tout le monde sait bien qu'on doit évaluer un polynôme, soit sous sa forme factorisée, lorsqu'elle est connue (cf sous-subsection~11.8.2.1), soit par le schéma de Horner-Ruffini ^{notehttps://fr.wikipedia.org/wiki/M\%C3\%A9thode_de_Ruffini-Horner}~[219]A New Method of Solving Numerical Equations of All Orders, by Continuous Approximation, 1819, W. G. Horner pour l'expression usuelle~:

\begin{array}{r} \begin{aligned} p (x) & = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots + a_{n} x^{n} \\ = a_{0} + x (a_{1} + x (a_{2} + x (a_{3} + \dots + x (a_{n - 1} + x a_{n}) \dots))) \end{aligned} \end{array}

C'est non seulement un gain de vitesse, par l'économie d'opérations qu'il réalise, mais aussi de précision, en partie pour la même raison, mais surtout c'est un gage de stabilité du résultat et de sécurité vis-à-vis des dépassements intermédiaires, particulièrement dans le cas de la simple précision. Il est d'ailleurs possible d'aller encore plus vite~[220]Evaluation of Polynomials by Computer, 1962, Knuth, Donald E..

La popularisation d'instructions machine fma combinant addition et multiplication (cf sous-subsection~11.8.2.9.3), nous amène à rechercher vivement leur emploi dans ce cas~[247]Improving the Compensated Horner Scheme with a Fused Multiply and Add, 2006, Graillat, Stef and Langlois, Philippe and Louvet, Nicolas.

De plus, un polynôme étant avant tout une somme (cf sous-subsection~11.8.2.4), les techniques de sommation par compensation, comme l'algorithme de sommation de W.~Kahan~[204]Pracniques: Further Remarks on Reducing Truncation Errors, 1965, Kahan, William, doivent être prise en considération.