Algorithme de décalage n-racines

Algorithme de décalage n-racines

L'algorithme de décalage n-racines est un algorithme pour extraire la ne racine d'un nombre réel. Itératif, il procède en décalant n chiffres du radicande à partir du chiffre le plus significatif. Ressemblant à la division au long, il retourne un chiffre à chaque itération.

Sommaire

Description

Notation

Posons B la base du système de nombres et n le degré de la racine à extraire. Soit x le radicande à traiter, y la racine extraite jusqu'à maintenant et r le reste. Soit α les prochains n chiffres du radicande, et β le prochain chiffre de la racine. Soit x' la nouvelle valeur de x dans la prochaine itération, y' la nouvelle valeur de y dans la prochaine itération et r' la nouvelle valeur de r dans la prochaine itération. Ces trois nombres sont entiers.

Invariants

À chaque itération, l'invariant y^n + r = x\, est vrai. L'invariant (y+1)^n > x\, sera vrai. Alors, y est le plus grand entier plus petit que la ne racine de x et r est le reste.

Initialisation

Les valeurs initiales de x, y et r sont 0. Pour la première itération, la valeur d'α devrait être le bloc le plus significatif de n chiffres du radicande. Noter que l'alignement se fait à partir de la virgule décimale. Par exemple, dans 123,4 le bloc le plus significatif de 2 chiffres est 01, le prochain est 23 et le troisième est 40.

Boucle principale

À chaque itération, décaler n chiffres du radicande, de façon à avoir x' = B^n x + \alpha\, et 1 chiffre de la racine est produit, c'est-à-dire y' = B y + \beta\,. Il faut choisir \beta\, et r'\, de façon à maintenir les invariants décrits auparavant. Il existe justement un seul choix pour ces deux variables.

Le premier invariant est :

x' = y'^n + r'\,

ou

B^n x + \alpha = (B y + \beta)^n + r'\,

Choisir le plus grand \beta\, de façon à ce que

(B y + \beta)^n \le B^n x + \alpha\,

et poser

r' = B^n x + \alpha - (B y + \beta)^n\,

Un tel \beta\, existe, car si \beta = 0\, alors la condition est B^n y^n \le B^n x + \alpha\,, mais y^n \le x\,, qui est toujours vrai. De même, \beta\, doit être plus petit que B, car si \beta = B\,, alors on a

(B(y+1))^n \le B^n x + \alpha\,

mais le deuxième invariant implique que

B^n x < B^n (y+1)^n\,

et puisque B^n x\, et B^n (y+1)^n\, sont multiples de B^n\,, la différence entre les deux doit être d'au moins B^n\,. Nous avons donc

B^n x + B^n \le B^n (y+1)^n\,
B^n x + B^n \le B^n x + \alpha\,
B^n \le \alpha\,

et 0 \le \alpha < B^n\, par la définition d'\alpha\,. Ce qui est faux, et (B y + \beta)^n\, croit de façon monotone en fonction de \beta\,, ce qui n'est pas vrai pour un \beta\, plus grand. Nous pouvons conclure qu'il existe un entier \gamma\, avec \gamma < B\, tel qu'un entier r' avec r' \ge 0\, existe et que le premier invariant tient si et seulement si 0 \le \beta \le \gamma\,.

Considérons le deuxième invariant:

