Discussion:Algorithme d'Euclide

Complexité

La complexité serait plutôt en O(log(n))... il serait intéressant de revoir ça. (surtout la preuve "il apparait que..." voir théorème de Lamé)

Refonte de l'article

J'essaie de donner un fil directeur à l'article, en lien notamment avec l'article division euclidienne. Travail en cours. J'essaie de garder au maximum les sections qui existaient précédemment.Salle 20 mai 2006 à 02:23 (CEST)

Erreur dans le code du programme C

Le code contient le test suivant :

while(a =! b)

En prenant l'exemple d'un cours en ligne (par exemple http://www-rocq.inria.fr/codes/Anne.Canteaut/COURS_C/chapitre1.html) je trouve que la bonne syntaxe est while(a != b)

• Je l'ai remarqué aussi. Code corrigé.

Mais tu aurais pu le corriger directement, c'est tout l'intérêt de wikipedia. ;) Zoidberg 14 février 2007 à 23:21 (CET)

Erreurs dans le code du programme C

C'est pire que ça. Je reprends point par point:

 #include <stdio.h>
 #include <stdlib.h>
 int main ()

Il faut écrire int main (void). L'ancienne forme (K&R) est toujours acceptée, mais dans le cas général, elle ne permet pas de faire de vérification de paramètres (probablement pas important pour main, mais autant ne pas prendre de mauvaises habitudes).

 {
  double a = 0, b = 0;

Pourquoi des double pour un calcul typiquement sur des entiers? Ce n'est pas faux tant qu'on s'assure que les entiers ne sont pas trop gros (pour que tous les calculs se fassent exactement), mais dans ce contexte, c'est bizarre.

    scanf("%i %i", &a, &b);

Au passage, c'est incompatible avec le double plus haut.

    while(a =! b)

Erreur déjà notée.

    {
      if (a > b)
       a = a - b;

C'est correct, mais on utilise généralement l'idiome du C: a -= b;

       else
       b = b - a;
    }
    printf("PGCD = %i", a);

Il manque un \n à la fin de la chaîne (c'est nécessaire sur certaines plateformes).

    system("PAUSE");

Pas standard. Ne fonctionne pas sur la plupart des systèmes.

    return 0;
 }

Je pense qu'il faudrait plutôt reprendre ce qui se trouve sur la page en anglais (qui donne d'ailleurs uniquement les algos, indépendamment du langage de programmation). Vincent Lefèvre 5 janvier 2007 à 14:22 (CET)

J'ai essayé le code C donné pour l'algo d'Euclide, mais il me donnait toujours 0 quel que soit a et b. J'ai donc remplacé ce code par un autre code qui marche, même si l'écriture n'a pas été simplifié pour l'instant.

Au posteur précédent: J'ai suivi tous tes conseils et rectifié le code. Par contre, je trouve qu'il vaut mieux le laisser. Je suis d'accord qu'il n'est pas indispensable et que l'algo général est plus important que l'algo codé dans un langage donné, mais c'est très pratique. J'étais bien content de le trouver ici, même si j'ai été obligé de le corriger. ^^ Zoidberg 14 février 2007 à 23:28 (CET)

Structure d'anneau euclidien pas assez mise en valeur

Tel qu'il est écrit actuellement, l'article me semble trop centré sur l'anneau des nombres entiers, alors que l'algorithme est applicable dans n'importe quel anneau euclidien. C'est à peine évoqué en une ligne ! Cela mériterait un paragraphe complet, avec peut-être un exemple dans le cas de polynômes… Bon, je n'ai pas le temps de le faire ce soir mais si cela tente quelqu'un, qu'il n'hésite pas. --DSCH (m'écrire) 14 février 2007 à 23:37 (CET)

Fusion Algorithme d'Euclide et Algorithme d'Euclide (mathématiques élémentaires)

Ces deux articles traitent du même sujet. La nécessité d'avoir une présentation élémentaire ne se fait pas réellement sentir. Mais une fusion serait à réaliser : il y a dans le deuxième article un organigramme intéressant à récupérer. Kelemvor 29 septembre 2007 à 18:35 (CEST)

Jerome66|me parler 5 octobre 2007 à 12:20 (CEST)

Implémentation C et PHP

Cet article n'est pas un article de programmation. Je pense qu'il est inutile de multiplier les exemples dans différents langages. On peut s'en tenir à donner les pseudos code des algos récursifs et itératifs. Si vous êtes d'accord, j'aimerais supprimer les exemples donc. J'attend votre avis. --Max81 (d) 10 mai 2008 à 11:09 (CEST)

Je suis d'accord. Salle (d) 10 mai 2008 à 11:32 (CEST)

Je suis aussi tout à fait d'accord (comme je l'avais mentionné plus haut, cf la page en anglais). Vincent Lefèvre (d) 15 mai 2008 à 00:40 (CEST)

idem, je supprime Levochik (d) 5 décembre 2008 à 17:20 (CET)

