Somme d'entiers consécutifs

Un bref article de mise au point à propos d'un résultat élémentaire : la somme d'entiers consécutifs. En effet, il arrive encore de voir des programmeurs qui, pour effectuer ce calcul simple, écrivent une boucle itérant du premier au dernier entier. Nous allons voir pourquoi ceci est une hérésie, et comment résoudre le problème efficacement. Quelques exemples seront donnés dans différents langages.

La version bourrine

En substance, la version bourrine se formule comme ceci :

Résultat = 0
Pour k allant de l'entier de départ à l'entier d'arrivée
    Résultat += k

D'un point de vue de la complexité, on considère tous les entiers de la plage de valeurs : l'algorithme est donc en O(N). Sur de grandes valeurs de N, le temps d'exécution n'est absolument pas négligeable : employée au sein de projets complexe, cette solution n'est pas envisageable.

Une solution efficace

On peut pourtant calculer le résultat en O(1). La formule connue est la suivante (sa démonstration est donnée dans la section mathématique) :

$\large \sum_{k=1}^{n}{k}\,=\,{{{n}\,\times\,{(n\,+\,1)}} \over {2}}$

Une simple fonction, voire un calcul direct dans le code suffisent donc à résoudre le problème.

Exemples

Considérons quelques exemples dans différents langages histoire de fixer les idées.

Caml

let deb = read_int() and fin = read_int() in
let res = ((fin * (fin + 1) - (deb - 1) * deb) / 2) in
print_int(res);;

C++

#include <cstdio>
 
inline int somme(int deb, int fin)
{
    return ((fin * (fin + 1) - (deb - 1) * deb) / 2);
}
 
int main()
{
    int deb, fin;
    scanf("%d%d", &deb, &fin);
    printf("%d\n", somme(deb, fin));
    return 0;
}

Conclusion

Pour certains, l'informatique et les mathématiques sont deux matières distinctes. Voici une preuve que non : l'emploi de résultats mathématiques connus entraîne des programmes bien plus efficaces. Il est recommandé vivement à ceux qui ne connaissaient pas ce résultat de le connaître par coeur.