Extraction de racine carrée

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 Modèle:Mvar est identique à la résolution de l'équation Modèle:Math. 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) Modèle:Math, il convient dès lors de considérer la suite définie par récurrence de la façon suivante : Modèle:Retrait de premier terme Modèle:Mvar choisi si possible « assez proche » de Modèle:Sqrt, en général la partie entière de Modèle:Sqrt.

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 Modèle:S-, une correction différente de la méthode de Héron, la nouvelle valeur approchée étant $r+s-\frac{s^2}{2(r+s)}$. Elle est équivalente à appliquer deux fois de suite la méthode de Héron. L'itération de cette dernière méthode donne une vitesse de convergence bi-quadratique :

$\sqrt{a^2+\gamma }=a+\frac{\gamma }{2a}-\frac{(\gamma /2a{)}^2}{2(a+\gamma /2a)}.$

Approximation de Modèle:Racine à l'aide de suites adjacentes

On considère les suites Modèle:Math et Modèle:Math définies par :

• $u_0=1,v_0=a$,
• $u_{n+1}=\frac{2}{\frac{1}{u_n}+\frac{1}{v_n}}$ est la moyenne harmonique de Modèle:Mvar et Modèle:Mvar,
• $v_{n+1}=\frac{u_n+v_n}{2}$ est la moyenne arithmétique de Modèle:Mvar et Modèle:Mvar.

Les suites Modèle:Math et Modèle:Math sont adjacentes, et convergent vers la même limite : Modèle:Sqrt. L'erreur est majorée par la différence Modèle:Mvar. La suite Modèle:Math n'est autre que la suite obtenue en itérant la méthode de Héron à partir de la valeur Modèle:Math.

On peut remarquer l'originalité de cette présentation qui mêle moyennes harmonique, géométrique et arithmétique. En effet, Modèle:Sqrt n'est autre que la moyenne géométrique de Modèle:Math et de Modèle:Math, et si l'on remplace Modèle:Math par un réel strictement positif quelconque Modèle:Math, les suites Modèle:Math et Modèle:Math convergent vers la moyenne géométrique Modèle:Sqrt de Modèle:Math et Modèle:Math.

Algorithmes utilisant la notation décimale

Algorithme de la potence

Modèle:Article détaillé 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 Modèle:Ap JC Il a été utilisé pendant plusieurs siècles et jusqu'au milieu du Modèle:S-, 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 Modèle:Mvar 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 Modèle:Mvar tel que le nombre Modèle:Math ne dépasse pas le reste courant ;
• on complète Modèle:Mvar en plaçant la décimale Modèle:Mvar à sa droite, pour former le nouveau résultat intermédiaire ;
• on soustrait Modèle:Mvar 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.

Modèle:Démonstration/début (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)

1	52	,27	56	Modèle:BleuModèle:Rouge,Modèle:VertModèle:Tangerine		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 Modèle:Bleu. On complète r.
-1				Modèle:Bleu×Modèle:Bleu=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 Modèle:Rouge. On complète r.
-	44			2Modèle:Rouge×Modèle:Rouge=44		On ôte y (=44) au reste courant et on abaisse la tranche suivante. On place la virgule dans r.
	8	27		24?×?		r=12, on cherche le plus grand x tel que (240+x)x, noté y, ne dépasse pas 827. C'est Modèle:Vert. On complète r.
	-7	29		24Modèle:Vert×Modèle:Vert=729		On ôte y (=729) au reste courant et on abaisse la tranche suivante.
		98	56	246?×?		r=123, on cherche le plus grand x tel que (2460+x)x, noté y, ne dépasse pas 9856. C'est Modèle:Tangerine. On complète r.
	-	98	56	246Modèle:Tangerine×Modèle:Tangerine=9856		On ôte y (=9856) au reste courant
			0			Fin

Jusqu’au Modèle:S- 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 Modèle:Math. Soit Modèle:Mvar le plus grand entier tel que Modèle:Math soit négatif ou nul. La racine de Modèle:Mvar est un réel compris entre Modèle:Mvar et Modèle:Math. On pose alors Modèle:Math, dont on déduit Modèle:Math. La racine carrée de Modèle:Mvar est alors égale à Modèle:Math où Modèle:Mvar est racine du polynôme Modèle:Math.

