Voir la source de Algorithme de la potence

L''''algorithme de la potence''' est un [[Algorithmique|algorithme]] pour extraire la [[Racine d'un nombre|racine ''n''-ième]] d'un [[nombre réel]].  Il doit son nom<ref>Jean-Luc Chabert {{et al.}}, ''Histoire d'algorithmes'', Belin, 1993, {{p.|234}}.</ref> à la disposition des calculs qui ressemble à celle de la [[division]]. En effet, comme ce dernier, il procède en décalant ''n'' [[chiffre]]s du [[Racine d'un nombre|radicande]] à partir du chiffre le plus significatif et retourne un chiffre à chaque [[itération]].

Cet algorithme, très ancien, apparaît dès l'introduction de la notation décimale des nombres par position{{Référence nécessaire||date=8 août 2020}}. On en trouve mention pour la [[racine carrée]] et la [[racine cubique]] dans un ouvrage du [[Mathématiques indiennes|mathématicien indien]] [[Aryabhata]], vers 499 {{ap JC}}<ref>{{en}} Walter Eugene Clark, ''[https://archive.org/details/The_Aryabhatiya_of_Aryabhata_Clark_1930 The Aryabhatiya of Aryabhata — An Ancient Indian Work on Mathematics and Astronomy]'', [[University of Chicago Press]], 1930.</ref> Il a été utilisé pour le calcul des racines carrées jusqu'au milieu du {{s-|XX}}.

== Principe ==
Pour expliquer le principe de l'algorithme, on considère le calcul de la racine cubique de 3 avec 5 chiffres après la virgule. Ainsi, on pose 5 paquets 000 après la virgule, i.e. on écrit 3 sous la forme "3.000 000 000 000 000". Le calcul complet se schématise comme une division.
      {{Font color|red||1}}.  {{Font color|green||4}}   {{Font color|blue||4}}   {{Font color|magenta||2}}   {{Font color|gold||2}}   {{Font color|cyan||4}}
     ——————————————————————
 _ {{Font color|#444444||3}}/ 3.{{Font color|darkred||000}} {{Font color|darkgreen||000}} {{Font color|darkblue||000}} {{Font color|darkmagenta||000}} {{Font color|darkcyan||000}}
  \/  {{Font color|red||1}}                        = {{Font color|#444444||3}}(10×{{Font color|gray||0}})<sup>2</sup>×{{Font color|red||1}}     +{{Font color|#444444||3}}(10×{{Font color|gray||0}})×{{Font color|red||1}}<sup>2</sup>     +{{Font color|red||1}}<sup>3</sup>
      —
      2 {{Font color|darkred||000}}
      1 744                    = {{Font color|#444444||3}}(10×{{Font color|red||1}})<sup>2</sup>×{{Font color|green||4}}     +{{Font color|#444444||3}}(10×{{Font color|red||1}})×{{Font color|green||4}}<sup>2</sup>     +{{Font color|green||4}}<sup>3</sup>
      —————
        256 {{Font color|darkgreen||000}}
        241 984                = {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}})<sup>2</sup>×{{Font color|blue||4}}    +{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}})×{{Font color|blue||4}}<sup>2</sup>    +{{Font color|blue||4}}<sup>3</sup>
        ———————
         14 016 {{Font color|darkblue||000}}
         12 458 888            = {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}})<sup>2</sup>×{{Font color|magenta||2}}   +{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}})×{{Font color|magenta||2}}<sup>2</sup>   +{{Font color|magenta||2}}<sup>3</sup>
         ——————————
          1 557 112 {{Font color|darkmagenta||000}}
          1 247 791 448        = {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}{{Font color|magenta||2}})<sup>2</sup>×{{Font color|gold||2}}  +{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}{{Font color|magenta||2}})×{{Font color|gold||2}}<sup>2</sup>  +{{Font color|gold||2}}<sup>3</sup>
          —————————————
            309 320 552 {{Font color|darkcyan||000}}
            249 599 823 424    = {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}{{Font color|magenta||2}}{{Font color|gold||2}})<sup>2</sup>×{{Font color|cyan||4}} +{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}{{Font color|magenta||2}}{{Font color|gold||2}})×{{Font color|cyan||4}}<sup>2</sup> +{{Font color|cyan||4}}<sup>3</sup>
            ———————————————
             59 720 728 576

