Algoritmo di Horner

Dati i coefficienti $c_{0} \ldots c_n$ del polinomio rappresentato nella base di Newton, un metodo efficiente di calcolare il polinomio in un punto $\overline{x}$ è dato dall'algoritmo di Horner che corrisponde in pratica ad eseguire le operazioni raccogliendo i termini in questo modo.

$$c_0+(\overline{x}-x_0)(c_1+(x-x_1)(\ldots +(x-x_n-1)c_n)\ldots)$$

Questo algoritmo ha una complessità di $O(3n)$ flops. La procedura Horner esegue l'algoritmo di Horner lavorando in parallelo su un vettore di ascisse di tabulazione e restituisce un vettore dei corrispondenti valori del polinomio in quei punti.