Deux ans plus tard deux implémentations ont été remises, je serais d'avis de les supprimer mais demande l'avis de ceux qui suivent l'article (en deux ans la politique de rédaction peut avoir changé). HB (d) 9 novembre 2010 à 16:38 (CET)

Même avis. Anne Bauval (d) 12 février 2011 à 20:57 (CET)

Est-ce l'algorithme d'Euclide ?

Ne lisant pas le grec ancien, je n'ai pas lu les livres d'Euclide. En revanche, je me refère au livre de Knuth The Art of Computer Programming vol. 2 qui décrit l'algorithme d'Euclide en collant au plus près du texte et l'algorithme qu'il décrit est fondé sur des soustractions successives. Il est proche de la version anglaise de l'article de Wikipédia section Historical developments. Cela est suggéré dans la section remarque historique mais de façon ambigüe, qui ne rétablit pas vraiment la vérité. Je pense donc la présentation de l'article n'attribue pas à Euclide ce qui lui est dû. --Pierre de Lyon (d) 11 octobre 2010 à 17:41 (CEST)

Oui il s'agit bien de ce qu'on appelle l'algorithme d'Euclide dans la littérature technique en français. L'algorithme alternatif que vous décrivez et que j'ai du mal à trouver dans la version anglaise actuelle est appelé : Algorithme soustractif. S.dubourg (d) 15 janvier 2012 à 19:47 (CET)

Je suis désolé, je ne comprends pas votre réponse et je ne comprends pas à quoi vous répondez oui. L'algorithme d'Euclide est il bien l'algorithme à base de soustractions. --Pierre de Lyon (d) 18 janvier 2012 à 14:03 (CET)

Ce que je peux dire c'est que l'algorithme d'Euclide présenté au lycée utilise la division euclidienne, que l'on appelle souvent lemme d'Euclide la propriété : PGCD(a,b)=PBCD(b, a-kb), que l'on appelle division euclidienne une division avec reste qu'Euclide n'a jamais définie explicitement. Ce qu'ecrit Euclide est traduit par Henrion par « soit soustrait le plus petit nombre CD tant de fois que faire se pourra du plus grand AB, s'il reste quelque chose comme EB, iceluy soit oté de CD tellement qu'il reste encore FD (...) » - livre 7, problème 1 proposition 2 [1]. Le soulignement est de moi. Alors, simple soustraction ? recherche du reste ? Ceci n'est pas clair. La tradition attribue l'algorithme par recherche de reste à Euclide, le texte permet aussi cette interprétation, mais j'ignore si les historiens se sont penchés sur cette subtile différence. HB (d) 1 février 2012 à 11:26 (CET)

Je reprends une vieille discussion. La question de savoir si Euclide présente l’algorithme par soustractions successives ou par calculs de restes successifs. Voici ce qu'écrit Knuth dans The Art of Computer Programming vol. 2 (p. 319) (je traduis).

« Dans sa discussion, Euclide suggère tout d'abord de soustraire le plus petit des deux nombres courants du plus grand, et ce répétitivement jusqu'à ce qu'on obtienne deux nombres dont l'un est le multiple de l'autre. Mais dans la démonstration, il s'appuie, en fait, sur le reste de la division d'un nombre par l'autre. [...] Il est raisonnable de penser qu'il imagine chaque division (non pas la soustraction individuelle) comme une étape de base de l'algorithme et donc une présentation ``authentique`` de l'algorithme peut être faite comme suit ... Vient une présentation par calculs successifs de restes.  »

Donc une présentation par calculs successifs de restes est correcte. En revanche, faire en 2024, ce qu'à fait Euclide il y a 2 300 ans, à savoir présenter l'algorithme par soustractions successives, puis les exemples par calculs de restes ne me parait pas particulièrement didactique. Je vais le modifier--Pierre Lescanne (discuter) 27 janvier 2024 à 10:58 (CET)

Commentaire du lecteur : L'algorithme étendu...

81.66.85.211 a publié ce commentaire le 29 septembre 2013 (voir tous les retours).

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.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 convenablement adapté permet de calculer de tels coefficients.

Avez-vous des remarques à formuler ?

Litlok (m'écrire) 23 février 2014 à 00:09 (CET)

Ce commentaire n'est qu'un copié collé de passages de l'article. Anne (discuter) 23 février 2014 à 00:46 (CET)

Je n'avais pas remarqué, désolé pour le dérangement ! Il m'avait semblé assez bien tourné et précis pour ne pas être poubellisé d'office... Litlok (m'écrire) 23 février 2014 à 22:31 (CET)

Le cas où a ou b est nul ne nécessite aucun algorithme ; on l'exclut.

