Comparer, sur les mêmes couples, le PGCD par soustractions et…

def pgcd_euclide(a, b):
    """PGCD par restes. Rend (pgcd, nombre de tours).

    Precondition : a >= 1 et b >= 1.
    Invariant    : pgcd(a, b) est inchange, car pgcd(a, b) = pgcd(b, a % b).
    Variant      : b, entier positif strictement decroissant.
    """
    assert a >= 1 and b >= 1
    tours = 0
    while b != 0:
        a, b = b, a % b
        tours = tours + 1
    return a, tours

for a in range(1, 120):
    for b in range(1, 120):
        assert pgcd_euclide(a, b)[0] == math.gcd(a, b)

Les $14161$ cas passent, et pgcd_euclide(48, 18) rend (6, 3) — trois tours contre quatre pour les soustractions.

L'écart, lui, est sans commune mesure. Sur $(1,1000)$ : 999 tours par soustractions, 2 par Euclide. La raison tient à la ligne a, b = b, a % b : le reste fait d'un coup ce que les soustractions font une par une. Le variant $b$ est au moins divisé par deux tous les deux tours, alors que $a+b$ ne diminuait que de $1$ par tour.

Le pire cas d'Euclide. Il est atteint sur les couples de nombres de Fibonacci consécutifs : $(89,55)$ demande $9$ tours, autant que les soustractions — c'est le seul type de couple où les deux méthodes coïncident, précisément parce que chaque reste y est le terme précédent de la suite. C'est le résultat de Gabriel Lamé (1844), l'une des premières analyses de coût d'un algorithme.

L'affectation multiple a, b = b, a % b est celle du chapitre 4 : le membre de droite est évalué entièrement d'abord, ce qui évite la variable temporaire. Écrire les deux affectations à la suite, dans le mauvais ordre, donnerait un résultat faux.