Faire la somme des nombres consécutifs de 1 à $n$ ($1 + 2 + 3 + … + n$) est un exercice assez courant pour prendre en main un langage (ou bien s’initier à l’algorithmique). Dans cet article, je vais m’amuser avec Python à calculer cette somme — que l’on nomme parfois somme de Gauss — avec des méthodes plus ou moins tordues. L’occasion de survoler quelques principes algorithmiques comme le décalage de bits, les fonctions récursives…
La fonction sum()
Pour commencer, on va se reposer un peu sur nos lauriers. Je vais utiliser la fonction sum() déjà implémentée par Python. Cette fonction additionne tous les paramètres entre eux :
liste = [1, 2, 3, 4, 5]
sum(liste) #retourne 15Ok, ça marche : cependant, j’ai écrit la liste de nombres à la main. Ce n’est pas une solution très pratique ! Imaginons que j’ai une suite qui aille jusqu’à 100 ! On peut donc faire mieux. Avec les fonctions de Python, on sommer notre série en une seule ligne avec la fonction range() (Rappel : la borne supérieure est exclue). Donc, pour $1+2+3+4+5$ :
somme = sum(range(1, 6))La somme avec des boucles : une approche « analytique »
On peut bien entendu calculer une somme avec une boucle, par exemple en itérant sur les éléments de la liste de tout à l’heure
somme = 0
liste = [1, 2, 3, 4, 5]
for i in liste:
somme = somme + i
print(somme)Problème : si maintenant je veux faire la somme des nombres de 1 à 100, je ne vais quand même pas écrire ma liste à la main ? On peut utiliser une boucle et se passer de liste (ou même créer une liste avec une boucle):
somme = 0
for i in range(0, 101):
somme = somme + i
print(somme)Ici, nous avons une approche, disons, « analytique » : on avance pas à pas dans notre calcul en parcourant et en additionnant chacun des nombres de 1 à 100. D’abord +1, puis +2, puis +3 et ainsi de suite. Le code est clair, mais on peut se passer de la boucle (parce que pourquoi pas).
Les fonctions récursives
Toujours de façon analytique (où l’on envisage le problème comme une pile de chose à faire les unes à la suite des autres) il y a la méthode du calcul avec des fonctions récursives (des fonctions qui s’appellent elles-mêmes). La répétition est assurée par un appel infini… jusqu’à ce qu’une condition stoppe la ritournelle :
def somme_recursive(n):
if n == 0:
return 0
else :
return n + somme_recursive(n-1)On commence ici par le « haut de la pile » : on additionne notre borne supérieure (n) avec son prédécesseur (n-1) appelé en paramètre ; ce (n-1) repasse dans la fonction en tant que paramètre n qui va être additionné à son tour avec son propre prédécesseur… jusqu’à ce qu’on atteigne zéro. Personnellement, j’aime bien la récursivité même si, conceptuellement, c’est moins intuitif que la boucle. Elle a un côté « old school », très développeur C qui veut montrer comment fonctionne un stack.
L’approche synthétique
Ici, j’ai abordé le problème de la somme comme une suite d’opérations successives à réaliser. La somme de chacun des nombres sont, en quelque sorte, une suite de tâches qu’il me fallait en quelque sorte implémenter/traduire avec les moyens et la syntaxe de Python. Mais connaissez-vous cette histoire assez fameuse qui met en scène le jeune Gauss, alors écolier, ses camarades de classe et son professeur ? (Attention, il ne s’agirait là que d’un mythe.)
Voici l’histoire : un instituteur demande à ses élèves de calculer la somme de tous les nombres entre 1 et 100… les élèves s’exécutent et font à la main 1 + 2 + 3 + 4 + … + 100, que je noterai ici $\sum_{i=1}^{n} i$. Gauss, lui, malgré son jeune âge, réfléchit un instant. Et, finalement, au lieu de calculer fastidieusement la somme, dégage une formule qui permet de le faire mentalement: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
La démonstration, que je ne reproduis pas ici, est assez amusante mais je vous laisse la découvrir si vous ne la connaissez pas.
Jusqu’à présent, avec Python, je me suis comporté comme les autres élèves (il ne faut pas leur jeter la pierre, qui aurait suivi la voie du jeune Gauss ?) : j’ai effectué, certes avec un ordinateur qui calcule vite, laborieusement les additions.
L’approche synthétique revient donc à implémenter la formule de Gauss :
n = 100
sum = n * (n + 1) / 2Un soupçon de bits décalés pour flex
Ici, on a donc fait implémenté la logique synthétique du (petit) mathématicien. Mais si l’on continuer à s’amuser sur un problème simple, on peut remplacer la division par deux par un décalage de bits vers la droite.
n = 100
sum = n * (n + 1) >> 1Cela ne change pas grand chose : mais, sur des grands nombres, le décalage de bits permet de gagner en vitesse de calcul ! Mais on perd en lisibilité. En tout cas, sur 10.000 itérations, le décalage de bits permet d’effectuer les calculs environ 25% plus rapidement qu’avec la fonction sum() de python :
import timeit
def somme_gausse(n:int) -> int:
return n * (n + 1) >> 1
def somme(n:int) -> int:
return sum(range(1, n + 1))
iterations = 100000
temps_gausse = timeit.timeit('somme_gausse(100)', globals=globals(), number=iterations)
print(f'Temps pour somme_gausse: {temps_gausse:.6f} secondes')
temps_somme = timeit.timeit('somme(100)', globals=globals(), number=iterations)
print(f'Temps pour somme: {temps_somme:.6f} secondes')
ratio = temps_gausse/temps_somme
print(ratio)Voilà pour ce tour d’horizon : comme quoi un petit problème peut donner lieu à plusieurs implémentation et à différentes façons de l’envisager. Notre dernière solution ne prend que deux lignes et permet de gagner en performance — bien que cela n’est pas spécialement utile ici.
Laisser un commentaire