Algorithme de décalage n-racines

Un article de Wikipédia, l'encyclopédie libre.

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

[modifier] Description

[modifier] 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.

[modifier] 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.

[modifier] 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.

[modifier] 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 and y to 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).

[modifier] 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.

[modifier] 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.

Prendre note que 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(log2(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.

[modifier] 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.

[modifier] 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

[modifier] 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

[modifier] 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

[modifier] 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

[modifier] Voir aussi

Autres langues