C++ ne disposant pas d'un opérateur d'exponentiation, il faut la
programmer, ou bien, dans le cas des nombres flottants, utiliser celle
définie dans la librairie mathématique. Le programme suivant calcule
, pour des entiers
et
avec
, en accumulant (par
multiplication)
dans
, ceci
fois, l'expression
étant
un invariant de boucle :
int exp(int x, int e) { int y = 1; while (e != 0) { y = y*x; e = e-1; } return y; }
Chaque itération effectue une transformation
; par
exemple, le calcul de exp(5,8) effectue les transformations
successives suivantes de
:
int exp_rec_aux(int x, int y, int e) { if (e == 0) { return y; } else { return exp_rec_aux(x, y*x, e-1); } } int exp_rec(int x, int e) { return exp_rec_aux(x,1,e); }
La fonction exp_rec_aux
est une fonction auxiliaire9 qui ne sera appelée que par exp_rec
.
Pour les trois programmes précédents, le nombre d'itérations ou d'appels
récursifs est l'entier . Il est possible d'accélérer
significativement ce calcul en ramenant ce nombre de
à au plus
, grâce à la propriété suivante :
int exp_fastrec_aux(int x, int y, int e) { if (e == 0) { return y; } else if (e % 2 == 1) { return exp_fastrec_aux(x, x*y, e-1); } else { return exp_fastrec_aux(x*x, y, e/2); } }
La version itérative s'écrit facilement à partir de cette version récursive terminale, en remplaçant la liste des arguments des appels récursifs par des affectations appropriées :
int exp_fastiter(int x, int e) { int y = 1; while (e!=0) { if (e%2 == 1) { y = x*y; e = e-1; } else { x = x*x; e = e/2; } } return y; }
Le cas bénéficiant de la plus forte accélération est celui où l'exposant
est une puissance de 2 ; voici la suite des transformations de
pour le calcul de
(en trois itérations au lieu de 8):