Extraction de racine carrée par la méthode du goutte à goutte

La technique du goutte à goutte est un algorithme permettant d'extraire la racine carrée d'un nombre décimal.

Historique[modifier | modifier le code]

Cette méthode a été mise au point en 1865 par August Toepler (en) et publiée par Franz Reuleaux dans les Verhandlungen des Vereins zur Beförderung des Gewerbfleißes in Preußen^[1] la même année^[2]. Elle est spécialement créée pour rechercher une racine carrée à l'aide d'un arithmomètre dont Reuleaux était un ardent promoteur^[3]. Mais elle peut tout aussi bien s'effectuer à la main.

On lui donne parfois le nom d'extraction par la méthode du goutte à goutte^[4],[5] car elle permet, petit à petit (goutte à goutte) , d'obtenir les décimales successives d'une racine carrée uniquement à l'aide d'un nombre modéré de soustractions^[6].

Algorithme[modifier | modifier le code]

Description[modifier | modifier le code]

L'algorithme consiste à effectuer ces étapes :

1. Découper le nombre en tranches de 2 chiffres à partir de la virgule
2. Prendre la tranche la plus à gauche et lui retrancher les nombres impairs successifs tant que cela est possible
3. Le nombre de soustractions effectuées est le chiffre le plus à gauche de la racine
4. Au résultat des soustractions effectuées à l'étape 2, coller la tranche suivante
5. Prendre le dernier nombre impair utilisé, lui ajouter 1, multiplier par 10 et ajouter 1
6. Au nombre ainsi obtenu, retrancher, tant que cela est possible, les nombres impairs à partir du nombre impair obtenu à l'étape 5 - Le nombre de soustractions effectuées est le chiffre suivant de la racine
7. Recommencer à partir de l'étape 4

Remarque : Si le résultat des soustractions est 0 et que les tranches restantes ne comportent que des zéros, on arrête les calculs et on écrit des zéros à droite des chiffres déjà obtenus de la racine (autant que de tranches restantes)

Exemple[modifier | modifier le code]

On applique l’algorithme au nombre 71214,28.

• Étape 1 : 71214,28 est découpé en tranches de 2 chiffres, soit 7, 12, 14 et 28. 7 est la tranche la plus à gauche.
• Étape 2 : La suite des entiers positifs impairs commencent par 1, 3, 5, 7... On va donc commencer par soustraire à 7 le nombre 1 puis 3 et ainsi de suite jusqu'à ce que le résultat soit négatif.

7 - 1 - 3 = 3 > 0 et 7 - 1 - 3 - 5 = -2 < 0

Il y a donc 2 soustractions à faire.

• Étape 3 : 2 (nombre de soustractions) est le chiffre le plus à gauche de la racine de 71214,28.
• Étape 4 : 3 est le résultat des soustractions. Avec la deuxième tranche (12), on obtient 312.
• Étape 5 : 3 est le dernier nombre impair retranché. (3+1)×10+1 = 41. 41 va être utilisé à l'étape 6.
• Étape 6 : 312-41-43-45-47-49-51 = 36 il y a 6 soustractions donc 6 est le chiffre suivant de la racine.
• Étape 4 : 36 est le résultat des soustractions. Avec la tranche suivante, on obtient 3614
• Étape 5 : 51 est le dernier nombre impair retranché. (51 + 1)×10+1 = 521
• Étape 6 : 3614-521-523-525-527-529-531 = 458 il y a 6 soustractions donc 6 est le chiffre suivant de la racine (266)
• Étape 4 : 458 est le résultat des soustractions. Avec la tranche suivante (28), on obtient 45828. La tranche 28 étant constituée du chiffre des dixièmes et de celui des centièmes du nombre dont on cherche la racine carrée, le chiffre obtenu sera le chiffre des dixièmes de la racine carrée.
• Étape 5 : 531 est le dernier nombre impair retranché. (531+1)×10+1 = 5321
• Étape 6 : 45828-5321-5323-5325-5327-5329-5331-5333-5335 = 3204, soit 8 soustractions donc 8 est le chiffre suivant de la racine (266,8)