* Pour la première itération, on considère 3. On cherche alors le plus grand chiffre β avec {{nobr|β<sup>3</sup> ≤ 3}} : il s'agit de 1. Ensuite, on calcule {{nobr|3 – 1 {{=}} 2}} puis on ramène le premier bloc {{Font color|darkred||000}}. Le reste est donc "2 000".  
* Pour la seconde itération, on cherche le plus grand chiffre β tel que {{nobr|(10 + β)<sup>3</sup> ≤ 3000}}. Ce plus grand chiffre est 4 puisque {{nobr|14<sup>3</sup> {{=}} 2744 < 3000 < 15<sup>3</sup> {{=}} 3375}}. On remarque que {{nobr|14<sup>3</sup> {{=}} 10<sup>3</sup> + {{Font color|#444444||3}}(10×{{Font color|red||1}})<sup>2</sup>×{{Font color|green||4}} + {{Font color|#444444||3}}(10×{{Font color|red||1}})×{{Font color|green||4}}<sup>2</sup> + {{Font color|green||4}}<sup>3</sup>}}. Ainsi, trouver β tel que {{nobr|(10 + β)<sup>3</sup> ≤ 3000}}, revient à trouver β tel que {{nobr|{{Font color|#444444||3}}(10×{{Font color|red||1}})<sup>2</sup>×β +{{Font color|#444444||3}}(10×{{Font color|red||1}})×β<sup>2</sup> + β<sup>3</sup> ≤ 2000}}. Le nombre {{Font color|#444444||3}}(10×{{Font color|red||1}})<sup>2</sup>×{{Font color|green||4}} + {{Font color|#444444||3}}(10×{{Font color|red||1}})×{{Font color|green||4}}<sup>2</sup> + {{Font color|green||4}}<sup>3</sup> est 1744. Le reste est donc 256.  
* Pour la troisième itération, on descened le bloc {{Font color|darkgreen||000}}. Le reste est "256 {{Font color|darkgreen||000}}". Le plus grand β avec {{nobr|{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}})<sup>2</sup>×β + {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}})×β<sup>2</sup> + β<sup>3</sup> ≤ 256 {{Font color|darkgreen||000}}}} est {{Font color|blue||4}}, et ce nombre vaut {{formatnum:241984}}. Le nouveau reste est {{nobr|256 {{Font color|darkgreen||000}} – 241984 {{=}} 14016}}.

* Pour la quatrième itération, on fait descendre le bloc {{Font color|darkblue||000}}. Le processus continue de la même manière.

Le résultat approximatif de la racine cubique de 3 est 1,44224.

== Formalisation ==
Soit ''x'' le nombre dont on cherche la racine ''n''-ième que l'on note ''y''. On calcule ''y'' chiffre par chiffre en regroupant  les chiffres de ''x'' par blocs successifs de ''n'' chiffres.

=== Notations ===
On note ''B'' la [[Base (arithmétique)|base]] du système de nombres, ''x'' la partie du radicande déjà traitée, ''y'' la racine extraite jusqu'à maintenant, α le prochain bloc de ''n'' chiffres du radicande, et β le prochain chiffre à déterminer de la racine.  On note ''x''<nowiki>'</nowiki> la nouvelle valeur de ''x'' dans la prochaine itération, obtenue en adjoignant à ''x'' le bloc α de chiffres non encore traités{{Douteux|date=8 août 2020}}, et ''y''<nowiki>'</nowiki> la nouvelle valeur de ''y'' dans la prochaine itération, obtenue en complétant ''y'' par le nouveau chiffre β. Ces nombres peuvent être supposés [[nombre entier|entiers]], le cas des [[Nombre décimal|nombres décimaux]] pouvant être réglé en multipliant ''x'' par une puissance adéquate de ''B<sup>n</sup>''.

=== Invariant ===
À chaque itération, la relation <math>y^n \le x < (y+1)^n</math> est conservée, exprimant le fait que ''y'' est le plus grand entier inférieur ou égal à la racine ''n''-ième de x.

=== Initialisation ===
Les valeurs initiales de ''x'' et ''y'' sont 0. Pour la première itération, la valeur de α est le bloc le plus significatif de ''n'' chiffres du radicande. En cas de nombre décimal, l'alignement se fait à partir de la virgule. 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, on décale de ''n'' chiffres le radicande, de façon à avoir <math>x' = B^n x + \alpha\,</math> et un chiffre de la racine sera produit, de sorte que <math>y' = B y + \beta\,</math>, avec <math>0 \le \beta < B</math>. La relation <math>y^n \le x < (y+1)^n</math> étant supposée vraie, on choisit <math>\beta\,</math> de façon que <math>y'^n \le x' < (y'+1)^n</math>. Pour cela, on choisit le plus grand <math>\beta</math> tel que :