Si Modèle:Mvar est le plus grand entier tel que Modèle:Math est négatif, la racine de Modèle:Mvar est alors comprise entre Modèle:Math et Modèle:Math. On pose alors Modèle:Math, d'où Modèle:Math, puis on procède par récurrence.

La méthode de Ruffini-Horner permet d'effectuer facilement les changements de variables. Modèle:Démonstration/début

On part de Modèle:Math. Le calcul donne Modèle:Math.

Le changement de variable Modèle:Math dans le polynôme Modèle:Mvar s'effectue selon la méthode de Horner :

Coefficients de P	1	0	− 153,2756
	1	12	144 -152,2756 = -8,2756
	1	12 + 12 = 24
	1

Donc

$P(12+Y/10)=Y^2+240Y-827,56=P_1(Y)$

Le plus grand entier Modèle:Mvar tel que Modèle:Math 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 Modèle:Math dans le polynôme Modèle:Math

Coefficients de Modèle:Math	1	240	− 827,56
	1	3×1+240 = 243	3×243 -827,56 = -98,56
	1	3×1+243 = 246
	1

Donc

$P_1(3+Z/10)=Z^2+2460Z-9856=P_2(Z)$

Or 4 est une racine de Modèle:Math. Donc la racine carrée de 152,2756 est 12,34 Modèle:Démonstration/fin

Extraction par sommes d'impairs successifs

Cette méthode enseignée parfois au Modèle:S 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 Modèle:Mvar, Modèle:Math. 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 Modèle:Mvar, la racine carrée de ce carré immédiatement inférieur. On multiple l'entier Modèle:Mvar trouvé par 10 et on balaie la table des carrés à partir de Modèle:Math (et Modèle:Math) pour s'approcher du nombre formé des deux groupes les plus à gauche. Ce nombre Modèle:Math étant trouvé, on le multiplie par 10 pour parcourir la table des carrés à partir de Modèle:Math, etc.

Modèle:Démonstration/début La racine carrée 1 522 756 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

Modèle:Mvar	Modèle:Math	Modèle:Math
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.

Modèle:Mvar	Modèle:Math	Modèle:Math
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.

Modèle:Mvar	Modèle:Math	Modèle:Math
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 Modèle:Démonstration/fin

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 Modèle:Math, 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 Modèle:Math, soit Modèle:Math, 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 Modèle:Math que de Modèle:Math.

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 Modèle:Math. Il suffira alors de diviser la racine finale par Modèle:Math.

Comme Modèle:Math, on a Modèle:Math. Mais 47 étant plus proche de 49 que de 36, Modèle:Sqrt sera plus proche de 7 que de 6.

Au lieu de commencer à balayer à Modèle:Math et Modèle:Math, on peut, dans ce cas, initier le processus à Modèle:Math : Modèle:Math. On a bien, comme prévu, 4225 < 4700.

L'algorithme (détaillé dans l'exemple ci-dessus) amène, petit à petit, à Modèle:Math auquel on ajoute Modèle:Math, d'où Modèle:Math qui est plus proche de 470000 que Modèle:Math. On en déduit : $\sqrt{4700}\approx 68,6$ 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 Modèle:Math et Modèle:Math définies par :

• $a_0=5m,b_0=5$,
• Si $a_n\ge b_n$ alors $a_{n+1}=a_n-b_n$ et $b_{n+1}=b_n+10$
• Sinon, $a_{n+1}=100a_n$ (ce qui revient à rajouter deux zéros à la fin de $a_n$) et $b_{n+1}=10(b_n-5)+5$ (ce qui revient à insérer un zéro juste avant le dernier chiffre de $b_n$ car cette dernière termine toujours par un 5)

Ainsi, les chiffres de $b_n$ approchent de plus en plus les chiffres de $\sqrt{m}$. À noter que $b_n$ reste un entier (de plus en plus grand) donc ce n'est pas $b_n$ qui tend vers $\sqrt{m}$ mais seulement ses chiffres dans sa représentation décimale. Modèle:Démonstration/début $b_0=5$, $a_0=15$

$n$	$a_n$	$b_n$	Commentaires
0	15	5	On peut soustraire
1	10	15	On ne peut plus soustraire
2	1000	105	On peut soustraire
3	895	115	On peut soustraire
4	780	125	On peut soustraire
5	655	135	On peut soustraire
6	520	145	On peut soustraire
7	375	155	On peut soustraire
8	220	165	On peut soustraire
9	55	175	On ne peut plus soustraire
10	5500	1705	On peut soustraire
11	3795	1715	On peut soustraire
12	2080	1725	On peut soustraire
13	355	1735	On ne peut plus soustraire
14	35500	17305	On peut soustraire
15	18195	17315	On peut soustraire
16	880	17325	on ne peut plus soustraire
...

