Ouvrir le menu principal

Algorithme d'Euclide

Algorithme d'arithmétique

En mathématiques, l'algorithme d'Euclide est un algorithme qui calcule le plus grand commun diviseur (PGCD) de deux entiers, c'est-à-dire le plus grand entier qui divise les deux entiers, en laissant un reste nul. L'algorithme ne connaît pas la factorisation de ces deux nombres.

HistoireModifier

 
Peinture censée représenter le mathématicien Euclide d'Alexandrie, par Justus of Ghent.

Selon Donald Knuth, l'algorithme d'Euclide est l'un des plus anciens algorithmes[1]. Il est décrit dans le livre VII (Proposition 1-3) des Éléments d'Euclide (vers 300 avant JC) sous la forme de l'anthyphérèse. Il est aussi décrit dans le livre X (Proposition 2), mais pour un problème de façon géométrique : comment trouver une « unité de mesure » commune pour deux longueurs de segments. Il procède par soustractions répétées de la longueur du plus court segment sur la longueur du plus long. Cela correspond à une adaptation de la méthode naïve de calcul de la division euclidienne, telle que décrite dans l'article consacré. Pour ce problème géométrique, l'algorithme d'Euclide ne termine pas forcément (dans un langage plus moderne, cela correspond à exécuter l'algorithme d'Euclide pour des nombres réels).

Probalement, l'algorithme n'as pas été découvert par Euclide, qui aurait compilé des résultats d'autres mathématiciens dans ses Elements[2],[3]. Pour le mathématicien et historienn B. L. van der Waerden, le livre VII vient d'un livre de théorie des nombres écrit par un mathématicien de l'école de Pythagore[4] L'algorithme était probablement connu de Eudoxe de Cnide (vers 375 avant JC)[5],[6]. Il se peut même que l'algorithme aurait existé avant Eudoxe[7],[8], vu les termes techniques ἀνθυφαίρεσις (anthyphairesis, soustraction réciproque) dans les travaux d'Euclide et aussi d'Aristote[9].

Quelques siècles plus tard, l'algorithme d'Euclide est inventé de manière indépendante à la fois en Inde et en Chine (voir p. 31 dans [10]). L'objectif était de résoudre des équations diophantiennes issus de l'astronomie et de faire des calendriers plus précis. Au 5e siècle, le mathématicien et astronome indien Aryabhata a décrit cette algorithme comme le "pulvérisateur" (voir p. 70 de [11]), à cause de son efficacité pour résoudre les équations diophantiennes (voir p. 86-87 dans [12]).


PrésentationModifier

PrincipeModifier

Le PGCD de deux entiers relatifs étant égal au PGCD de leurs valeurs absolues : de ce fait, on se restreint dans cette section aux entiers positifs. L'algorithme part du constat suivant : le PGCD de deux nombres n'est pas changé si on remplace le plus grand d'entre eux par leur différence. Autrement dit, pgcd(a, b) = pgcd(b, a - b). Par exemple, le PGCD de 252 et 105 vaut 21, mais c'est aussi le PGCD de 252 - 105 = 147 et 105. Ainsi, comme le remplacement de ces nombres diminue strictement le plus grand d'entre eux, on peut continuer le processus, jusqu'à obtenir deux nombres égaux.

Dans l'algorithme, on pourrait réaliser autant de différences que l'on souhaite. Par exemple, le PGCD de 252 et 105 est aussi égal au PGCD de 105 et 252 - 2 × 105 = 42. Ainsi, l'algorithme d'Euclide opère ainsi : on remplace le plus grand des deux nombres par le reste de la division euclidienne du plus grand nombre par le plus petit. Par exemple, la division euclidienne de 252 par 105 donne un reste de 42. Dans Introduction à l'algorithmique de Cormen et al. (voir Th. 31.9[13]), les auteurs appellent théorème de la récursivité pour le PGCD le fait suivant :

pgcd(a, b) = pgcd(b, r) où r est le reste de la division euclidienne de a par b.

Ainsi, l'algorithme d'Euclide sur deux nombres entiers positifs a et b avec a > b procède comme suit. L'algorithme regarde si b = 0 ou non.

  • Si b = 0, le PGCD est la valeur a.
  • Sinon, l'algorithme calcule le reste r de la division euclidienne de a par b, puis l'algorithme recommence mais avec a := b et b := r.

