# 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

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 la même année. Elle est spécialement créée pour rechercher une racine carrée à l'aide d'un arithmomètre dont Reuleaux était un ardent promoteur. 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$^,$ 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.

## Algorithme
### Description

L'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

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

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$^2$, 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 : $N={\overline {A_{0}A_{1}\cdots A_{k}}}$ où les $A_{i}$ sont les tranches de 2 chiffres sauf éventuellement pour $A_{0}$. N ayant (k+1) tranches de 2 chiffres, sa racine carrée sera composée de (k+1) chiffres : ${\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 à $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 $A_{0}$ en lui ôtant tous les entiers impairs de 1 à $2c_{0}-1$
Étape 3 : On a ôté ainsi $c_{0}$ nombres impairs et on sait que $c_{0}^{2}\leq A_{0}<(c_{0}+1)^{2}$
Étape 4 : Le résultat de la dernière soustraction est $d_{0}=A_{0}-c_{0}^{2}$. En collant la tranche suivante, on obtient ${\overline {d_{0}A_{1}}}={\overline {A_{0}A_{1}}}-100c_{0}^{2}$ soit le reste obtenu en soustrayant à ${\overline {A_{0}A_{1}}}$ tous les entiers impairs de 1 à $20c_{0}-1$.
Étape 5 : L'entier impair suivant à ôter est $20c_{0}+1$, soit le dernier impair ôté à l'étape 2, $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 ${\overline {A_{0}A_{1}}}$ en ôtant à ${\overline {d_{0}A_{1}}}$tous les entiers impairs à partir de $20c_{0}+1$ jusqu'à $20c_{0}+2c_{1}-1=2{\overline {c_{0}c_{1}}}-1$
Étape 7 : On a ôté ainsi $c_{1}$ nombres impairs supplémentaires et on sait que ${\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 $d_{1}={\overline {A_{0}A_{1}}}-{\overline {c_{0}c_{1}}}^{2}$. En collant la tranche suivante, on obtient ${\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 à ${\overline {A_{0}A_{1}A_{2}}}$ tous les entiers impairs de 1 à $20{\overline {c_{0}c_{1}}}-1$.
Étape 5bis : L'entier impair suivant à ôter est $20{\overline {c_{0}c_{1}}}+1$ soit le dernier impair ôté à l'étape 6, $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

Une variante, utilisée dans la machine à calculer Friden SRW10, permet de n'incrémenter qu'un chiffre à la fois dans les soustractions successives. 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.