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 auxiliaire 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 à 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):
La situation est moins favorable quand l'exposant n'est pas une puissance de 2 ; le calcul de se fait en 5 itérations, soit moins de :
La fonction exponentielle croissant très rapidement, on dépasse
facilement les limites de l'arithmétique entière de la machine, et on ne
profite guère de cette accélération. Calculons plutôt , de
façon à rester dans ces limites. Il suffit de placer un %m
après chaque opération. Voici la version récursive terminale de cette
fonction :
static int expmod_fastrec_aux(int x, int y, int e, int m) {
if (e == 0) {
return y;
} else if (e % 2 == 1) {
return expmod_fastrec_aux(x, (x*y) % m, e-1, m);
} else {
return expmod_fastrec_aux((x*x) % m, y, e/2, m);
}
}
int expmod_fastrec(int x, int e, int m) {
return expmod_fastrec_aux(x, 1, e, m);
}
La version itérative s'obtient facilement par dérécursivation de cette
définition récursive terminale :
int expmod_iter(int x, int e, int m) {
int y = 1;
while (e != 0) {
if (e%2 == 1) {
y = (x*y) % m;
e = e-1;
} else {
x = (x*x) % m;
e = e/2;
}
}
return y;
}