Algorithme de la potence
# Algorithme de la potence

L'algorithme de la potence est un algorithme pour extraire la racine n-ième d'un nombre réel. Il doit son nom à la disposition des calculs qui ressemble à celle de la division. En effet, comme ce dernier, il procède en décalant n chiffres du 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. On en trouve mention pour la racine carrée et la racine cubique dans un ouvrage du mathématicien indien Aryabhata, vers 499 apr. J.-C. Il a été utilisé pour le calcul des racines carrées jusqu'au milieu du XXe siècle.

## Principe

Expliquons le principe de l'algorithme sur le calcul de la racine cubique de 3. Nous souhaitons calculer le résultat avec 5 chiffres après la virgule. Ainsi, nous considérons 5 paquets 000 après la virgule, i.e. nous écrivons 3 comme "3.000 000 000 000 000". Le calcul complet se schématise comme une division.

* Pour la première itération, nous considérons 3. On cherche alors le plus grand chiffre β avec $β^3$ ≤ 3 : il s'agit de 1. Ensuite, nous faisons 3-1 = 2 puis nous ramenons le premier bloc 000. Le reste est donc "2 000".
* Pour la seconde itération, nous cherchons le plus grand chiffre β tel que $(1β)^3$ ≤ 3000. Ce plus grand chiffre est 4 puisque $(14)^3$ = 2744 alors que $(15)^3$ = 3375 dépasse 3000. Remarquons que $(14)^3$ = $10^3$ + $3(10×1)^2×4$ $+3(10×1)×4^2$ $+4^3.$ Ainsi, trouver β tel que $(1β)^3$ ≤ 3000, revient à trouver β tel que $3(10×1)^2×β$ $+3(10×1)×β^2$ $+β^3$ ≤ 2000. Le nombre $3(10×1)^2×4$ $+3(10×1)×4^2$ $+4^3$ est 1744. Le reste est donc 256.
* Pour la troisième itération, nous faisons descendre le bloc 000. Le reste est "256 000". Le plus grand β avec $3(10×14)^2×β$ $+3(10×14)×β^2$ $+β^3$ ≤ 256 000 est 4, et ce nombre vaut 241 984. Le nouveau reste est 256 000 - 241 984 = 14 016.
* Pour la quatrième itération, nous faisons descendre le bloc 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 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' la nouvelle valeur de x dans la prochaine itération, obtenue en adjoignant à x le bloc α de chiffres non encore traités, et y' 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 entiers, le cas des nombres décimaux pouvant être réglé en multipliant x par une puissance adéquate de $B^n.$

### Invariant