Bonjour. C'est une véritable aberration mathématique : "Le cas où a ou b est nul ne nécessite aucun algorithme ; on l'exclut". Et pourquoi pas pour a ou b valant 1 (ne demandant pas non plus de calcul) ? Non, en réalité, c'est que l'algorithme présenté est mal fait. Je suis désolé de dire cela, mais c'est vrai. Le bon algorithme commence par (*) tester si b est nul (auquel cas c'est terminé car le pgcd vaut a, en valeur absolue si on travaille avec des entiers relatifs). Puis on calcule le reste r de la division euclidienne de a par b (division possible car b est maintenant non nul). Ensuite le couple (a,b) prend la valeur de (b,r) et on revient au test initial (*). Conclusion : en mettant les instructions dans le bon ordre, on ne néglige artificiellement aucun nombre entier. De plus, dans le paragraphe "Démonstration de sa finitude et de son exactitude", on utilise très justement la propriété pgcd(a_n,0)=a_n car elle est fondamentale. On voit très bien dans cette preuve qu'il faut renvoyer au bon moment la valeur de a et non de b. Cordialement. Leon1789 (discuter) 9 mars 2019 à 11:48 (CET)

Je suis d'accord avec vous et je vais modifier cette phrase. Il semble que celui qui a écrit cela a une vision erronée de ce qu'est un algorithme. Je pense donc que la section Description de l'algorithme doit être modifiée. A titre de modèle on pourra s'appuyer sur ce qui est présenté dans Algorithme récursif. --Pierre de Lyon (discuter) 10 mars 2019 à 11:29 (CET)

Merci. J'ai refait l'organigramme de manière cohérente avec la description récursive, mais en données j'ai pris des entiers naturels (et non relatifs). Tant pis, ce n'est peut-être pas si grave :) . Leon1789 (discuter) 10 mars 2019 à 14:24 (CET)

Nous progressons, mais je ne pense pas qu'un organigramme soit la meilleure façon de traduire un algorithme récursif. --Pierre de Lyon (discuter) 10 mars 2019 à 17:35 (CET)

oui d'accord. Mais je pense qu'il faut mettre un "organigramme qui boucle" quelque part sur le page car l'algorithme est souvent implémenté sous forme itérative. Où le mettre alors ? Leon1789 (discuter) 10 mars 2019 à 18:46 (CET)

Place du pseudo code

La nouvelle mouture de l'article ne me parait pas satisfaisante:

• le pseudo-code est un outil d'informaticien alors que l'article doit pouvoir viser un public plus large, le pseudo-code n'a donc pas à être mis en premier dans l'article
• la refonte a fait disparaitre le principe mathématique de l'algorithme: Or un algorithme n'est pas une recette et doit s'appuyer sur un raisonnement

Cependant elle apporte un plus avec l'exemple plus explicite

Je propose donc un autre plan

1. Remarque historique ou histoire (un peu présomptueux)
2. Présentation
   1. principe (où on remettrait la propriété PGCD(a, b)=PGCD (a-b, b) et sa généralisation PGCD (a,b)=pgcd(b,r) où r= a-bq est le reste de la division euclidienne
   2. exemple sous forme d'un tableau
   3. illustration géométrique (dispensable)
3. Pseudo-code
   1. pseudo code simple
   2. pseudo code récursif
   3. correction et terminaison (où on rappelle le principe et la présence d'une suite strictement décroissante d'entier)
   4. Longueur de l'algorithme ou théorème de Lamé
4. Généralisation et approfondissement
   1. Généralisation à un anneau euclidien
   2. Algorithme étendu aux coefficient de Bézout.
   3. Fractions continues

Des avis ? HB (discuter) 28 septembre 2019 à 19:43 (CEST)

Merci à vous. J'ai adopté votre proposition de plan que je trouve plus cohérente et pédagogique. Fschwarzentruber (discuter) 28 septembre 2019 à 23:05 (CEST)

Ça me gêne un peu de trouver le pseudo-code sous une section nommée "Implémentation". Car par "implémentation", on entend généralement du code écrit spécifiquement dans un langage ou pour une machine: c'est le niveau du dessous de l'algorithme. Or ici le but du pseudo-code est de décrire l'algorithme dans sa généralité. Peut-être renommer la section?

D'autre part, les noms de section "Pseudo-code" / "Autre pseudo-code : version récursive" ne conviennent pas. Ça devrait plus symétrique, comme "version itérative" / "version récursive". Vincent Lefèvre (discuter) 28 septembre 2019 à 23:17 (CEST)

Oui. Complétement d'accord avec vous Vincent, merci pour votre commentaire. Je me suis aussi permis de rajouter une nouvelle illustration pour l'explication géométrique. Fschwarzentruber (discuter) 28 septembre 2019 à 23:33 (CEST)

Histoire

L'histoire de cette algorithme est vraiment bien décrite dans la page anglaise. Est-ce que vous êtes d'accord pour traduire ? Si quelqu'un de passionné veut le faire ;) J'ai commencé un peu mais voilà. Bonne soirée ! Fschwarzentruber (discuter) 1 octobre 2019 à 16:43 (CEST)