Le schéma de Horner

def horner(coefs, x):
    # coefs = [a0, a1, ..., an], du degre 0 au degre n
    r = 0
    for a in reversed(coefs):
        r = r * x + a
    return r

def naif(coefs, x):
    return sum(a * x**i for i, a in enumerate(coefs))

Le compte, pour un polynôme de degré $n$.

Horner : la boucle fait $n+1$ tours, chacun avec une multiplication (le premier tour la fait sur $r=0$, donc $n$ sont utiles). Total : $\mathbf{n}$ multiplications et $n$ additions.

Naïf : calculer $x^i$ par produits répétés coûte $i-1$ multiplications, plus une pour $a_i{x}^i$. En sommant sur $i$, on obtient de l'ordre de $\frac{n(n+1)}{2}$ multiplications — une croissance quadratique.

Pour $n=100$ : $100$ multiplications contre environ $5050$.

Et ce n'est pas seulement une question de vitesse. La forme naïve calcule des puissances $x^{100}$ énormes ou minuscules avant de les recombiner, ce qui, en flottants, détruit des chiffres significatifs. Horner n'évalue jamais rien de plus grand que le résultat lui-même : il est aussi plus stable.

Un bonus. Le tableau des valeurs intermédiaires de r donne les coefficients du quotient de $P$ par $(x-x_0)$ : le schéma de Horner est la division euclidienne par un facteur du premier degré.