Lorsqu’on apprend à calculer, on commence toujours par l’addition. En effet, c’est l’opération la plus élémentaire. Elle nous sert à figurer les entiers naturels : 4, c’est 3 + 1, 2 + 1 + 1, ou 1 + 1 + 1 + 1. C’est d’ailleurs cette représentation qui nous permet de comprendre la première méthode d’addition que l’on apprend à l’école. Ainsi, pour additionner deux entiers naturels A et B, il suffit de prendre A et de lui ajouter B fois le nombre 1. C’est la méthode utilisée lorsque l’on « compte sur ses doigts ».
Quand on commence à concevoir des nombres plus grands, il est difficile d’utiliser cette méthode et on en apprend donc une deuxième. Pour additionner deux grands entiers naturels A et B, on ajoute d’abord les chiffres des unités, puis celui des dizaines, etc., en utilisant une « retenue » lorsque le résultat possède plus de deux chiffres. En fait, on utilise ici les propriétés associatives et commutatives de l’addition ainsi que la décomposition d’un nombre en puissances de 10. Par exemple, 59 + 125 = (5 × 10 + 9 × 1) + (1 × 100 + 2 × 10 + 5 × 1) = (9 × 1 + 5 × 1) + (5 × 10 + 2 × 10) + 1 × 100. Mais on n’énoncera pas ces propriétés formelles pour expliquer comment poser une addition à un enfant.
Deux méthodes au banc d’essai
Si vous demandez à un ami d’effectuer le calcul 23 + 126, vous pouvez être sûr qu’il posera l’addition et n’utilisera pas la première méthode. Il est clair que si a et b sont « suffisamment grands », la deuxième méthode sera beaucoup plus rapide que la première. Mais qu’en est-il pour une machine, un ordinateur ou une calculatrice ? Nous vous proposons de vérifier que cela reste le cas, en programmant ces deux méthodes en langage Python avec la calculatrice Graph 90+E. Dans la suite, on considèrera donc deux entiers naturels A et B tels que A ≤ B.
La calculatrice Graph 90+E. Depuis le 31 août 2018, une mise à jour disponible gratuitement sur le site www.casio-education.fr permet d’y intégrer le nouveau menu de programmation en langage Python
Première méthode : l’addition par itération de l’unité.
Pour additionner nos deux nombres, on prend le plus grand des deux, ici B, et on lui ajoute l’entier 1, ceci A fois (afin de réaliser le moins d’itérations possibles).
Pour calculer 3 + 12, on calcule ainsi successivement 12 + 1 = 13, 13 + 1 = 14, 14 + 1 = 15. Donc 3 + 12 = 15. Ce qui donne en Python :
Seconde méthode : l’addition posée avec retenue.
En tant que lecteur de Tangente, vous savez bien sûr poser une addition avec retenue sans difficulté. Mais si on vous demandait d’expliquer comment faire à un enfant, comment procéderiez-vous?
Commençons par un exemple. Pour calculer 127 + 59, cela donne dans le détail :
Ici, on ne considère plus les chiffres comme des nombres mais comme des symboles et on applique la méthode suivante :
Pour additionner A et B, on commence par ajouter autant de 0 que nécessaire à A pour que les deux nombres aient « la même taille », c’est-à-dire le même nombre de chiffres) ;
On additionne ensuite deux à deux les chiffres des deux nombres en commençant par la droite (en utilisant la méthode 1), et on ajoute la retenue s’il y en a une ;
On pose le chiffre le plus à droite du résultat ;
Si le résultat a plus de deux chiffres, on pose une nouvelle retenue ;
On passe enfin aux chiffres d’à côté ;
Lorsqu’il ne nous reste plus de chiffre, on regarde si on a encore une retenue. Si c’est le cas, on pose 1 devant le résultat, sinon on ne fait rien ;
On obtient ainsi le résultat final.
Essayons de formaliser cette deuxième méthode. On considère A = an…a1a0 et
B = bm…b1b0 écrits sous forme décimale, c’est-à-dire où a0, a1… an, et b0, b1… bm sont respectivement les chiffres, compris entre 0 et 9, de A et B.
Par hypothèse, A possède moins de chiffres (au sens large) que B. On commence par ajouter des 0 à gauche de A de sorte que les deux nombres soient de la même taille ; A devient 00…0an…a1a0.
Pour i allant de 0 à m, on pose di le chiffre de droite du résultat de l’addition ai + bi (c’est-à-dire le reste de la division euclidienne de ai + bi par 10). On a alors C = cm+1cm…c0 qui est égal à la somme de A et B, où :
•c0 = d0 ;
• ci = di + r pour i allant de 0 à m, avec r la retenue de l’opération précédente (le quotient de la division euclidienne de ai–1 + bi–1 par 10) ;
• cm+1 = r est la dernière retenue.
Pour cette seconde méthode, nous allons essayer de coder l’addition comme on l’apprendrait à un enfant, sans utiliser la division euclidienne. Pour écrire le programme correspondant, on commence par transformer nos nombres en chaînes de caractères (string) avec l’instruction str.
On initialise la retenue à 0 et on crée une chaîne de caractère vide C.
Avec une première boucle for, on ajoute le nombre de 0 nécessaires au début du nombre qui a le moins de chiffres, ici A, pour que les deux entiers aient la même taille m.
La boucle sur A[–j–1], B[–j–1] nous permet de parcourir les deux nombres de droite à gauche (nom_chaîne[–1] retourne le dernier caractère de la chaîne).
On additionne deux à deux les chiffres de chaque entier en utilisant la méthode précédente. Mais avant, nous devons les considérer à nouveau comme des nombres et non pas comme des caractères ! On utilise pour cela la fonction int. À ce résultat, on ajoute la retenue précédente.
On regarde si le résultat s’écrit avec plus de deux chiffres. Si c’est le cas, on met une retenue. Puis on concatène par la gauche C avec ce nouveau résultat.
Enfin, on concatène la dernière retenue à la chaîne C et on transforme cette chaîne en nombre grâce à l’instruction int.
En langage Python, cela donne :
Le lièvre et la tortue ?
Il ne reste plus qu’à tester la vitesse de calcul avec les deux méthodes présentées ! Pour cela, on définit une fonction test qui, pour une fonction fct donnée de deux arguments A et B, calcule n fois la quantité fct(A, B) où n est un entier suffisamment grand (ici, n = 1 000) pour voir émerger un phénomène.
En Python, cela donne :
À vous de réaliser quelques tests en allant télécharger le programme « Vitesse de calcul » sur le site www.casio-education.fr/ ressources de CASIO ! Vous pouvez par exemple effectuer les expériences suivantes avec la Graph 90+E ou avec votre environnement de développement Python préféré :
test(add1, 919, 223, 1000) ;
test(add2, 919, 223, 1000);
test(add1, 23, 126, 1000) ;
test(add2, 23, 126, 1000).
Vous risquez d’avoir quelques surprises !