Voir la source de 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 [[Algorithme de calcul de la racine n-ième|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 {{mvar|a}} est identique à la résolution de l'équation {{math|''x''{{2}} – ''a'' {{=}} 0}}. Les méthodes générales de résolution d'équations polynomiales, et plus généralement les [[Algorithme de recherche d'un zéro d'une fonction|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 [[Anneau (mathématiques)|anneaux]] tels que [[Anneau Z/nZ|ℤ/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 [[mathématiques babyloniennes|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) {{math|''a''}}, il convient dès lors de considérer la [[suite définie par récurrence]] de la façon suivante :
{{Retrait|<math>\forall n\in\N\quad x_{n+1}=\frac{x_n+\frac{a}{x_n}}2,</math>}}
de premier terme {{mvar|''x''{{ind|0}} > 0}} choisi si possible « assez proche » de {{sqrt|''a''}}, en général la [[partie entière]] de {{sqrt|''a''}}.

La [[vitesse de convergence des suites|vitesse de convergence]] des approximations successives vers la valeur exacte est [[Vitesse de convergence des suites#Convergence q-quadratique|quadratique]].

=== Méthode du manuscrit de Bakshali ===

On trouve dans un [[manuscrit]] indien, dit manuscrit de Bakshali, datant peut-être du {{s-|VII}}, une correction différente de la méthode de Héron, la nouvelle [[valeur approchée]] étant <math>r+s-\frac{s^2}{2(r+s)}</math>. Elle est équivalente à appliquer deux fois de suite la méthode de Héron<ref>T. Hayashi, ''The Bakhshali mauscript, an ancient Indian mathematical treatise'', John Benjamins Publishing Company, Amsterdam (2005).</ref>. L'itération de cette dernière méthode donne une vitesse de convergence bi-quadratique :
:<math>\sqrt{a^2+\gamma}=a +\frac{\gamma}{2a}-\frac{(\gamma/2a)^2}{2(a+\gamma/2a)}.</math>

=== Approximation de {{racine|''a''}} à l'aide de suites adjacentes ===

On considère les suites {{math|''u''}} et {{math|''v''}} définies par :
* <math>u_0=1, v_0=a</math>,
* <math>u_{n+1} = \frac2{\frac1{u_n} + \frac1{v_n}}</math> est la [[moyenne harmonique]] de {{mvar|u{{ind|n}}}} et {{mvar|v{{ind|n}}}},
* <math>v_{n+1} = \frac{u_n + v_n}2</math> est la [[moyenne arithmétique]] de {{mvar|u{{ind|n}}}} et {{mvar|v{{ind|n}}}}.
Les suites {{math|''u''}} et {{math|''v''}} sont [[Suites adjacentes|adjacentes]], et convergent vers la même limite : {{sqrt|''a''}}. L'erreur est majorée par la différence {{mvar|v{{ind|n}} – u{{ind|n}}}}. La suite {{math|''v''}} n'est autre que la suite obtenue en itérant la méthode de Héron à partir de la valeur {{math|1}}.

On peut remarquer l'originalité de cette présentation qui mêle moyennes harmonique, [[moyenne géométrique|géométrique]] et arithmétique. En effet, {{sqrt|''a''}} n'est autre que la moyenne géométrique de {{math|1}} et de {{math|''a''}}, et si l'on remplace {{math|''u''{{ind|0}}}} par un réel strictement positif quelconque {{math|''b''}}, les suites {{math|''u''}} et {{math|''v''}} convergent vers la moyenne géométrique {{sqrt|''ab''}} de {{math|''a''}} et {{math|''b''}}.

=== Algorithmes utilisant la notation décimale ===
==== Algorithme de la potence ====
{{Article détaillé|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 {{ap JC}}<ref>{{Ouvrage|langue=en|auteur1=W. E. Clarke|titre=The Aryabhatiya of Aryabhata, an ancient Indian work on mathematics and astronomy|lieu=Chicago|éditeur=University of Chicago|année=1930}}.</ref> Il a été utilisé pendant plusieurs siècles et jusqu'au milieu du {{s-|XX}}, avant l'invention des calculateurs électroniques. Âryabhata donne également un algorithme comparable permettant de calculer des [[racine cubique|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 {{mvar|r}} 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]] {{mvar|x}} tel que le nombre {{math|''y'' {{=}} (20''r'' + ''x'')''x''}} ne dépasse pas le reste courant ;
* on complète {{mvar|r}} en plaçant la décimale {{mvar|x}} à sa droite, pour former le nouveau résultat intermédiaire ;
* on soustrait {{mvar|y}} 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.

{{peu clair|On remarque que la recherche de {{mvar|x}} en négligeant le terme en {{math|''x''{{2}}}} n'est autre que la méthode de Héron.}}

{{Démonstration/début|titre=Exemple : {{racine|152,2756}} = 12,34 par la méthode de la potence}}
(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)
{|border ="0" cellspacing = "0" 
|- style="text-align:right"
|1||52||,27|| 56||style="text-align:left;border-left:thin solid black"|{{bleu|1}}{{rouge|2}},{{vert|3}}{{tangerine|4}}|| &nbsp;  ||style="text-align:left| Constitution progressive de la racine ''r''. On abaisse la première tranche.
|- style="text-align:right"
| 1|| || ||  ||style="text-align:left;border-top:thin solid black;border-left:thin solid black"|?×?||  ||style="text-align:left| On cherche le plus grand ''x'' tel que ''x''² ne dépasse pas 1. C'est {{bleu|1}}. On complète ''r''.
|- style="text-align:right"
| -1|| || ||  ||style="text-align:left;border-left:thin solid black"|{{bleu|1}}×{{bleu|1}}=1|| ||style="text-align:left| On ôte ''x''² au reste courant et on abaisse la tranche suivante.
|- style="text-align:right"
|style="border-top:thin solid black"|0|| 52|| ||  ||style="text-align:left;border-left:thin solid black"|2?×?|| ||style="text-align:left|''r''=1, on cherche le plus grand ''x'' tel que (20+''x'')''x'', noté ''y'', ne dépasse pas 52. C'est {{rouge|2}}. On complète ''r''.
|- style="text-align:right"
| - || 44|| ||  ||style="text-align:left;border-left:thin solid black"|2{{rouge|2}}×{{rouge|2}}=44|| ||style="text-align:left| On ôte ''y'' (=44) au reste courant et on abaisse la tranche suivante. On place la virgule dans ''r''.
|- style="text-align:right"
| ||style="border-top:thin solid black"| 8||27 ||  ||style="text-align:left;border-left:thin solid black"|24?×?|| ||style="text-align:left|''r''=12, on cherche le plus grand ''x'' tel que (240+''x'')''x'', noté ''y'', ne dépasse pas 827. C'est {{vert|3}}. On complète ''r''.
|- style="text-align:right"
| || -7 ||29 || ||style="text-align:left;border-left:thin solid black"|24{{vert|3}}×{{vert|3}}=729|| ||style="text-align:left| On ôte ''y'' (=729) au reste courant et on abaisse la tranche suivante. 
|- style="text-align:right"
| || style="border-top:thin solid black"| &nbsp;  ||style="border-top:thin solid black"|98 || 56||style="text-align:left;border-left:thin solid black"|246?×?|| ||style="text-align:left|''r''=123, on cherche le plus grand ''x'' tel que (2460+''x'')''x'', noté ''y'', ne dépasse pas 9856. C'est {{tangerine|4}}. On complète ''r''.
|- style="text-align:right"
|  ||-||98 || 56||style="text-align:left;border-left:thin solid black"|246{{tangerine|4}}×{{tangerine|4}}=9856|| ||style="text-align:left| On ôte ''y'' (=9856) au reste courant 
|- style="text-align:right"
| || ||style="border-top:thin solid black"| ||style="border-top:thin solid black"|0 ||style="text-align:left;border-left:thin solid black"|&nbsp;|| ||style="text-align:left| Fin
|}
{{Démonstration/fin}}

Jusqu’au {{s-|XX}} 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 (arithmétique)|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]] {{math|''P''(''X'') {{=}} ''X''{{2}} – ''a''}}. Soit {{mvar|n}} le plus grand entier tel que {{math|''P''(''n'')}} soit négatif ou nul. La racine de {{mvar|a}} est un réel compris entre {{mvar|n}} et {{math|''n'' + 1}}. On pose alors {{math|''X'' {{=}} ''n'' + ''Y''/10}}, dont on déduit {{math|''P''(''X'') {{=}} ''P''(''n'' + ''Y''/10) {{=}} ''P''<sub>1</sub>(''Y'')}}. La racine carrée de {{mvar|a}} est alors égale à {{math|''n'' + ''r''/10}} où {{mvar|r}} est racine du polynôme {{math|''P''<sub>1</sub>}}.

Si {{mvar|m}} est le plus grand entier tel que {{math|''P''<sub>1</sub>(''m'')}} est négatif, la racine de {{mvar|a}} est alors comprise entre {{math|''n'' + ''m''/10}} et {{math|''n'' + ''b''/10 + 1/10}}. On pose alors {{math|''Y'' {{=}} ''b'' + ''Z''/10}}, d'où {{math|''P''<sub>1</sub>(''Y'') {{=}} ''P''<sub>2</sub>(''Z'')}}, puis on procède par récurrence.

La [[méthode de Ruffini-Horner]] permet d'effectuer facilement les changements de variables.
{{démonstration/début|titre=Exemple : {{racine|152,2756}} = 12,34 par la méthode de Horner}}

On part de {{math|''P''(''X'') {{=}} ''X''{{2}} – 152,2756}}. Le calcul donne {{math|''n'' {{=}} 12}}.

Le changement de variable {{math|''X'' {{=}} 12 + ''Y''/10}} dans le polynôme {{mvar|P}} s'effectue selon la méthode de Horner :

{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de P
|width = "80"|1
|width = "120"|0
|width = "120"|− 153,2756
|-style="text-align:center"
| bgcolor="#b3e2d1" |   ||1||12
|bgcolor="#b3e2d1" |144 -152,2756 = -8,2756
|-style="text-align:center"
| bgcolor="#b3e2d1" |   ||1
|bgcolor="#b3e2d1" |12 + 12 = 24 ||
|-style="text-align:center"
| bgcolor="#b3e2d1" |   
|bgcolor="#b3e2d1"|1|| ||  
|}

Donc
:<math> P(12 + Y/10) = Y^2+240Y -827,56 = P_1(Y)</math>

Le plus grand entier {{mvar|m}} tel que {{math|''P''<sub>1</sub>(''b'')}} 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 {{math|''Y'' {{=}} 3 + ''Z''/10}} dans le polynôme {{math|''P''<sub>1</sub>}}
{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''<sub>1</sub>}}
|width = "80"|1
|width = "120"|240
|width = "120"|− 827,56
|-style="text-align:center"
| bgcolor="#b3e2d1" |   ||1||3×1+240 = 243
|bgcolor="#b3e2d1" |3×243  -827,56 = -98,56
|-style="text-align:center"
| bgcolor="#b3e2d1" | ||1
|bgcolor="#b3e2d1" |3×1+243 = 246|| 
|-style="text-align:center"
| bgcolor="#b3e2d1" |  
|bgcolor="#b3e2d1"|1|| ||  
|}

Donc
:<math> P_1(3 + Z/10) = Z^2+2460Z -9856 = P_2(Z)</math>

Or 4 est une racine de {{math|''P''<sub>2</sub>}}. Donc la racine carrée de 152,2756 est 12,34
{{démonstration/fin}}

==== Extraction par sommes d'impairs successifs ====
Cette méthode enseignée parfois au {{s|XIX|e}} 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<ref>{{Ouvrage|auteur1=Joseph Claudel|titre=Introduction à la science des ingénieurs|éditeur=[[Éditions Dunod|Dunod]]|année=1863|pages totales=86/87|lire en ligne=https://books.google.fr/books?id=R8deXwtIkOwC&pg=PA86}}</ref>.

Elle consiste à exploiter la table des carrés successifs et de leur différence, en remarquant que, pour tout entier {{mvar|n}}, {{math|(''n''+1){{2}} – ''n''{{2}} {{=}} 2''n''+1}}. 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 {{mvar|n}}, la racine carrée de ce carré immédiatement inférieur. On multiple l'entier {{mvar|n}} trouvé par 10 et on balaie la table des carrés à partir de {{math|10''n''}} (et {{math|100''n''{{2}}}}) pour s'approcher du nombre formé des deux groupes les plus à gauche. Ce nombre {{math|''n''{{ind|1}}}} étant trouvé, on le multiplie par 10 pour parcourir la table des carrés à partir de {{math|10''n''{{ind|1}}}}, etc.

{{démonstration/début|titre=Exemple : {{racine|152,2756}} = 12,34 par la méthode de impairs successifs}}
La racine carrée {{formatnum:1522756}} donnera à un facteur 100 près la racine carrée recherchée. On découpe ce nombre en tranche de 2 chiffres : 1&nbsp;52&nbsp;27&nbsp;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
{| class="wikitable"
|-
! {{mvar|n}} !! {{math|''n''{{2}}}} !! {{math|2''n''+1 {{=}} (''n''+1){{2}} – ''n''{{2}}}}
|-
| 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.

{| class="wikitable"
|-
! {{mvar|n}} !! {{math|''n''{{2}}}} !! {{math|2''n''+1 {{=}} (''n''+1){{2}} – ''n''{{2}}}}
|-
| 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.

{| class="wikitable"
|-
! {{mvar|n}} !! {{math|''n''{{2}}}} !! {{math|2''n''+1 {{=}} (''n''+1){{2}} – ''n''{{2}}}}
|-
| 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
{{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 {{math|10''n''}}, 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 {{math|(10''n''+5){{2}}}}, soit {{math|100''n''(''n''+1) + 25}}, 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 {{math|10''n''+5}} que de {{math|10''n''}}.

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 {{math|4700 × 100 {{=}} 470000}}. Il suffira alors de diviser la racine finale par {{math|{{sqrt|100}} {{=}} 10}}.

Comme {{math|6{{2}} {{=}} 36 < 47 < 49 {{=}} 7{{2}}}}, on a {{math|''n'' {{=}} 6}}. Mais 47 étant plus proche de 49 que de 36, {{sqrt|47}} sera plus proche de 7 que de 6.

Au lieu de commencer à balayer à {{math|10''n'' {{=}} 60}} et {{math|100 ''n''{{2}} {{=}} 3600}}, on peut, dans ce cas, initier le processus à {{math|10''n''+5 {{=}} 65}} : {{math|65{{2}} {{=}} 6 × 7 × 100 + 25 {{=}} 4225}}. On a bien, comme prévu, 4225 < 4700.

L'algorithme (détaillé dans l'exemple ci-dessus) amène, petit à petit, à {{math|n{{indexp|4|2}} {{=}} 685{{2}} {{=}} 469225}} auquel on ajoute {{math|2 ''n''{{ind|4}} + 1 {{=}} 1370}}, d'où {{math|''n''{{indexp|5|2}} {{=}} 686{{2}} {{=}} 470595}} qui est plus proche de 470000 que {{math|''n''{{indexp|4|2}}}}. On en déduit : <math>\sqrt{4700} \approx 68,6</math> au dixième près.

==== Extraction par additions et soustractions ====

Cette méthode<ref>{{lire en ligne|lang=en|auteur=Frazer Jarvis|titre=Square roots by subtraction|url=http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf}}</ref> 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 {{math|''a''}} et {{math|''b''}} définies par :
* <math>a_0=5m, b_0=5</math>,
* Si <math>a_n \geq b_n</math> alors <math>a_{n+1} = a_n - b_n</math> et <math>b_{n+1} = b_n + 10</math>
* Sinon, <math>a_{n+1} = 100a_n</math> (ce qui revient à rajouter deux zéros à la fin de <math>a_n</math>) et <math>b_{n+1} = 10(b_n - 5) + 5</math> (ce qui revient à insérer un zéro juste avant le dernier chiffre de <math>b_n</math> car cette dernière termine toujours par un 5)

Ainsi, les chiffres de <math>b_n</math> approchent de plus en plus les chiffres de <math>\sqrt{m}</math>. À noter que <math>b_n</math> reste un entier (de plus en plus grand) donc ce n'est pas <math>b_n</math> qui tend vers <math>\sqrt{m}</math> mais seulement ses chiffres dans sa représentation décimale.
{{démonstration/début|titre=Exemple :{{racine|3}} ≈ 1,732 par additions et soustractions}}
<math> b_0=5</math>, <math>a_0=15</math>

{| class="wikitable alternance center"
|-
!<math>n</math>	!!<math>a_n</math>	!!<math>b_n</math>	!!Commentaires
|-
|0 ||15	||5		|| On peut soustraire
|-
|1	||10	||'''1'''5	|| 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	||'''17'''5	||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	||'''173'''5	||On ne peut plus soustraire
|-
|14	||35500	||17305	||On peut soustraire
|-
|15	||18195	||17315	||On peut soustraire
|-
|16 ||880	||'''1732'''5	|| on ne peut plus soustraire
|-
|...||		||		||
|}

{{Démonstration/fin}}

Si, au lieu de prendre {{formule|5''m''}}, on en prend des troncatures par tranches de deux chiffres et, au lieu d'ajouter à {{mvar|a{{ind|n}}}} deux zéros, on abaisse les tranches suivantes, on aboutit à la [[Extraction de racine carrée par la méthode du goutte à goutte#Variante par 5|variante par 5]] de la méthode par goutte à goutte.

=== Méthode par les fractions continues ===
{{Article détaillé|Fraction continue d'un irrationnel quadratique}}
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, [[Fraction continue d'un irrationnel quadratique#Extraction d'une racine carrée|on calcule relativement simplement]] cette suite, ainsi qu'une [[sous-suite]] qui correspond à un cas particulier de la [[#La méthode de Héron|méthode de Héron]].

=== Méthode par dichotomie ===
On peut également procéder par [[méthode de dichotomie|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 {{formatnum:1024}} 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).
<syntaxhighlight lang="text">
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;
</syntaxhighlight>

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 :

<syntaxhighlight lang="c" line="1">
// 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;
}
</syntaxhighlight>

== Dans d'autres ensembles de nombres ==
=== Nombres complexes ===
{{…}}
{{article détaillé|Racine d'un nombre complexe}}
La racine carrée d'un nombre complexe {{math|''Z'' {{=}} ''a'' + i''b''}} sera un nombre complexe {{math|''z'' {{=}} ''x'' + i''y''}} tel que :
:<math>a = x^2 - y^2\, b = 2xy</math>
En posant {{math|''m''{{2}} {{=}} {{!}}''Z''{{!}}{{2}} {{=}} ''a''{{2}} + ''b''{{2}}}}, le carré du module de {{mvar|Z}}, on peut établir une formule générale :
:<math>
z=\begin{cases}
\pm\frac12\left[\sqrt{2(m+a)} + \mathrm{i}\sqrt{2(m-a)}\right] & \textrm{ si }\ b>0\\
\pm\frac12\left[\sqrt{2(m+a)} - \mathrm{i}\sqrt{2(m-a)}\right] & \textrm{ si }\ b<0
\end{cases}
</math>

Le calcul revient donc à extraire trois racines carrées : le calcul de {{mvar|m}}, puis les racines carrées de {{math|''m'' + ''a''}} et {{math|''m'' – ''a''}}.

=== Anneaux ℤ/nℤ ===
On cherche à résoudre l'équation {{math|''x''{{2}} ≡ ''a'' mod ''n''}}. On distingue alors trois cas<ref name = "shoup">{{Ouvrage|langue=en|prénom1=Victor|nom1=Shoup|lien auteur1=Victor Shoup|titre=A computational introduction to number theory and algebra|éditeur=[[Cambridge University Press]]|année=2009|numéro d'édition=2|pages totales=580|passage=350-355|isbn=9780521516440|isbn2=0521516447|oclc=277069279|lire en ligne=https://shoup.net/ntb/ntb-v2.pdf|consulté le=2020-02-26|partie=12. Quadratic reciprocity and computing modular square roots|numéro chapitre=5|titre chapitre=Computing modular square roots}}.</ref>:
* {{mvar|n}} est un [[nombre premier]] (par exemple 19) ;
* {{mvar|n}} est une [[Puissance d'un nombre|puissance]] de nombre premier (par exemple 81 = 3<sup>4</sup>) ;
* {{mvar|n}} est un [[nombre composé]] (par exemple 35 = 5×7).

S'il existe une solution, c'est-à-dire si {{mvar|a}} est un [[résidu quadratique]] modulo {{mvar|n}}, on dispose d'algorithmes efficaces pour la trouver dans les deux premiers cas. Si {{mvar|n}} est un nombre composé, on ne dispose à l'heure actuelle d'un algorithme efficace que si la [[Décomposition en produit de facteurs premiers|factorisation]] de {{mvar|n}} est connue<ref name = "shoup"/>. De plus on peut montrer que s'il existait un algorithme efficace pour calculer une racine carrée sans disposer de la factorisation de {{mvar|n}}, cet algorithme pourrait être utilisé pour obtenir un [[Algorithme de décomposition en produit de facteurs premiers|algorithme efficace de factorisation]]. On ne pourra donc pas calculer efficacement de racines carrées modulo {{mvar|n}} tant que l'on ne pourra pas factoriser efficacement n'importe quel entier et réciproquement<ref name = "shoup"/>.

== Notes et références ==
{{Crédit d'auteurs|interne|Racine carrée|145701092}}
{{Références}}

{{Portail|mathématiques|informatique théorique}}

[[Catégorie:Racine carrée]]
[[Catégorie:Analyse numérique]]
[[Catégorie:Algorithme numérique]]
[[Catégorie:Algorithme de recherche d'un zéro d'une fonction]]
[[Catégorie:Technique de calcul]]