Si, au lieu de prendre Modèle:Formule, on en prend des troncatures par tranches de deux chiffres et, au lieu d'ajouter à Modèle:Mvar 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

Modèle:Article détaillé 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

On peut également procéder par dichotomie à condition de disposer d'un encadrement de la racine carrée cherchée. On peut pour cela utiliser le nombre de chiffres du nombre dont on cherche la racine carrée. Cette racine aurait moitié moins de chiffres. Ainsi, si le nombre possède 1 024 chiffres, sa racine carrée en possèdera entre 511 et 513. On peut également utiliser d'abord les méthodes précédentes pour obtenir une première valeur approchée de la racine carrée avant de procéder à la dichotomie.

L'algorithme de dichotomie est le suivant. Il évite de procéder à des divisions (autre que la division par 2 qui n'est qu'un décalage de registre si les nombres sont codés en binaire. Cette division est notée shr 1 ci-dessous).

function Racine_64(C: int64): int64;
var
 A, B, D, D2: int64;
begin
  A := borne basse;
  B := borne haute;
  repeat
    D := (A + B) shr 1;
    D2 := D * D; ⇐ on élève au carré avant de tester
    if D2 > C then        
      A := D - 1
    else
      if C > D2 then
        B := D + 1
      else
        Result := A;
  until B > A;
end;

La même méthode s'applique pour les racines n-ièmes, en remplaçant le calcul de D2 = D*D par le calcul de D^n.

La méthode de dichotomie a cependant une vitesse de convergence plus lente que l'itération de la méthode de Héron.

Méthode informatique par décalage des bits

Le code ci-dessous présente un algorithme en C qui extrait la racine carrée d'un nombre entier positif en exécutant des décalages de bits :

// retourne le nombre qui doit être multiplié par lui-même pour atteindre num.
unsigned racine_carree(unsigned num) {
    unsigned a = 0, b = num, c, d;
    for (c = 1 << 30 ; c; c >>= 2) {
        d = a + c;
        a >>= 1;
        if (b >= d) {
            b -= d;
            a += c;
        }
    }
    // la variable b contient le reste.
    return a;
}

Dans d'autres ensembles de nombres

Nombres complexes

Modèle:… Modèle:Article détaillé La racine carrée d'un nombre complexe Modèle:Math sera un nombre complexe Modèle:Math tel que :

$a=x^2-y^{2}b=2xy$

En posant Modèle:Math, le carré du module de Modèle:Mvar, on peut établir une formule générale :

$z=\{\begin{array}{cc}\pm \frac{1}{2}[\sqrt{2(m+a)}+\mathrm{i}\sqrt{2(m-a)}]& \text{si}b>0\\ \pm \frac{1}{2}[\sqrt{2(m+a)}-\mathrm{i}\sqrt{2(m-a)}]& \text{si}b<0\end{array}$

Le calcul revient donc à extraire trois racines carrées : le calcul de Modèle:Mvar, puis les racines carrées de Modèle:Math et Modèle:Math.

Anneaux ℤ/nℤ

On cherche à résoudre l'équation Modèle:Math. On distingue alors trois cas:

• Modèle:Mvar est un nombre premier (par exemple 19) ;
• Modèle:Mvar est une puissance de nombre premier (par exemple 81 = 3⁴) ;
• Modèle:Mvar est un nombre composé (par exemple 35 = 5×7).

S'il existe une solution, c'est-à-dire si Modèle:Mvar est un résidu quadratique modulo Modèle:Mvar, on dispose d'algorithmes efficaces pour la trouver dans les deux premiers cas. Si Modèle:Mvar est un nombre composé, on ne dispose à l'heure actuelle d'un algorithme efficace que si la factorisation de Modèle:Mvar est connue. De plus on peut montrer que s'il existait un algorithme efficace pour calculer une racine carrée sans disposer de la factorisation de Modèle:Mvar, cet algorithme pourrait être utilisé pour obtenir un algorithme efficace de factorisation. On ne pourra donc pas calculer efficacement de racines carrées modulo Modèle:Mvar tant que l'on ne pourra pas factoriser efficacement n'importe quel entier et réciproquement.