En algorithmique et en analyse numérique, l'extraction de racine carrée est le processus qui consiste, étant donné un nombre, à en calculer la racine carrée. Il existe de nombreuses méthodes pour effectuer ce calcul. C'est un cas particulier de la recherche de calcul de la racine n-ième.
Contexte La racine carrée d'un nombre pouvant être un nombre irrationnel, l'extraction de racine carrée est en général approchée.
Définitions L'extraction de la racine carrée d'un nombre est identique à la résolution de l'équation . Les méthodes générales de résolution d'équations polynomiales, et plus généralement les algorithmes de recherche d'un zéro d'une fonction s'appliquent donc. On utilise les mêmes outils pour mesurer les performances des méthodes.
Lorsque l'on ne donne pas de précision supplémentaire, l'extraction de racine carrée se fait dans l'ensemble des nombres réels. On peut cependant s'intéresser à d'autres ensembles de nombres tels que les nombres complexes ou encore les anneaux tels que ℤ/nℤ.
Méthodes dans le cas des nombres réels positifs Méthode de Héron La méthode de Héron est une méthode historique développée par les Babyloniens. En termes plus modernes, c'est un cas particulier de la méthode de Newton.
Pour déterminer la racine carrée du nombre (positif) , il convient dès lors de considérer la suite définie par récurrence de la façon suivante :
de premier terme choisi si possible « assez proche » de , en général la partie entière de .
La vitesse de convergence des approximations successives vers la valeur exacte est quadratique.
Méthode du manuscrit de Bakshali
On trouve dans un manuscrit indien, dit manuscrit de Bakshali, datant peut-être du , une correction différente de la méthode de Héron, la nouvelle valeur approchée étant . Elle est équivalente à appliquer deux fois de suite la méthode de HéronT. Hayashi, The Bakhshali mauscript, an ancient Indian mathematical treatise, John Benjamins Publishing Company, Amsterdam (2005).. L'itération de cette dernière méthode donne une vitesse de convergence bi-quadratique :
Approximation de à l'aide de suites adjacentes
On considère les suites et définies par : , est la moyenne harmonique de et , est la moyenne arithmétique de et . Les suites et sont adjacentes, et convergent vers la même limite : . L'erreur est majorée par la différence . La suite n'est autre que la suite obtenue en itérant la méthode de Héron à partir de la valeur .
On peut remarquer l'originalité de cette présentation qui mêle moyennes harmonique, géométrique et arithmétique. En effet, n'est autre que la moyenne géométrique de et de , et si l'on remplace par un réel strictement positif quelconque , les suites et convergent vers la moyenne géométrique de et .
Algorithmes utilisant la notation décimale Algorithme de la potence
L'introduction de la notation décimale des nombres par position a permis de développer un algorithme tirant parti de cette notation. On en trouve mention dans un ouvrage du mathématicien indien Âryabhata, vers 499 . Il a été utilisé pendant plusieurs siècles et jusqu'au milieu du , avant l'invention des calculateurs électroniques. Âryabhata donne également un algorithme comparable permettant de calculer des racines cubiques.
On sépare les chiffres du nombre par paires en commençant à partir de la virgule. On place le nombre dont on veut extraire la racine en haut, de la même façon que lorsqu'on effectue une division selon la méthode classique ; la racine carrée sera inscrite à la place réservée normalement au diviseur dans une division posée classique.
À chaque étape :
on abaisse la paire de chiffres la plus significative non encore utilisée et on la place au côté d’un reste éventuel de l'étape précédente (initialement nul) ; soit le résultat intermédiaire de la racine carrée obtenu précédemment (égal à zéro au début). On cherche le plus grand chiffre tel que le nombre ne dépasse pas le reste courant ; on complète en plaçant la décimale à sa droite, pour former le nouveau résultat intermédiaire ; on soustrait de la valeur courante pour former le nouveau reste ; si le reste est nul et qu’il n’y a plus de chiffre à abaisser alors l’algorithme se termine sinon on recommence.
(nota : la suite des chiffres constituant la racine s'inscrit au fur et à mesure à la place dévolue au diviseur dans une division classique, et donne le résultat : 12,34. La place de la virgule est significative mais n'a pas besoin d'être prise en compte pendant les calculs, il suffit de la constater à la fin) 152,27 56, Constitution progressive de la racine r. On abaisse la première tranche. 1 ?×? On cherche le plus grand x tel que x² ne dépasse pas 1. C'est . On complète r. -1 ×=1 On ôte x² au reste courant et on abaisse la tranche suivante.0 52 2?×? r=1, on cherche le plus grand x tel que (20+x)x, noté y, ne dépasse pas 52. C'est . On complète r. - 44 2×=44 On ôte y (=44) au reste courant et on abaisse la tranche suivante. On place la virgule dans r. 827 24?×? r=12, on cherche le plus grand x tel que (240+x)x, noté y, ne dépasse pas 827. C'est . On complète r. -7 29 24×=729 On ôte y (=729) au reste courant et on abaisse la tranche suivante. 98 56246?×? r=123, on cherche le plus grand x tel que (2460+x)x, noté y, ne dépasse pas 9856. C'est . On complète r. -98 56246×=9856 On ôte y (=9856) au reste courant 0 Fin
Jusqu’au on utilisait couramment cet algorithme en accélérant les calculs à l’aide d’un abaque formé d’un jeu de réglettes : les bâtons de Napier.
Bien que décrite ici pour des nombres écrits en base 10, la procédure fonctionne dans n’importe quelle base de numération, par exemple la base 2.
Méthode de Ruffini-Horner On pose le problème comme la détermination de la racine positive du polynôme . Soit le plus grand entier tel que soit négatif ou nul. La racine de est un réel compris entre et . On pose alors , dont on déduit . La racine carrée de est alors égale à où est racine du polynôme .
Si est le plus grand entier tel que est négatif, la racine de est alors comprise entre et . On pose alors , d'où , puis on procède par récurrence.
La méthode de Ruffini-Horner permet d'effectuer facilement les changements de variables.
On part de . Le calcul donne .
Le changement de variable dans le polynôme s'effectue selon la méthode de Horner :
Coefficients de P10− 153,2756 112144 -152,2756 = -8,2756 112 + 12 = 24 1
Donc
Le plus grand entier tel que soit négatif est 3 (on cherche une valeur proche de 827/240). La racine cherchée est donc comprise entre 12,3 et 12,4
On effectue le changement de variable dans le polynôme Coefficients de 1240− 827,56 13×1+240 = 2433×243 -827,56 = -98,56 13×1+243 = 246 1
Donc
Or 4 est une racine de . Donc la racine carrée de 152,2756 est 12,34
Extraction par sommes d'impairs successifs Cette méthode enseignée parfois au a l'avantage de se résumer à une série d'additions (au maximum 9 pour chaque décimale cherchée) d'impairs consécutifs.
Elle consiste à exploiter la table des carrés successifs et de leur différence, en remarquant que, pour tout entier , . Balayer la table des carrés consiste donc à ajouter des impairs successifs. Après avoir découpé le nombre en tranches de deux chiffres en commençant par la droite, on recherche le carré immédiatement inférieur au groupe le plus à gauche. Soit , la racine carrée de ce carré immédiatement inférieur. On multiple l'entier trouvé par 10 et on balaie la table des carrés à partir de (et ) pour s'approcher du nombre formé des deux groupes les plus à gauche. Ce nombre étant trouvé, on le multiplie par 10 pour parcourir la table des carrés à partir de , etc.
La racine carrée donnera à un facteur 100 près la racine carrée recherchée. On découpe ce nombre en tranche de 2 chiffres : 1 52 27 56. Le carré le plus proche du premier groupe est 1.
On parcourt alors la table des carrés à partir de 10 pour approcher 152 10 100 21 11 100 + 21 = 121 23 12 121 + 23 = 144 25
Ajouter 25 conduirait à dépasser 152. On passe donc à la dizaine suivante en parcourant la table des carrés à partir de 120 pour approcher 15227.
120 14400 241 121 14400 + 241 = 14641 243 122 14641 + 243 = 14884 245 123 14884 + 245 = 15129 247
Ajouter 247 conduirait à dépasser 15227. On passe donc à la dizaine suivante en parcourant la table des carrés à partir de 1230 pour approcher 1522756.
1230 1512900 2461 1231 1512900 + 2461 = 1515361 2463 1232 1515361 + 2463 = 1517824 2465 1233 1517824 + 2465 = 1520289 2467 1234 1520289 + 2467 = 1522756
1522756 est donc le carré de 1234 et 152,2756 est celui de 12,34
C'est ce même principe qui est utilisé dans l'extraction de racine carrée par la méthode du goutte à goutte.
On peut raccourcir l'exécution de l'algorithme : avant de balayer la table des carrés à partir de , la facile calculabilité des carrés d'entiers se terminant par 5 peut permettre, dans certains cas, de s'affranchir de cinq additions en testant si , soit , reste aussi inférieure (ou pas) au nombre dont on cherche la racine. Si c'est le cas, il vaut mieux poursuivre l'algorithme à partir de que de .
Par exemple, on cherche l'arrondi au dixième près de la racine carrée de 4700. Pour respecter cette précision, on est amené à chercher la racine de . Il suffira alors de diviser la racine finale par .
Comme , on a . Mais 47 étant plus proche de 49 que de 36, sera plus proche de 7 que de 6.
Au lieu de commencer à balayer à et , on peut, dans ce cas, initier le processus à : . On a bien, comme prévu, 4225 < 4700.
L'algorithme (détaillé dans l'exemple ci-dessus) amène, petit à petit, à auquel on ajoute , d'où qui est plus proche de 470000 que . On en déduit : au dixième près.
Extraction par additions et soustractions
Cette méthode très simple a la particularité de n'utiliser que des opérations très simples : addition, soustraction et ajout de 0. Considérons les suites et définies par : , Si alors et Sinon, (ce qui revient à rajouter deux zéros à la fin de ) et (ce qui revient à insérer un zéro juste avant le dernier chiffre de car cette dernière termine toujours par un 5)
Ainsi, les chiffres de approchent de plus en plus les chiffres de . À noter que reste un entier (de plus en plus grand) donc ce n'est pas qui tend vers mais seulement ses chiffres dans sa représentation décimale.
,
Commentaires0 15 5 On peut soustraire1 10 15 On ne peut plus soustraire2 1000 105 On peut soustraire3 895 115 On peut soustraire4 780 125 On peut soustraire5 655 135 On peut soustraire6 520 145 On peut soustraire7 375 155 On peut soustraire8 220 165 On peut soustraire9 55 175 On ne peut plus soustraire10 5500 1705 On peut soustraire11 3795 1715 On peut soustraire12 2080 1725 On peut soustraire13 355 1735 On ne peut plus soustraire14 35500 17305 On peut soustraire15 18195 17315 On peut soustraire16 880 17325 on ne peut plus soustraire...
Si, au lieu de prendre , on en prend des troncatures par tranches de deux chiffres et, au lieu d'ajouter à deux zéros, on abaisse les tranches suivantes, on aboutit à la variante par 5 de la méthode par goutte à goutte.
Méthode par les fractions continues
La fraction continue d'un irrationnel est la suite de ses approximations « optimales » par des fractions, c'est-à-dire que si p/q est une des valeurs de cette suite, alors aucune fraction de a/b avec b < q n'approche plus précisément le réel. Dans le cas particulier des racines carrées, on calcule relativement simplement cette suite, ainsi qu'une sous-suite qui correspond à un cas particulier de la méthode de Héron.
Méthode par dichotomie