Algorithme_d\'Euclide

Un article de Wikipedia.y-project.com.

L'algorithme d'Euclide est un algorithme pour déterminer le plus grand commun diviseur (P.G.C.D.) de deux nombres entiers. Il est décrit dans le livre VII des Éléments d'Euclide. L'algorithme n'exige pas de factorisation, qui est très fastidieuse quand on doit travailler sur de grands nombres entiers.

Étant donnés deux entiers naturels a et b, on commence par tester si b est nul. Si oui, alors le P.G.C.D. est égal à a. Sinon, on calcule c, le reste de la division de a par b. On remplace a par b, et b par c, et recommence le procédé. Le dernier reste non nul est le P.G.C.D. Calculons par exemple, le pgcd de 1071 et 1029 (égal à 21) par cet algorithme avec les étapes suivantes:

a	b	c
1071	1029	42
1029	42	21
42	21	0
21	0

L'algorithme peut être traduit dans le langage Python comme suit:

def pgcd(a,b):
   while b != 0:   
      c = a%b
      a, b = b, c
   return abs(a)

(La valeur absolue (abs) est utilisée dans la dernière ligne, pour assurer que le programme traite correctement des données négatives; rappelons que le pgcd est un entier naturel. Exemple : pgcd(-7,0) = 7.)

En mettant de côté les quotients obtenus à chaque étape de l'algorithme, on peut déterminer aussi des nombres entiers p et q tels que :

ap+bq = pgcd (a,b).

Voir l'algorithme d'Euclide étendu.

Ces algorithmes peuvent être utilisés dans n'importe quel contexte dans lequel toutes les divisions avec reste sont possibles. Ceci inclut les anneaux de polynômes à coefficients dans un corps, l'anneau des entiers de Gauss, et en général tout anneau euclidien.

Au début, Euclide a formulé le problème géométriquement : comment trouver une «unité de mesure» commune pour deux longueurs de segments. Il procéda par soustractions répétées de la longueur du plus court segment sur la longueur du plus long.

Ceci est illustré avec l'implémentation suivante dans le langage de programmation Python, qui travaille uniquement à partir de données strictement positives et est considérablement moins efficace que la méthode expliquée ci-dessus:

def pgcd(a,b):
   while a != b:
       if a > b:
           a = a - b
       else:
           b = b - a
   return a

[] La Preuve de l'exactitude de l'Algorithme d'Euclide

La preuve de cet algorithme n'est pas difficile. Supposons que a et b soient des nombres entiers non tous deux nuls.

Et supposons que le reste de la division euclidienne de a par b soit c.

Alors l'on peut écrire <math> a = q.b + c\,</math> où q est le quotient de la division d'où <math>c = a - q.b\,</math>.

Puisque l'on cherche <math>\varepsilon = pgcd(a,b)</math> alors l'on en déduit que <math>a\,</math> est un multiple d'<math>\varepsilon </math> et <math>b\,</math> est un multiple d'<math>\varepsilon </math>.

Puisque <math> c = a - q.b\,</math> alors <math>c\,</math> est la somme (au sens général) de deux multiples d'<math>\varepsilon</math> donc <math>c\,</math> est multiple d'<math>\varepsilon</math>.

On peut donc dire que pour trouver le plus grand commun diviseur de a et de b, il suffit de trouver le plus grand commun diviseur de b et de c.

Cela justifie que l'on puisse continuer le procédé avec les nombres b et c. Puisque c est le reste de la division entière de a par b alors c est toujours plus petit que b, nous atteindrons c = 0 après un nombre fini d'étapes.

[] Exécution

En étudiant l'exécution de l'algorithme d'Euclide, il apparaît que les nombres qui exigent le plus d'étapes sont les nombres consécutifs de la suite de Fibonacci, et dans le pire des cas cela demande O(n) divisions, où n est le nombre de bits des nombres en entrée (voir la notation grand O).

[] Fractions continues

Les quotients successifs qui apparaissent quand l'algorithme d'Euclide est appliqué aux données a et b, sont précisément les nombres qui apparaissent dans la représentation sous forme de fraction continue de a/b. Considérons l'exemple de a = 1071 et b = 1029 utilisé ci-dessus.

Voici le calcul avec les quotients soulignés (successivement 1, 24 et 2):

1071 = 1029 × 1 + 42

1029 = 42 × 24 + 21

42 = 21 × 2 + 0

De cela on tire :

<math>\frac = \mathbf + \frac + \frac}}</math>.

Dans l'égalité précédente, le second membre s'appelle la fraction continue ou continuée du quotient 1071/1029.

On peut en déduire les 3 approximations suivantes de la fraction, classées par ordre de précision croissante :

• <math>\frac = \mathbf = \frac</math>
• <math>\frac = \mathbf + \frac} = \frac</math>
• <math>\frac = \mathbf + \frac + \frac}} = \frac</math>

Cette méthode peut également être utilisée pour des nombres réels a et b  ;  comme dans le cas de deux entiers, la suite de quotients calculés représente la « décomposition en fraction continue » de a/b et fournit une suite d'approximations successives, de qualité croissante, du quotient a/b. Dans le cas où ce quotient est irrationnel, l'algorithme d'Euclide ne se termine pas et la suite des approximations obtenues est donc elle-même infinie !

nota : La décomposition en fraction continuée (et la série d'approximations successives correspondante) peut être appliquée, non seulement à un nombre réel quelconque, mais également à une fonction : cette démarche consiste à rechercher les approximants de Padé, dont on peut définir le principe comme suit : Au voisinage d'un point, le développement en série de Taylor d'une fonction donnée fournit un polynôme qui réalise une approximation de la fonction. Mais on peut également chercher une fraction rationnelle qui satisfasse les mêmes conditions que la partie polynômiale du développement de Taylor : l'égalité des dérivées de la fonction et de son approximation, jusqu'à un certain ordre donné.

La comparaison de ces deux types de développements permet de très intéressants développements (voir par exemple la démonstration de l'irrationalité de ?(3)).lt:Euklido algoritmas

 
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/Algorithme d\\\'Euclide