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 Il a été utilisé pour le calcul des racines carrées jusqu'au milieu du . 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. —————————————————————— _ / 3. / = (10×)2× +(10×)×2 +3 — 2 1 744 = (10×)2× +(10×)×2 +3 ————— 256 241 984 = (10×)2× +(10×)×2 +3 ——————— 14 016 12 458 888 = (10×)2× +(10×)×2 +3 —————————— 1 557 112 1 247 791 448 = (10×)2× +(10×)×2 +3 ————————————— 309 320 552 249 599 823 424 = (10×)2× +(10×)×2 +3 ——————————————— 59 720 728 576 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 . 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 = 103 + (10×)2× +(10×)×2 +3. Ainsi, trouver β tel que (1β)3 ≤ 3000, revient à trouver β tel que (10×)2×β +(10×)×β2 +β3 ≤ 2000. Le nombre (10×)2× +(10×)×2 +3 est 1744. Le reste est donc 256. Pour la troisième itération, nous faisons descendre le bloc . Le reste est "256 ". Le plus grand β avec (10×)2×β +(10×)×β2 +β3 ≤ 256 est , et ce nombre vaut 241 984.