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
modifierCette 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
modifierDescription
modifierL'algorithme consiste à effectuer ces étapes :
- Découper le nombre en tranches de 2 chiffres à partir de la virgule
- Prendre la tranche la plus à gauche et lui retrancher les nombres impairs successifs tant que cela est possible
- Le nombre de soustractions effectuées est le chiffre le plus à gauche de la racine
- Au résultat des soustractions effectuées à l'étape 2, coller la tranche suivante
- Prendre le dernier nombre impair utilisé, lui ajouter 1, multiplier par 10 et ajouter 1
- 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
- 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
modifierOn 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
modifierL'algorithme est basé d'une part sur la propriété que la somme des n premiers nombres impairs (de 1 à 2n – 1) est n2, 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 : où les sont les tranches de 2 chiffres sauf éventuellement pour . N ayant (k+1) tranches de 2 chiffres, sa racine carrée sera composée de (k+1) chiffres : . Le découpage par tranches de 2 chiffres va permettre de trouver des approximations par défaut successives de la racine carré de N à près, de i égal k à 0.
Étape 2 : On trouve une approximation par défaut à l'unité de la racine carré de en lui ôtant tous les entiers impairs de 1 à
Étape 3 : On a ôté ainsi nombres impairs et on sait que
Étape 4 : Le résultat de la dernière soustraction est . En collant la tranche suivante, on obtient soit le reste obtenu en soustrayant à tous les entiers impairs de 1 à .
Étape 5 : L'entier impair suivant à ôter est , soit le dernier impair ôté à l'étape 2, , 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 en ôtant à tous les entiers impairs à partir de jusqu'à
Étape 7 : On a ôté ainsi nombres impairs supplémentaires et on sait que
Étape 4bis : Le résultat de la dernière soustraction est . En collant la tranche suivante, on obtient soit le reste obtenu en soustrayant à tous les entiers impairs de 1 à .
Étape 5bis : L'entier impair suivant à ôter est soit le dernier impair ôté à l'étape 6, , 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
modifierUne 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
35 | 30 | 15 |
5 | 15 |
- 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
1560 | 1355 | 1140 | 915 | 680 | 435 | 180 |
205 | 215 | 225 | 235 | 245 | 255 |
- 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
18071 | 15466 | 12851 | 10226 | 7591 | 4946 | 2291 |
2605 | 2615 | 2625 | 2635 | 2645 | 2655 |
- 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
229140 | 202535 | 175920 | 149295 | 122660 | 96015 | 69960 | 43295 | 16620 |
26605 | 26615 | 26625 | 26635 | 26645 | 26655 | 26665 | 26675 |
- Une approximation au dixième de √71214,28 est 266,8
Ainsi de suite.
Références
modifier- Actes de l'Association pour la promotion de l'industrie en Prusse
- Reuleaux 1865.
- Ageron 2016, p. 5.
- Willemin.
- Lehning 2012.
- Présentation sur Publimath de l'article d'Hervé Lehning «Les racines au goutte à goutte»
- Deveaux 2007, p. 11.
Sources
modifier- « Racine carrée - Appel aux impairs - Méthode du goutte à goutte », sur Gérard Willemin, Nombres, curiosités, théorie et usages (consulté le );
- Hervé Lehning, « Les racines au goutte à goutte », Bibliothèque Tangente, no 22, , 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, no 471, , 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, , 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, no 44, , 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 ), p. 6-9;
- (de) Quadratwurzel mit mechanischer Rechenmaschine, Kijo sur Youtube () : « Utilisation de la méthode de Toepler avec un arithmomètre »