Accélération logarithmique

 

C ne disposant pas d'une opération d'exponentiation, il faut la programmer (ou utiliser celle définie dans la librairie mathématique dans le cas des nombres flottants). Le programme suivant calcule , pour des entiers x et e avec , en accumulant (par multiplication) x dans y, ceci e 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 (y,e) :

On vérifie l'invariant

On a donc l'égalité de valeur de cet invariant au début de la boucle (quand y=1) et à la fin de la boucle (quand e=0) :

On notera que la version récursive équivalente à ce programme itératif n'est pas celle que l'on écrirait directement à partir de la définition par récurrence de la fonction puissance, mais est la suivante (la boucle du while modifiant les variables y et e, la fonction récursive doit prendre ces valeurs en argument) :

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 e. Il est possible d'accélérer significativement ce calcul en ramenant e à au plus , grâce à la propriété suivante :

Par exemple, en quatre multiplications au lieu de 9. On obtient la définition    

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 :

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 (x,y,e) 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 :

Cet algorithme est décrit dans le Chandah Sutra d'Acharya Pingala (écrit avant 200 ans avant J.C.).