Le même calcul, deux algorithmes

# version A
S = 0
for i in range(1, n + 1):
    S = S + i

# version B
S = n * (n + 1) // 2

Version A effectue $n$ additions ; version B en effectue trois, quel que soit n.

Pour $n=10^9$, la version A demande un milliard de tours — plusieurs minutes — tandis que la version B répond instantanément. Les deux donnent le même nombre, $500000000500000000$.

La version B repose sur la formule de Gauss $1+2+\cdots +n=\frac{n(n+1)}{2}$, qui se démontre en appariant le premier terme avec le dernier, le deuxième avec l'avant-dernier, etc. : on obtient $n/2$ paires valant chacune $n+1$.

La leçon est double. D'abord, un raisonnement mathématique peut remplacer une boucle — c'est souvent le plus grand gain de performance disponible. Ensuite, la division est écrite // et non / : le produit $n(n+1)$ est toujours pair, donc le résultat est un entier exact, alors que / renverrait un flottant qui perdrait des chiffres pour de grandes valeurs de n.