Exemple : l'algorithme d'Euclide

Un des plus anciens algorithmes connus, dû à Euclide, permet de calculer le plus grand commun diviseur de deux entiers 61#61 et 62#62, par itération. L'algorithme utilise deux variables x et y, initialisées aux valeurs 61#61 et 62#62, puis opère itérativement sur ces variables. L'idée de la transformation est de maintenir l'invariant 63#63 et de s'arrêter quand 64#64 auquel cas, 65#65. Euclide savait que si 66#66, 67#67 et que si 68#68, 69#69. D'où l'itération suivante, qu'on peut décrire ainsi en français : « tant que 70#70 et 71#71 sont différents, soustraire le plus petit du plus grand » :

    while (x != y) {
      if (x > y) {
        x = x-y;
      } else {
        y = y-x;
      }
    }

Contrairement au for de l'exemple précédent, il n'est pas évident que cette boucle termine^2.1, c'est-à-dire qu'il n'y ait qu'un nombre fini d'itérations. En effet si 61#61 ou 62#62 est 72#72, la boucle ne termine pas. Supposons que 73#73 et 74#74 ; après initialisation, on a donc 75#75 et 76#76; à chaque itération, si 77#77, 78#78 décroît strictement, mais reste strictement positif. Il y a donc au plus 79#79 itérations avant que la condition ne devienne fausse, c'est-à-dire que 64#64. Ce n'est pas très efficace.

Tout en conservant le même invariant 63#63, on peut choisir d'autres transformations de x et y de sorte que la boucle termine en moins d'itérations ; c'est l'algorithme d'Euclide dans sa version moderne, où l'on remplace la soustraction par le calcul du reste par division entière (opérateur %), en utilisant l'identité 80#80 ; voici ce que donne directement ce remplacement :

    while (x != y) {
      if (x > y) {
        x = x%y;
      } else {
        y = y%x;
      }
    }

Comme 81#81, les tests peuvent être éliminés en faisant en sorte que la valeur de x soit supérieure à celle de y.

  static int pgcd(int x, int y) {
    while (y > 0) {
       int t = x%y;
       x = y;
       y = t;
    }
    return x;
  }

Rappelons que les arguments étant passés par valeur, les affectations aux paramètres x et y ne modifient que des variables locales et en aucune façon les arguments eux-mêmes.