(y'+1)^n>x'\,

ou

(B y + \beta + 1)^n>B^n x + \alpha\,

Si \beta\, n'est pas le plus grand \beta\, acceptable pour le premier invariant, alors \beta + 1\, est aussi acceptable, et nous avons

(B y + \beta + 1)^n \le B^n x + \alpha\,

Ceci viole le premier invariant. Pour satisfaire les deux invariants, il faut choisir le plus grand \beta\, permis par le premier invariant.

L'existence et l'unicité de \beta\, et r' sont prouvés.

En résumé, à chaque itération :

  1. Soit \alpha\, le prochain bloc de chiffres du radicande
  2. Soit x' = B^n x + \alpha\,
  3. Soit \beta\, le plus grand \beta\, tel que (B y + \beta)^n \le B^n x + \alpha\,
  4. Soit y' = B y + \beta\,
  5. Soit r' = x' - y'^n\,

En notant que x = y^n + r\,, la condition

(B y + \beta)^n \le B^n x + \alpha\,

est équivalente à

(B y + \beta)^n - B^n y^n \le B^n r + \alpha\,

et

r' = x' - y'^n = B^n x + \alpha - (B y + \beta)^n\,

est équivalente à

r' = B^n r + \alpha - ((B y + \beta)^n - B^n y ^n)\,

Donc, x est superflu et puisque r = x - y^n\, et x<(y+1)^n\,, r<(y+1)^n-y^n\, ou r<n y^{n-1}+O(y^{n-2})\,, ou r<n x^{{n-1}\over n} + O(x^{{n-2}\over n})\,. Alors, en utilisant r plutôt que x, il y a économie de temps et d'espace par un facteur 1/n. Aussi, le facteur B^n y^n\, soustrait dans le nouveau test annule celui de (B y + \beta)^n\,, alors la plus grande puissance de y qu'il faut estimer est y^{n-1}\, plutôt que y^n\,.

La forme finale de l'algorithme est :

  1. Initialiser r et y à 0
  2. Répéter jusqu'à la précision désirée :
    1. Soit α le prochain bloc de chiffres du radicande
    2. Soit \beta\, le plus grand \beta\, tel que (B y + \beta)^n - B^n y^n \le B^n r + \alpha\,
    3. Soit y' = By + β
    4. Soit r' = B^n r + \alpha - ((B y + \beta)^n - B^n y^n)\,
    5. Assigner y \leftarrow y'\, et r \leftarrow r'\,
  3. y est le plus grand entier tel que y^n<x B^k\, et y^n+r=x B^k\,, où k est le nombre de chiffres du radicande précédant la virgule qui sont consommées (un nombre négatif si l'algorithme n'a pas atteint la virgule).

Les ne racines avec papier crayon

Tel qu'indiqué plus haut, cet algorithme ressemble à la longue division et sa notation est semblable :

Note : la notation utilisée est courante dans le monde anglo-saxon. La valeur de la racine apparaît au-dessus du symbole de la racine.

     1.  4   4   2   2   4
    ----------------------
  3/ 3.000 000 000 000 000
/\/  1 = 300*(0^2)*1+30*0*(1^2)+1^3
     -
     2 000
     1 744 = 300*(1^2)*4+30*1*(4^2)+4^3
     -----
       256 000
       241 984 = 300*(14^2)*4+30*14*(4^2)+4^3
       -------
        14 016 000
        12 458 888 = 300*(144^2)*2+30*144*(2^2)+2^3
        ----------
         1 557 112 000
         1 247 791 448 = 300*(1442^2)*2+30*1442*(2^2)+2^3
         -------------
           309 320 552 000
           249 599 823 424 = 300*(14422^2)*4+30*14422*(4^2)+4^3
           ---------------
            59 720 728 576

Après une ou deux itérations, le premier terme domine dans (By + β)n − Bnyn, alors nous pouvons obtenir une première estimation de β en divisant Br + α par nBn − 1yn − 1.

Performance

À chaque itération, la tâche qui consomme le plus de temps est le choix de β. Ayant B valeurs possibles, il est possible de trouver β en effectuant O(log(B)) comparaisons. Chacune exige d'évaluer (By + β)n − Bnyn. À la ke itération, y possède k chiffres, et le polynôme peut être évalué en faisant 2n − 4 multiplications d'au plus k(n − 1) chiffres et n − 2 additions d'au plus k(n − 1) chiffres, une fois connues les puissances de y et β jusqu'à n − 1 pour y et n de β. Par ailleurs, les valeurs de β sont peu nombreuses, il est donc possible d'obtenir β dans un temps constant. Les puissances de y peuvent être calculées n − 2 multiplications d'au plus k(n − 1) chiffres. En faisant l'hypothèse qu'une multiplication de n chiffres prend O(n2) et l'addition prend O(n), alors il en coûte O(k2n2) à chaque comparaison, ou O(k2n2log(B)), pour choisir β. La portion restante de l'algorithme demande des additions et des soustractions consommant O(k). Donc, chaque itération prend O(k2n2log(B)). Pour k chiffres, il faut compter O(k3n2log(B)).

La seule mémoire interne nécessaire est r, qui contient O(k) chiffres après la ke itération. Cet algorithme n'ayant pas de limite supérieure sur la mémoire impose une limite supérieure sur le nombre de chiffres que l'on peut calculer de tête, au contraire des algorithmes arithmétiques plus élémentaires. Malheureusement, n'importe quelle machine à états finis avec un intrant périodique ne peut que retourner un extrant périodique. Il n'existe donc pas d'algorithme capable de calculer un nombre irrationnel à partir d'un nombre rationnel. En conséquence, il n'existe pas d'algorithme capable de calculer une racine à l'intérieur d'une mémoire limitée.

Plus la base est grande, plus le temps pour choisir β est grand par un facteur O(log(B)), mais, en même temps, diminue le nombre de chiffres nécessaires pour atteindre la même précision par le même facteur. Puisque l'algorithme est propotionnel au cube du nombre de chiffres, augmenter la base augmente la vitesse d'exécution par le facteur O(log 2(B)).

Cependant, lorsque la base est plus grande que le radicande, l'algorithme dégenère en une dichotomie. À ce moment, il est inutile puisque la dichotomie est plus efficace.

Exemples de calculs

Note: la notation utilisée est couramment utilisée dans le monde anglo-saxon. La valeur de la racine apparaît au-dessus du symbole de la racine.

Racine carrée de 2 en binaire

      1. 0  1  1  0  1
    ------------------
   / 10.00 00 00 00 00     1
/\/   1                  + 1
     -----               ----
      1 00                100
         0               +  0
     --------            -----
      1 00 00             1001
        10 01            +   1
     -----------         ------
         1 11 00          10101
         1 01 01         +    1
         ----------      -------
            1 11 00       101100
                  0      +     0
            ----------   --------
            1 11 00 00    1011001
            1 01 10 01          1
            ----------
               1 01 11 remainder

Racine carrée de 3

     1. 7  3  2  0  5
    ----------------------
   / 3.00 00 00 00 00
/\/  1 = 20*0*1+1^2
     -
     2 00
     1 89 = 20*1*7+7^2
     ----
       11 00
       10 29 = 20*17*3+3^2
       -----
          71 00
          69 24 = 20*173*2+2^2
          -----
           1 76 00
                 0 = 20*1732*0+0^2
           -------
           1 76 00 00
           1 73 20 25 = 20*17320*5+5^2
           ----------
              2 79 75

Racine cubique de 5

     1.  7   0   9   9   7
    ----------------------
  3/ 5.000 000 000 000 000
/\/  1 = 300*(0^2)*1+30*0*(1^2)+1^3
     -
     4 000
     3 913 = 300*(1^2)*7+30*1*(7^2)+7^3
     -----
        87 000
             0 = 300*(17^2)*0+30*17*(0^2)+0^3
       -------
        87 000 000
        78 443 829 = 300*(170^2)*9+30*170*(9^2)+9^3
        ----------
         8 556 171 000
         7 889 992 299 = 300*(1709^2)*9+30*1709*(9^2)+9^3
         -------------
           666 178 701 000
           614 014 317 973 = 300*(17099^2)*7+30*17099*(7^2)+7^3
           ---------------
            52 164 383 027

Racine quatrième de 7

     1.   6    2    6    5    7
    ---------------------------
  4/ 7.0000 0000 0000 0000 0000
/\/  1 = 4000*(0^3)*1+600*(0^2)*(1^2)+40*0*(1^3)+1^4
     -
     6 0000
     5 5536 = 4000*(1^3)*6+600*(1^2)*(6^2)+40*1*(6^3)+6^4
     ------
       4464 0000
       3338 7536 = 4000*(16^3)*2+600*(16^2)*(2^2)+40*16*(2^3)+2^4
       ---------
       1125 2464 0000
       1026 0494 3376 = 4000*(162^3)*6+600*(162^2)*(6^2)+40*162*(6^3)+6^4
       --------------
         99 1969 6624 0000
         86 0185 1379 0625 = 4000*(1626^3)*5+600*(1626^2)*(5^2)+
         -----------------   40*1626*(5^3)+5^4
         13 1784 5244 9375 0000
         12 0489 2414 6927 3201 = 4000*(16265^3)*7+600*(16265^2)*(7^2)+
         ----------------------   40*16265*(7^3)+7^4
          1 1295 2830 2447 6799

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de décalage n-racines de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Algorithme De Décalage N-racines — L algorithme de décalage n racines est un algorithme pour extraire la ne racine d un nombre réel. Itératif, il procède en décalant n chiffres du radicande à partir du chiffre le plus significatif. Ressemblant à la division au long, il retourne un …   Wikipédia en Français

  • Algorithme de decalage n-racines — Algorithme de décalage n racines L algorithme de décalage n racines est un algorithme pour extraire la ne racine d un nombre réel. Itératif, il procède en décalant n chiffres du radicande à partir du chiffre le plus significatif. Ressemblant à la …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Extraction de racine enieme — Extraction de racine énième L extraction de racine énième désigne un ensemble de techniques permettant de calculer la Racine d un nombre positif. Plusieurs méthodes peuvent être employées : la méthode de la potence se présente à la manière d …   Wikipédia en Français

  • Extraction de racine énième — L extraction de racine énième désigne un ensemble de techniques permettant de calculer la Racine d un nombre positif. Plusieurs méthodes peuvent être employées : la méthode de la potence se présente à la manière d une division longue et… …   Wikipédia en Français

  • Racine (Mathématiques) — Racine d un nombre En mathématiques, une racine n ième d un nombre a est un nombre b tel que bn = a, où n est un entier naturel non nul, Selon que l on travaille dans l ensemble des réels positifs, l ensemble des réels ou l ensemble des complexes …   Wikipédia en Français

  • Racine N-ième — Racine d un nombre En mathématiques, une racine n ième d un nombre a est un nombre b tel que bn = a, où n est un entier naturel non nul, Selon que l on travaille dans l ensemble des réels positifs, l ensemble des réels ou l ensemble des complexes …   Wikipédia en Français

  • Racine d'un nombre — En mathématiques, une racine n ième d un nombre a est un nombre b tel que bn = a, où n est un entier naturel non nul, Selon que l on travaille dans l ensemble des réels positifs, l ensemble des réels ou l ensemble des complexes, le nombre de… …   Wikipédia en Français

  • Racine n-ieme — Racine d un nombre En mathématiques, une racine n ième d un nombre a est un nombre b tel que bn = a, où n est un entier naturel non nul, Selon que l on travaille dans l ensemble des réels positifs, l ensemble des réels ou l ensemble des complexes …   Wikipédia en Français

  • Racine n-ième — Racine d un nombre En mathématiques, une racine n ième d un nombre a est un nombre b tel que bn = a, où n est un entier naturel non nul, Selon que l on travaille dans l ensemble des réels positifs, l ensemble des réels ou l ensemble des complexes …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”