Le PGCD est la dernière valeur de a pour laquelle b = 0. En d'autres termes, l'algorithme réalise les divisions euclidiennes suivantes :

 

ExempleModifier

Le tableau suivant montre le calcul du PGCD de 21 et 15. On réalise la division euclidienne de a = 21 et b = 15. Le quotient est 1 et le reste 6. Puis l'algorithme continue a = b et b = le précédent reste. On réalise la division euclidienne de a = 15 et b = 6. Le quotient est 2 et le reste 3. Puis l'algorithme continue a = b et b = le précédent reste. On réalise la division euclidienne de a = 6 et b = 3. Le quotient est 2 et le reste est 0. Puis l'algorithme continue a = b et b = le précédent reste. Comme b est nul, l'algorithme s'arrête et le PGCD est a (c'est aussi le dernier reste non nul, à savoir 3).

Étape Dividende Diviseur Équation Quotient Reste de la division
1 21 15 21 = 15 × 1 + 6 1 6
2 15 6 15 = 6 × 2 + 3 2 3
3 6 3 6 = 3 × 2 + 0 2 0
4 3 0 fin de l'algorithme


Explications géométriquesModifier

Dans la tradition grecque, en comprenant un nombre entier comme une longueur et un couple d'entiers comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L'algorithme décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul.

Considérons par exemple le rectangle de dimensions L = 21 par l = 15 représenté ci-dessous. On peut glisser un carré de côté 15 mais il reste un rectangle de côtés 15 et 6. On peut y glisser deux carrés de côté 6 mais il reste un rectangle de côtés 6 et 3 que l'on peut carreler entièrement de carrés de côté 3. Les carrés de côté 6 ou 15 peuvent aussi se carreler en carrés de côté 3. Le rectangle entier peut se carreler en carrés de côté 3. Il n'existe pas de carré plus grand permettant un tel carrelage.

 
Explication géométrique de l'algorithme d'Euclide sur les entiers 21 et 15.

ImplémentationModifier

Version itérativeModifier

 
Algorithme d'Euclide sous la forme d'un organigramme. On pose la question "est-ce que b = 0 ?". Si oui, le pgcd est égal à a. Sinon, on part dans la boucle "Non". On revient à la question avec les nouvelles valeurs de a et b.

Donald Knuth, dans The Art of Computer Programming écrit une version itérative de l'algorithme d'Euclide[1] :

fonction euclide(a, b)
    tant que b ≠ 0
       t := b; 
       b := a modulo b; 
       a := t; 
    retourner a

où on note a modulo b le reste de la division euclidienne de a et b.

La version originale de l'algorithme d'Euclide, où on effectue que des différences successives est[1] :

fonction euclide(a, b)
    tant que a ≠ b 
        si a > b alors
           a := a − b
        sinon
           b := b − a
    retourner a

Version récursiveModifier

Cormen et al., dans Introduction à l'algorithmique en donne une version récursive[13] ; Dasgupta et al.[14] en donne la même version :

fonction euclide(a, b)
    si b = 0 alors retourner a
    sinon euclide(b, a modulo b)

L'appel à euclide(a, b) s'arrête et retourne la valeur a si b = 0. Sinon, l'appel continue avec les nombres b et a modulo b. L'exécution du calcul de PGCD de 21 et 15 donne : euclide(21, 15) = euclide(15, 6) = euclide(6, 3) = euclide(3, 0) = 3.

Correction et terminaisonModifier

Article détaillé : Propriétés du PGCD.

On sait que PGCD(a, 0) = a et que PGCD(a, b) = PGCD(b, a mod b). On progresse dans l'algorithme en diminuant à chaque étape les nombres considérés par calcul du modulo. L'algorithme termine bien : pour une valeur non nulle de b, le calcul de PGCD(a, b) fait appel au calcul de PGCD(a’, b’), où 0 ≤ b’ < |b|, car b’ est le reste d'une division euclidienne par b.


ComplexitéModifier

 
Nombre d'étapes de l'algorithme d'Euclide en fonction des nombres entiers a et b (respectivement en abscisse et en ordonnées). Plus, c'est foncé, plus il y a des étapes. Les points (a, b) avec a > b les plus foncés sont concentré autour de la droite a = bφ, où φ est le nombre d'or.

