Algorithme d'Euclide : Terminaison  Correction  Complexité

I) Présentation

Définition: Le pgcd de deux entiers a et b est le plus grand diviseur d commun à a et b .

pgcd(10,3) = 1 , pgcd(42,35) = 7, et pgcd(a,0) = a pour tout entier a > 0.

  L'algorithme d'Euclide est un algorithme calculant de pgcd de deux entiers naturels. Il s'adapte au calcul du pgcd de deux polynômes et permet la résolution de certaines équations diophantiennes comme le calcul des coefficients de Bezout.

On s'intéresse ici à la terminaison, au coût et à la complexité de l'algorithme d'Euclide.

II) Algorithme d'Euclide

1) Principe

  Le pgcd de a et b est le dernier reste non nul dans la suite des divisions euclidiennes successives a = b q 1 + r 1 ;   b = r 1 q 2 + r 2 ;   r 1 = r 2 q 3 + r 3 ; r 2 = r 3 q 4 + r 4 etc...

  Il repose sur la remarque suivante: si a=b q + r est l'égalité de la divison euclidienne de a par b, alors  pgcd(a, b) = pgcd(b, r). (En effet, l'ensemble des diviseurs de a et b est égal à l'ensemble des diviseurs de b et r)
  Si l'on fait alors les divisions euclidiennes successives:    a = bq 1 + r 1 ;   b = r 1 q 2 + r 2 ;   r 1 = r 2 q 3 + r 3 , etc, on en déduit:
pgcd ( a , b ) = pgcd ( b , r 1 ) = pgcd ( r 1 , r 2 ) = pgcd ( r 2 , r 3 ) =. ..
  Mais b > r 1 > r 2 > r 3 > ... 0 . La suite des restes successifs ( r n ) est une suite strictement décroissante d'entiers. Donc il existe un plus petit entier n tel que r n = 0 . Alors pgcd ( a , b ) = pgcd ( r n - 1 , 0 ) = r n - 1 .
  Le pgcd de a et b est le dernier reste non nul dans la suite des divisions euclidiennes.

La suite ( r n ) des restes successifs est une suite strictement décroissante d'entiers. Donc il existe un plus petit entier n ∈ N * tel que r n = 0 . Alors pgcd ( a , b ) = pgcd ( r n - 1 , 0 ) = r n - 1

2) Exemple

Par exemple, pour 637 et 490:
637 = 1x490 + 147
490 = 3x147 + 49
147 = 3x49 + 0
pgcd(637,490) = pgcd(490,147) = pgcd(147,49) = pgcd(49,0) = 49

Remarque : si  a < b au départ, la première division a pour effet d'échanger a et b

3) Algorithme

L'algorithme d'Euclide est très simple à implémenter

def pgcd(a, b):
    """ Calcul itératif du pgcd par l'algorithme d'Euclide"""
    while b > 0:
        a, b = b, a % b
    return a

III) Terminaison, correction et complexité

Notons a n et b n les valeurs des paramètres a et b après la n ième itération de la boucle while.  
On aura: { a 0 = a b 0 = b et { a n + 1 = b n b n + 1 = a n % b n pour n N , tant que b n 0 .


  On commence par justifier que l'algorithme se termine.

Q1)  Prouver que la quantité b est un variant de la boucle while et donc que l'algorithme se termine.
On note dans la suite N le plus petit entier naturel tel que b N = 0 .

  On prouve ensuite qu'il calcule effectivement le pgcd.

Q2)  Prouver que la propriété   P ( n ) : pgcd ( a n , b n ) = pgcd ( a , b )   est un invariant de boucle. En déduire que l'algorithme est correct.

  Nous allons calculer la complexité de cette fonction pgcd(a,b), et prouver que cette complexité est en O ( ln ( b ) ) .

  Le  coût C ( a , b ) est  le nombre de divisions (on néglige les affectations).  Donc ce coût C ( a , b ) est le nombre d'itérations de la boucle while.

  Nous nous placerons dans le cas où au départ   a b . Lorsque a < b , alors a et b sont échangés à la première itération de la boucle while: on aura a 1 b 1 .

  Les questions suivantes ont un sens tant que les suites ( a n ) et ( b n ) sont définies.

Q3) Prouver que si a = b q + r est la divison euclidienne de a par b avec a b 1 , alors r < a 2 . (Distinguer les cas a 2 b et a < 2 b . )

Q4)  Prouver que n N , b n + 1 < b n - 1 2 .

Q5) En déduire que pour n N , b 2 n < b 0 2 n , où b 0 = b est la valeur de départ.

Q6) En déduire que n [ ln ( b ) ln ( 2 ) ] b 2 n = 0   puis que C ( a , b ) 2 [ ln ( b ) ln ( 2 ) ] .

Q7) Montrer que  si a < b alors   C ( a , b ) 2 [ ln ( b ) ln ( 2 ) ] + 1 .

Q8) En déduire que la complexité de l'algorithme d'Euclide est en O ( ln ( min ( a , b ) ) ) donc en O ( ln ( b ) ) . L'algorithme d'Euclide est un excellent algorithme.

  On peut démontrer qu'en fait C ( a , b ) 2 + [ ln ( b ) ln ( ϕ ) ] avec ϕ = 1 + 5 2 (ϕ est le nombre d'or). cette majoration est meilleure que celle obtenue ici.

© 2014 - Eric Obermeyer      Powered by      Corrigé