et ainsi de suite ... La racine carrée de 71214,28 vaut environ 266,86003822... On s'aperçoit que les décimales sont exactes.

Preuve de l'algorithme[modifier | modifier le code]

L'algorithme est basé d'une part sur la propriété que la somme des n premiers nombres impairs (de 1 à 2n – 1) est n², et d'autre part que lorsqu'on change de tranche (2 chiffres), cela correspond à un changement d'un chiffre pour la racine.

Remarquons que lorsqu'on a un nombre à virgule, on peut se ramener à un nombre entier par un décalage de la virgule par tranche de 2 chiffres : cela correspond à un décalage de la virgule d'1 chiffre pour la racine carrée. En pratique, le passage de la virgule consiste à mettre une virgule dans la racine (voir l'exemple).

Pour la justification, appelons N un nombre entier dont on cherche la racine carrée.

Étape 1 : On sépare N en tranches de 2 chiffres à partir du chiffre des unités : ${\displaystyle N={\overline {A_{0}A_{1}\cdots A_{k}}}}$ où les ${\displaystyle A_{i}}$ sont les tranches de 2 chiffres sauf éventuellement pour ${\displaystyle A_{0}}$. N ayant (k+1) tranches de 2 chiffres, sa racine carrée sera composée de (k+1) chiffres : ${\displaystyle {\overline {c_{0}c_{1}\cdots c_{k}}}}$. Le découpage par tranches de 2 chiffres va permettre de trouver des approximations par défaut successives de la racine carré de N à ${\displaystyle 10^{i}}$ près, de i égal k à 0.

Étape 2 : On trouve une approximation par défaut à l'unité de la racine carré de ${\displaystyle A_{0}}$ en lui ôtant tous les entiers impairs de 1 à ${\displaystyle 2c_{0}-1}$

Étape 3 : On a ôté ainsi ${\displaystyle c_{0}}$ nombres impairs et on sait que ${\displaystyle c_{0}^{2}\leq A_{0}<(c_{0}+1)^{2}}$

Étape 4 : Le résultat de la dernière soustraction est ${\displaystyle d_{0}=A_{0}-c_{0}^{2}}$. En collant la tranche suivante, on obtient ${\displaystyle {\overline {d_{0}A_{1}}}={\overline {A_{0}A_{1}}}-100c_{0}^{2}}$ soit le reste obtenu en soustrayant à ${\displaystyle {\overline {A_{0}A_{1}}}}$ tous les entiers impairs de 1 à ${\displaystyle 20c_{0}-1}$.

Étape 5 : L'entier impair suivant à ôter est ${\displaystyle 20c_{0}+1}$, soit le dernier impair ôté à l'étape 2, ${\displaystyle 2c_{0}-1}$, auquel on a ajouté 1, résultat qu'on a multiplié par 10 et auquel on ajoute de nouveau 1.

Étape 6 : On trouve une approximation par défaut à l'unité de la racine carré de ${\displaystyle {\overline {A_{0}A_{1}}}}$ en ôtant à ${\displaystyle {\overline {d_{0}A_{1}}}}$tous les entiers impairs à partir de ${\displaystyle 20c_{0}+1}$ jusqu'à ${\displaystyle 20c_{0}+2c_{1}-1=2{\overline {c_{0}c_{1}}}-1}$

Étape 7 : On a ôté ainsi ${\displaystyle c_{1}}$ nombres impairs supplémentaires et on sait que ${\displaystyle {\overline {c_{0}c_{1}}}^{2}\leq {\overline {A_{0}A_{1}}}<({\overline {c_{0}c_{1}}}+1)^{2}}$

Étape 4bis : Le résultat de la dernière soustraction est ${\displaystyle d_{1}={\overline {A_{0}A_{1}}}-{\overline {c_{0}c_{1}}}^{2}}$. En collant la tranche suivante, on obtient ${\displaystyle {\overline {d_{1}A_{2}}}={\overline {A_{0}A_{1}A_{2}}}-100{\overline {c_{0}c_{1}}}^{2}}$ soit le reste obtenu en soustrayant à ${\displaystyle {\overline {A_{0}A_{1}A_{2}}}}$ tous les entiers impairs de 1 à ${\displaystyle 20{\overline {c_{0}c_{1}}}-1}$.

Étape 5bis : L'entier impair suivant à ôter est ${\displaystyle 20{\overline {c_{0}c_{1}}}+1}$ soit le dernier impair ôté à l'étape 6, ${\displaystyle 2{\overline {c_{0}c_{1}}}-1}$, auquel on a ajouté 1, résultat qu'on a multiplié par 10 et auquel on ajoute de nouveau 1.

etc.

Si le dernier reste est nul et qu'il n'y a plus de tranche non nulle à coller, la racine carrée est exacte.

Variante par 5[modifier | modifier le code]

Une variante, utilisée dans la machine à calculer Friden SRW10, permet de n'incrémenter qu'un chiffre à la fois dans les soustractions successives^[7]. Elle consiste à multiplier N par 5 et à lui ôter tous les entiers de la forme 10k+5. Pour reprendre l'exemple de 71214,28. On multiplie ce nombre par 5, on obtient 356071,4.

• On coupe ce nombre par tranches de 2 chiffres 35 60 71,40

• A la tranche 35, on ôte les entiers à partir de 5 par pas de 10

• la première décimale de √71214,28 est 2
• On abaisse la tranche suivante et on obtient le nombre 1560. À ce nombre, on ôte les entiers à partir de 205 par pas de 10

• Les deux premières décimales de √71214,28 sont 26
• On abaisse la tranche suivante et on obtient 18071. À ce nombre, on ôte les entiers à partir de 2605 par pas de 10

• Les trois premières décimales de √71214,28 sont 266
• On abaisse la tranche suivante, après la virgule, et on obtient 229140. À ce nombre, on ôte les entiers à partir de 26605 par pas de 10

• Une approximation au dixième de √71214,28 est 266,8

Ainsi de suite.

Références[modifier | modifier le code]

Sources[modifier | modifier le code]

• « Racine carrée - Appel aux impairs - Méthode du goutte à goutte », sur Gérard Willemin, Nombres, curiosités, théorie et usages (consulté le 16 avril 2021);
• Hervé Lehning, « Les racines au goutte à goutte », Bibliothèque Tangente, n^o 22,‎ 2012, p. 88-90 (ISSN 2263-4908);
• André Devaux, « Evolution des machines à calculer mécaniques », Bulletin de l'APMEP - Ateliers des Journées APMEP de Clermont-Ferrand 2006, n^o 471,‎ 2007, p. 88-90 (en détaillé 1-13) (ISSN 2263-4908, lire en ligne);
• Pierre Ageron, « L’arithmomètre de Thomas : sa réception dans les pays méditerranéens (1850-1915), son intérêt dans nos salles de classe », History and Pedagogy of Mathematics,‎ 2016, p. 1-17 (HAL hal-1349266, lire en ligne);
• (de) Franz Reuleaux, « Toepler's Verfahren der Wurzelausziehung mittelst der Thomas'schen Rechenmaschine. », Aus den Verhandlungen des Vereins zur Beförderung des Gewerbfleißes in Preußen, n^o 44,‎ 1865, p. 112-116 (lire en ligne);
• IREM de Caen Normandie, « Mathématiques de Secondes appuyées sur l'histoire : Recueils de textes historiques (première partie) », Stage du plan académique de formation, sur IREM de l'université de Caen, février mars 2020 (consulté le 16 avril 2021), p. 6-9;
• (de) Quadratwurzel mit mechanischer Rechenmaschine, Kijo sur Youtube (7 décembre 2013) “Utilisation de la méthode de Toepler avec un arithmomètre”

Voir aussi[modifier | modifier le code]

• Méthode de Héron

• Portail de l'informatique théorique
• Arithmétique et théorie des nombres