Dans cette section, nous étudions la complexité temporelle de l'algorithme d'Euclide, c'est-à-dire le nombre d'étapes de calcul en fonction des entiers a et b. La première analyse de complexité connue est due à A. L. Reynaud en 1811 : il écrit que le nombre d'étapes de l'algorithme d'Euclide sur a et b est borné par b[15]. En 1841, P.-J.-E. Finck démontre que le nombre d'étapes est borné par 2 log2 b + 1[16]. Cela démontre que l'algorithme d'Euclide s'exécute en temps polynomiale en la taille de l'entrée (nombre de chiffres pour écrire les nombres a et b)[17]. En 1844, Gabriel Lamé raffine les résultats de Finck : il démontre que l'algorithme effectue au plus 5 fois le nombre de chiffres en base 10 du plus petit nombre[18].

Première analyseModifier

Nous donnons d'abord une analyse qui part du constat suivant[14] :

  • Si a ≥ b, alors a mod b < a / 2

Ainsi, si a et b sont codés sur n bits, au bout de deux appels récursifs, leurs tailles contient un bit de moins. Il y a donc O(n) appels récursifs. Comme la division euclidienne s'exécute en O(n2) opérations, l'algorithme d'Euclide est en O(n3)[14].

Analyse via le théorème de LaméModifier

Nous en donnons ici une analyse plus moderne et plus précise donné dans le livre Introduction à l'algorithmique de Cormen et al. L'analyse de complexité de l'algorithme d'Euclide utilise la suite de Fibonacci : F0 = 0, F1 = 1, Fk+2 = Fk+1 + Fk. pour tout k ≥ 0. Voici les premiers termes de la suite de Fibonacci :

                                  ...
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 ...

Le théorème de Lamé (voir Th. 31.11 dans [13]) s'énonce comme suit :

Théorème de Lamé — Pour tout entier k ≥ 1, si a > b ≥ 1, et b < Fk+1, alors l'algorithme d'Euclide sur a et b réalise moins de k appels récursifs.

De plus, cette majoration est la meilleure possible, puisqu'elle est atteinte quand   et   sont deux nombres de Fibonacci consécutifs. En effet, les appels récursifs sur a = Fk+2 et b = Fk+1 sont :

euclide( Fk+2 , Fk+1 ) = euclide( Fk+1 , Fk ) = ... euclide(F2, F1) = euclide(F1, F0)

Via la formule de Binet, Fk est équivalent à    est le nombre d'or. Ainsi, on en déduit que le nombre d'appels récursifs est  . Plus précisément, il y a au plus   appels récursifs, où  désigne le logarithme en base  . On peut même montrer qu'il y a  appels récursifs (cf. exercice 31.2.5 dans [13]).

Complexité quadratiqueModifier

Soit n le nombre de bits dans les nombres d'entrées. Comme l'algorithme effectue une division euclidienne à chaque appel récursif, qui coûte O(n2), et qu'il ya O(n) appels récursifs, l'algorithme est en O(n3)[14]. Toutefois, une analyse fine montre que l'algorithme s'exécute en temps quadratique en le nombre de bits des nombres d'entrées (voir Problème 31.2 laissé en exercice dans [13], p. 902).

GénéralisationModifier

Anneau euclidienModifier

Cet algorithme repose sur la structure d’anneau euclidien de l’anneau Z des entiers relatifs, plus particulièrement sur la propriété de division euclidienne. Il se généralise donc à d’autres anneaux, en particulier les anneaux de polynômes à coefficients dans un corps. L’algorithme se généralise pour permettre le calcul des coefficients de Bézout.

L’algorithme est effectif à condition de disposer d’un algorithme effectif de division euclidienne. La possibilité de disposer d’un tel algorithme rend de nombreux autres calculs effectifs, notamment, en algèbre linéaire, le calcul de facteurs invariants.


Algorithme étendu aux coefficients de BézoutModifier

Article détaillé : Algorithme d'Euclide étendu.

Le théorème de Bachet-Bézout assure l'existence de deux entiers u et v tels que :  . L'algorithme d'Euclide étendu calcule de tels coefficients.

