Extraction de racine carrée

procédé de calcul d'une racine carée

En algorithmique et en analyse numérique, l'extraction de racine carrée est le processus qui consiste, étant donnée 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.

ContexteModifier

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éfinitionsModifier

L'extraction de la racine carrée de a 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 positifsModifier

La méthode de HéronModifier

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) a, 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 a, en général la partie entière de a.

La vitesse de convergence des approximations successives vers la valeur exacte est quadratique.

Méthode du manuscrit de BakshaliModifier

On trouve dans un manuscrit indien, dit manuscrit de Bakshali, datant peut-être du VIIe siècle, 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éron[1]. L'itération de cette dernière méthode donne une vitesse de convergence bi-quadratique :

 

Approximation de a à l'aide de suites adjacentesModifier

Considérons les suites u et v définies par :

  •  ,
  •   est la moyenne harmonique de   et  , soit  ,
  •   est la moyenne arithmétique de   et  , soit  .

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

Remarquons l'originalité de cette présentation qui mêle moyennes harmonique, géométrique et arithmétique. En effet, a n'est autre que la moyenne géométrique de 1 et de a, et si l'on remplace   par un réel strictement positif quelconque b, les suites u et v convergent vers la moyenne géométrique ab de a et b.

Algorithmes utilisant la notation décimaleModifier

Algorithme de la potenceModifier

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 apr. J.-C.[2] Il a été utilisé pendant plusieurs siècles et jusqu'au milieu du XXe siècle, 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 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 x tel que le nombre y=(20r + x)x ne dépasse pas le reste courant ;
  • on complète r en plaçant la décimale x à sa droite, pour former le nouveau résultat intermédiaire ;
  • on soustrait 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.

On remarque que la recherche de x en négligeant le terme en x2 n'est autre que la méthode de Héron.[pas clair]

Jusqu’au XXe siècle 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-HornerModifier

Trouver la racine carrée de A, c'est trouver la racine positive du polynôme P(X)= X² - A. Soit a le plus grand entier tel que P(a) soit négatif ou nul. La racine de A est un entier compris entre a et a + 1. On pose alors X = a + Y/10. P(X ) = P(a + Y/10) = P1(Y). La racine carrée de A est alors égale à a + r/10 où r est racine du polynôme P1. Si b est le plus grand entier tel que P1(b) est négatif, la racine de A est alors comprise entre a + b/10 et a + b/10+1/10. On pose alors Y = b + Z/10, P1(Y)=P2(Z). On cherche alors une racine de P2, etc.

La méthode de Ruffini-Horner permet d'effectuer facilement les changements de variables

Extraction par sommes d'impairs successifsModifier

Cette méthode enseignée parfois au XIXe siècle à l'avantage de se résumer à une série d'additions (au maximum 9 pour chaque décimale cherchée) d'impairs consécutifs[3]

Elle consiste à exploiter la table des carrés successifs et de leur différence, en remarquant que  . 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   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   pour parcourir la table des carrés à partir de  , etc.

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 à   près de la racine carrée de  . Pour respecter cette précision, on est amené à chercher la racine de  . Il suffira alors de diviser la racine finale par  .

Comme  , c'est-à-dire  , on a :  . Mais   étant plus proche de   que de  ,   sera plus proche de   que de  .

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

L'algorithme (détaillé dans l'exemple suivant) nous amène, petit à petit, à   auquel on ajoute  , d'où   qui est plus proche de   que  . On en déduit :   à   près.


C'est ce même principe qui est utilisé dans l'extraction de racine carrée par la méthode du goutte à goutte.

Méthode par les fractions continuesModifier

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 dichotomieModifier

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.

Dans d'autres ensembles de nombresModifier

Nombres complexesModifier

Anneaux ℤ/nℤModifier

On cherche à résoudre l'équation  . On distingue alors trois cas[4]:

  •   est un nombre premier (par exemple 19) ;
  •   est une puissance de nombre premier (par exemple 81 = 34) ;
  •   est un nombre composé (par exemple 35 = 5×7).

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

Notes et référencesModifier

NotesModifier

RéférencesModifier

  1. T. Hayashi, The Bakhshali mauscript, an ancient Indian mathematical treatise, John Benjamins Publishing Company, Amsterdam (2005).
  2. W. E. Clarke, The Aryabhatiya of Aryabhata, an ancient Indian work on mathematics and astronomy, University of Chicago, Chicago IL (1930).
  3. Joseph Claudel, Introduction à la science des ingénieurs, Dunod, 1863 pages 86/87
  4. a b c d et e (en) Victor Shoup, A computational introduction to number theory and algebra, Cambridge University Press, , 2e éd., 580 p. (ISBN 9780521516440 et 0521516447, OCLC 277069279, lire en ligne), 12. Quadratic reciprocity and computing modular square roots, chap. 5 (« Computing modular square roots »), p. 350-355.