À chaque itération, la relation $y^{n}\leq x<(y+1)^{n}$ 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 $x'=B^{n}x+\alpha \,$ et un chiffre de la racine sera produit, de sorte que $y'=By+\beta \,$, avec $0\leq \beta <B$. La relation $y^{n}\leq x<(y+1)^{n}$ étant supposée vraie, on choisit $\beta \,$ de façon que $y'^{n}\leq x'<(y'+1)^{n}$. Pour cela, on choisit le plus grand $\beta$ tel que :

    $(By+\beta )^{n}\leq B^{n}x+\alpha \,$

Il reste à vérifier qu'un tel $\beta \,$ est bien un chiffre en base B. $\beta \,$ est bien positif ou nul, car $B^{n}y^{n}\leq B^{n}x+\alpha \,$. $\beta \,$ est également strictement inférieur à B, car, sachant que $\alpha \leq B^{n}-1$ et que $x+1\leq (y+1)^{n}$, on a :

    $(By+\beta )^{n}\leq B^{n}x+\alpha \leq B^{n}x+B^{n}-1=B^{n}(x+1)-1\leq B^{n}(y+1)^{n}-1<B^{n}(y+1)^{n}$

donc

    $By+\beta <B(y+1)=By+B$ et donc $\beta <B$

Enfin, $\beta$ étant maximal, on a bien :

    $y'^{n}=(By+\beta )^{n}\leq B^{n}x+\alpha \ =x'<(By+\beta +1)^{n}=(y'+1)^{n}$

et l'invariant est bien conservé au cours de l'itération.

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

* Soit $\alpha \,$ le prochain bloc de chiffres du radicande
* Poser $x'=B^{n}x+\alpha \,$
* Soit $\beta \,$ le plus grand nombre tel que $(By+\beta )^{n}\leq B^{n}x+\alpha \,$
* Poser $y'=By+\beta \,$
* Assigner $x\leftarrow x'\,$ et $y\leftarrow y'\,$

### Économie de la variable x

En posant $r=x-y^{n}$ et $r'=x'-y'^{n}$, la condition $(By+\beta )^{n}\leq B^{n}x+\alpha \,$ est équivalente à $(By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha \,$

et la condition $r'=x'-y'^{n}=B^{n}x+\alpha -(By+\beta )^{n}\,$ est équivalente à $r'=B^{n}r+\alpha -((By+\beta )^{n}-B^{n}y^{n})\,$. 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, $r=x-y^{n}\,$ et $x<(y+1)^{n}\,$ impliquent que $r<(y+1)^{n}-y^{n}\,$ ou $r<ny^{n-1}+O(y^{n-2})\,$, ou $r<nx^{{n-1} \over n}+O(x^{{n-2} \over n})\,$. De plus, le facteur $B^{n}y^{n}\,$ soustrait dans le nouveau test annule celui de $(By+\beta )^{n}\,$, ainsi 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 :

* Initialiser r et y à 0
* Répéter jusqu'à la précision désirée :
   * Soit α le prochain bloc de chiffres du radicande
   * Soit $\beta \,$ le plus grand nombre tel que $(By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha \,$
   * Soit $y'=By+\beta$
   * Soit $r'=B^{n}r+\alpha -((By+\beta )^{n}-B^{n}y^{n})\,$
   * Assigner $y\leftarrow y'\,$ et $r\leftarrow r'\,$

### 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 $(By+\beta )^{n}-B^{n}y^{n}=300y^{2}\beta +30y\beta ^{2}+\beta ^{3}$. La recherche de β se fait par tests successifs, mais après une ou deux itérations, le premier terme dominant dans $(By+\beta )^{n}-B^{n}y^{n}$ est $n(By)^{n-1}\beta$, et on peut obtenir une estimation de β en divisant $Br+\alpha$ par $nB^{n-1}y^{n-1}$.

## 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 dichotomie en effectuant $O(\log(B))$ comparaisons. Chacune exige d'évaluer le nombre$(By+\beta )^{n}-B^{n}y^{n}$. À la ke itération, le nombre y possède k chiffres, et le polynôme $(By+\beta )^{n}-B^{n}y^{n}$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(n^{2})$ et l'addition prend $O(n)$, alors chaque comparaison coûte $O(k^{2}n^{2})$, et donc $O(k^{2}n^{2}\log(B))$ pour choisir β. La portion restante de l'algorithme demande des additions et des soustractions consommant $O(k)$. Donc, chaque itération prend $O(k^{2}n^{2}\log(B))$. 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 $O(k^{3}n^{2}\log(B))$.

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 proportionnel 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égénère en une 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 $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.

## Exemples de calculs

### Racine carrée de 2 en binaire

On a ici B = 2 et n = 2 donc $(By+\beta )^{n}-(By)^{n}=4y\beta +\beta ^{2}$. 4 se note 100 en base 2.

### Racine carrée de 3

On a ici B = 10 et n = 2 donc $(By+\beta )^{n}-(By)^{n}=20y\beta +\beta ^{2}$.

### Racine cubique de 5

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

### Racine quatrième de 7

On a cette fois B = 10 et n = 4 donc $(By+\beta )^{n}-(By)^{n}=4000y^{3}\beta +600y^{2}\beta ^{2}+40y\beta ^{3}+\beta ^{4}$.