:<math>(B y + \beta)^n \le B^n x + \alpha\,</math>

Il reste à vérifier qu'un tel <math>\beta\,</math> est bien un chiffre en base ''B''. <math>\beta\,</math> est bien positif ou nul, car <math>B^n y^n \le B^n x + \alpha\,</math>. <math>\beta\,</math> est également strictement inférieur à ''B'', car, sachant que <math>\alpha \le B^n-1</math> et que <math>x+1 \le (y+1)^n</math>, on a :
:<math>(By + \beta)^n \le B^nx+\alpha \le B^nx+B^n-1 = B^n(x+1)-1 \le B^n(y+1)^n -1 < B^n(y+1)^n</math>
donc
:<math>By + \beta < B(y+1) = By + B</math> et donc <math>\beta < B</math>

Enfin, <math>\beta</math> étant maximal, on a bien :
:<math>y'^n = (B y + \beta)^n \le B^n x + \alpha\ = x' < (B y + \beta + 1)^n = (y'+1)^n</math>
et l'invariant est bien conservé au cours de l'itération.

En résumé, à chaque itération :
# Soit <math>\alpha\,</math> le prochain bloc de chiffres du radicande
# Poser <math>x' = B^n x + \alpha\,</math>
# Soit <math>\beta\,</math> le plus grand nombre tel que <math>(B y + \beta)^n \le B^n x + \alpha\,</math>
# Poser <math>y' = B y + \beta\,</math>
# Assigner <math>x \leftarrow x'\,</math> et <math>y \leftarrow y'\,</math>

===Économie de la variable ''x'' ===
En posant <math>r = x - y^n</math> et <math>r' = x' - y'^n</math>, la condition <math>(B y + \beta)^n \le B^n x + \alpha\,</math> est équivalente à <math>(B y + \beta)^n - B^n y^n \le B^n r + \alpha\,</math>

et la condition <math>r' = x' - y'^n = B^n x + \alpha - (B y + \beta)^n\,</math> est équivalente à <math>r' = B^n r + \alpha - ((B y + \beta)^n - B^n y ^n)\,</math>. ''r'' s'appelle le reste.

On peut donc remplacer l'utilisation de la variable ''x'' par la variable ''r''. On réalise ainsi une économie de temps et d'espace par un facteur 1/''n''. En effet, <math>r = x - y^n\,</math> et <math>x<(y+1)^n\,</math> impliquent que <math>r<(y+1)^n-y^n\,</math> ou <math>r<n y^{n-1}+O(y^{n-2})\,</math>, ou <math>r<n x^{{n-1}\over n} + O(x^{{n-2}\over n})\,</math>. De plus, le facteur <math>B^n y^n\,</math> soustrait dans le nouveau test annule celui de <math>(B y + \beta)^n\,</math>, ainsi la plus grande puissance de ''y'' qu'il faut estimer est <math>y^{n-1}\,</math> plutôt que <math>y^n\,</math>.

La forme finale de l'algorithme est :
# Initialiser ''r'' et ''y'' à 0
# Répéter jusqu'à la [[précision arithmétique|précision]] désirée :
## Soit α le prochain bloc de chiffres du radicande
## Soit <math>\beta\,</math> le plus grand nombre tel que <math>(B y + \beta)^n - B^n y^n \le B^n r + \alpha\,</math>
## Soit <math>y' = B y + \beta</math>
## Soit <math>r' = B^n r + \alpha - ((B y + \beta)^n - B^n y^n)\,</math>
## Assigner <math>y \leftarrow y'\,</math> et <math>r \leftarrow r'\,</math>

=== Les racines n-ièmes avec papier et crayon ===
Tel qu'indiqué plus haut, cet algorithme ressemble par sa disposition à celle de la division. On donne comme exemple le calcul de la racine cubique de 3. ''x'' vaut 3, complété à droite par des blocs de 000. On a ''B'' = 10 et ''n'' = 3 de sorte que <math>(B y + \beta)^n - B^n y^n= 300y^2\beta + 30y\beta^2+\beta^3</math>. La recherche de β se fait par tests successifs, mais après une ou deux itérations, le premier terme dominant dans 
<math>(B y + \beta)^n - B^n y^n</math> est <math>n(By)^{n-1}\beta</math>, et on peut obtenir une estimation de β en divisant <math>B r + \alpha</math> par <math>n B^{n-1} y^{n-1}</math>.

                            |  1.  4   4   2   2   4              
 3.000 000 000 000 000      |------------------------
 1                          | 1      premier chiffre de y qui vaut désormais 1
 -                          |
 2 000     reste            | 1 744 = 300*1^2*4 + 30*1*4^2 + 4^3   
 1 744                      | donc 4 est le deuxième chiffre, et y prend la valeur 14
 -----                      |  
   256 000    reste         | 241 984 = 300*14^2*4 + 30*14*4^2 + 4^3  
   241 984                  | donc 4 est le troisième chiffre, et y prend la valeur 144
   -------                  |
    14 016 000   reste      | 12 458 888 = 300*144^2*2 + 30*144*2^2 + 2^3 
    12 458 888              | donc 2 est le chiffre suivant, et y prend la valeur 1442
    ----------              |
     1 557 112 000  reste   | 1 247 791 448 = 300*1442^2*2 + 30*1442*2^2 + 2^3
     1 247 791 448          | donc 2 est le chiffre suivant, et y prend la valeur 14422
     -------------          |
       309 320 552 000      | 249 599 823 424 = 300*14422^2*4 + 30*14422*4^2 + 4^3
       249 599 823 424      | donc 4 est le chiffre suivant, et y prend la valeur 144224
       ---------------
        59 720 728 576

== Performance ==

=== Temps d'exécution ===
À 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 β par [[Recherche dichotomique|dichotomie]] en effectuant <math>O(\log(B))</math> comparaisons. Chacune exige d'évaluer le nombre<math>(B y +\beta)^n - B^n y^n</math>. À la k{{e}} itération, le nombre y possède ''k'' chiffres, et le polynôme <math>(B y +\beta)^n - B^n y^n</math>peut être évalué en faisant <math>2 n - 4</math> multiplications d'au plus <math>k(n-1)</math> chiffres et <math>n - 2</math> additions d'au plus <math>k(n-1)</math> chiffres, une fois connues les puissances de ''y'' et β jusqu'à <math>n-1</math> 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 <math>n-2</math> multiplications d'au plus <math>k(n-1)</math> chiffres. En faisant l'hypothèse qu'une multiplication de ''n'' chiffres prend <math>O(n^2)</math> et l'addition prend <math>O(n)</math>, alors chaque comparaison coûte <math>O(k^2 n^2)</math>, et donc <math>O(k^2 n^2 \log(B))</math> pour choisir β. La portion restante de l'algorithme demande des additions et des soustractions consommant <math>O(k)</math>. Donc, chaque itération prend <math>O(k^2 n^2 \log(B))</math>. Ainsi, comme il y a k itérations, la complexité temporelle pour calculer la racine ''n''-ième d'un nombre de ''k'' chiffres écrit en base B, est de <math>O(k^3 n^2 \log(B))</math>.

Plus la base est grande, plus le temps pour choisir β est grand par un facteur <math>O(log(B))</math>, 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 proportionnel au cube du nombre de chiffres, augmenter la base augmente la vitesse d'exécution par le facteur <math>O(\log^2(B))</math>.

Cependant, lorsque la base est plus grande que le radicande, l'algorithme dégénère en une [[recherche dichotomique|dichotomie]]. À ce moment, il est inutile puisque la dichotomie est plus efficace.

=== Mémoire utilisée ===
La seule mémoire interne nécessaire est le reste ''r'', qui contient <math>O(k)</math> chiffres après la ''k''{{e}} 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{{Pas clair|date=août 2020}}, 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.

== Exemples de calculs ==

===[[Racine carrée de 2]] en [[Système binaire|binaire]]===
On a ici ''B'' = 2 et ''n'' = 2 donc <math>(By+\beta)^n-(By)^n = 4y\beta+\beta^2</math>. 4 se note 100 en base 2.
      
                      | 1. 0  1  1  0  1
 10.00 00 00 00 00    |------------------   
  1                   | 1   y prend la valeur 1
  -----               |
  1 00                | 0 = 100*1*0 + 0^2
     0                | donc 0 est le deuxième chiffre et y = 10
  --------            |
  1 00 00             | 1001 = 100*10*1 + 1^2
    10 01             | donc 1 est le deuxième chiffre et y = 101
  -----------         |
     1 11 00          | 10101 = 100*101*1 + 1^2
     1 01 01          | donc 1 est le troisième chiffre et y = 1011
     ----------       |
        1 11 00       | 101100 = 100*1011*0 + 0^2
              0       | donc 0 est le chiffre suivant et y = 10110
        ----------    |
        1 11 00 00    | 1011001 = 100*10110*1 + 1^2
        1 01 10 01    | donc 1 est le chiffre suivant et y = 101101
        ----------
           1 01 11 reste

===[[Racine carrée de 3]]===
On a ici ''B'' = 10 et ''n'' = 2 donc <math>(By+\beta)^n-(By)^n = 20y\beta+\beta^2</math>.

                       | 1. 7  3  2  0  5
 3.00 00 00 00 00      |--------------------
 1                     | 1    est le premier chiffre de y
 -                     |
 2 00                  | 189 = 20*1*7 + 7^2
 1 89                  | donc 7 est le deuxième chiffre et y = 17
 ----                  |
   11 00               | 1 029 = 20*17*3 + 3^2
   10 29               | donc 3 est le troisième chiffre et y = 173
   -----               |
      71 00            | 6 924 = 20*173*2 + 2^2
      69 24            | donc 2 est le chiffre suivant et y = 1732
      -----            |
       1 76 00         | 0 = 20*1732*0 + 0^2
             0         | donc 0 est le chiffre suivant et y = 17320
       -------         |
       1 76 00 00      | 1 732 025 = 20*17320*5 + 5^2
       1 73 20 25      | donc y est le chiffre suivant et y = 173205
       ----------
          2 79 75

===Racine cubique de 5 ===
Elle se traite comme la racine cubique de 3 vue plus haut.

                           |  1.  7   0   9   9   7
 5.000 000 000 000 000     |------------------------
 1                         | 1     est le premier chiffre de y
 -                         |
 4 000                     | 3 913 = 300*1^2*7 + 30*1*7^2 + 7^3
 3 913                     | donc 7 est le deuxième chiffre et y = 17 
 -----                     |
    87 000                 | 0 = 300*17^2*0 + 30*17*0^2 + 0^3
         0                 | donc 0 est le troisième chiffre et y = 170
   -------                 |
    87 000 000             | 78 443 829 = 300*170^2*9 + 30*170*9^2 + 9^3
    78 443 829             | donc 9 est le chiffre suivant et y = 1709
    ----------             |
     8 556 171 000         | 7 889 992 299 = 300*1709^2*9 + 30*1709*9^2 + 9^3
     7 889 992 299         | donc 9 est le chiffre suivant et y = 17099
     -------------         |
       666 178 701 000     | 614 014 317 973 = 300*17099^2*7 + 30*17099*7^2 + 7^3
       614 014 317 973     | donc 7 est le chiffre suivant et y = 170997
       ---------------
        52 164 383 027

=== Racine quatrième de 7 ===
On a cette fois ''B'' = 10 et ''n'' = 4 donc <math>(By+\beta)^n-(By)^n = 4000y^3\beta+ 600y^2\beta^2 + 40y\beta^3 + \beta^4</math>.

                              |  1.   6    2    6    5    7
 7.0000 0000 0000 0000 0000   |-----------------------------
 1                            | 1     est le premier chiffre de y
 1                            |
 -                            |
 6 0000                       | 55 536 = 4000*1^3*6 + 600*1^2*6^2 + 40*1*6^3 + 6^4
 5 5536                       | donc 6 est le deuxième chiffre de y, et y = 16
 ------                       |
   4464 0000                  | 33 387 536 = 4000*16^3*2 + 600*16^2*2^2 + 40*16*2^3 + 2^4
   3338 7536                  | donc 2 est le troisième chiffre de y, et y = 162
   ---------                  |
   1125 2464 0000             | 102 604 943 376 = 4000*162^3*6 + 600*162^2*6^2 + 40*162*6^3 + 6^4
   1026 0494 3376             | donc 6 est le chiffre suivant et y = 1626
   --------------             |
     99 1969 6624 0000        | 86 018 513 790 625 = 4000*1626^3*5 + 600*1626^2*(5^2) + 40*1626*5^3 + 5^4
     86 0185 1379 0625        | donc 5 est le chiffre suivant et y = 16265
     -----------------        |
     13 1784 5244 9375 0000   | 120 489 241 469 273 201 = 4000*16265^3*7 +600*16265^2*7^2 + 40*16265*7^3 + 7^4
     12 0489 2414 6927 3201   | donc 7 est le chiffre suivant et y = 162657
     ----------------------   |
      1 1295 2830 2447 6799   |

==Notes et références ==
{{Traduction/Référence|en|Shifting nth root algorithm|25918574|type=note}}
{{Références}}

==Article connexe==
[[Algorithme de calcul de la racine n-ième]]

{{Portail|informatique théorique|arithmétique}}

{{DEFAULTSORT:Potence, Algorithme}}
[[Catégorie:Algorithme]]
[[Catégorie:Arithmétique]]