Pour cela, on introduit deux suites   et   telles que pour tout n, on ait la relation :   est la valeur de   à la nème étape de l'algorithme. Les termes   constitueront une paire de coefficients de Bézout pour a et b, où N est le numéro de la dernière étape de l'algorithme.

On choisit   et   (afin que   soit vrai pour n = 0 et pour n = 1), puis la relation de récurrence de pas 2 entre les   montre :

 

On peut ainsi définir   par la relation de récurrence de pas 2 :   et l'initialisation précédente, et   par   et l'initialisation précédente ; et on obtient bien la relation annoncée pour tout n.

L'algorithme étendu s'implémente comme l'algorithme classique ; il suffit de rajouter des variables correspondant aux coefficients u et v à calculer, et de faire une multiplication et une soustraction supplémentaires, pour calculer chacun des deux nouveaux coefficients, à chaque étape.

Fractions continuesModifier

Article détaillé : fraction continue.

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 = 1 071 et b = 1 029 utilisé ci-dessus.

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

1 071 = 1 029 × 1 + 42
1 029 = 42 × 24 + 21
42 = 21 × 2 + 0

De cela on tire :

 .

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

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

  •   ;
  •   ;
  •  .

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 termine pas et la suite des approximations obtenues est infinie[réf. nécessaire].

Nota : La décomposition en fraction continue (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 polynomiale du développement de Taylor : l'égalité des dérivées de la fonction et de son approximation, jusqu'à un certain ordre donné[réf. nécessaire].

La comparaison de ces deux types de développements permet de très intéressants développements, comme la démonstration de l'irrationalité de ζ(3)[réf. nécessaire]

Notes et référencesModifier

  1. a b et c (en) Donald E. Knuth, The Art of Computer Programming, Volume 2 (3rd Ed.) : Seminumerical Algorithms, Addison-Wesley Longman Publishing Co., Inc., , 762 p. (ISBN 978-0-201-89684-8, DOI 10.1145/270146, lire en ligne)
  2. A. Weil, Number Theory : An approach through history, Boston, Birkhäuser, , 4–6 p. (ISBN 978-0-8176-3141-3, notice BnF no FRBNF36146878)
  3. (en) A. Jones, Companion encyclopedia of the history and philosophy of the mathematical sciences, New York, Routledge, , 46–48 p. (ISBN 978-0-415-09238-8), « Greek mathematics to AD 300 »
  4. B. L. van der Waerden, Science Awakening, Groningen, P. Noordhoff Ltd, coll. « translated by Arnold Dresden », , 114–115 p.
  5. Knuth 1997, p. 318
  6. K. von Fritz, « The Discovery of Incommensurability by Hippasus of Metapontum », Annals of Mathematics, vol. 46, no 2,‎ , p. 242–264 (DOI 10.2307/1969021, JSTOR 1969021)
  7. T. L. Heath, Mathematics in Aristotle, Oxford Press, , 80–83 p.
  8. (en) D. H. Fowler, The Mathematics of Plato's Academy : A New Reconstruction, Oxford, Oxford University Press, , 31–66 p. (ISBN 978-0-19-853912-4, notice BnF no FRBNF34952462)
  9. O. Becker, « Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid », Quellen und Studien zur Geschichte der Mathematik B, vol. 2,‎ , p. 311–333
  10. (en) Stillwell, J., Numbers and Geometry., 1997 p.
  11. (en) Tattersall, J. J., Elementary Number Theory in Nine Chapters.,
  12. (en) Rosen, K. H., Elementary Number Theory and its Applications (4th ed.),
  13. a b c d e et f Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, et Clifford Stein, Introduction à l'algorithmique, 1176 p., Section 31.2
  14. a b c et d (en) Sanjoy Dasgupta, Christos Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill,
  15. A.-A.-L. Reynaud, Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique, Paris, Courcier, , Note 60, p. 34 As cited by Modèle:Harvtxt.
  16. P.-J.-E. Finck, Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales, Derivaux,
  17. J. Shallit, « Origins of the analysis of the Euclidean algorithm », Historia Math., vol. 21,‎ , p. 401–419 (DOI 10.1006/hmat.1994.1031)
  18. G. Lamé, « Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers », Comptes Rendus Acad. Sci., vol. 19,‎ , p. 867–870

Voir aussiModifier