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)

Tout à fait d’accord avec Pierre. Incidemment, en français (mais qui écrit en français de nos jours ?) terminer est un verbe transitif : on termine une activité. Les algorithmes SE terminent ou s’arrêtent. Ils ne « terminent » pas. JC.Raoult (discuter) 28 juillet 2024 à 10:53 (CEST)

Toit à fait d'accord pour que vous rajoutiez des "se". Robert FERREOL (discuter) 28 juillet 2024 à 18:56 (CEST)

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)

Ajouts de Arthur Baelde

@Arthur Baelde : vous n'avez tenu aucun compte des remarques qui on mené à un revert par deux utilisateurs différents (mauvais centrage du RI, exemple obscur, trop de détails pour un RI etc..). Vos contributions ne semblant pas appréciées (voir Projet:Mathématiques/Le_Thé#Algorithme_d'Euclide et ne dialoguant en aucune manière avec nous, ni en page de discussion, ni en commentaire de diff, il vous faut d'abord trouver un consensus ici avant de passer en force. Jean-Christophe BENOIST (discuter) 10 mai 2024 à 16:26 (CEST)

Je suis d'accord avec le message précédent. L'introduction pour un concept simple doit être simple. Un exemple complet d'algorithme n'a pas sa place dans l'introduction, mais dans le corps du texte (où il y en a). Merci de dire ici ce qui ne vous va pas dans l'introduction actuelle et ce qui vous semble manquer dans l'article, pour pouvoir discuter de la bonne place de leur insertion éventuelle.-- Cgolds (discuter) 10 mai 2024 à 18:32 (CEST)

Organigrammes

Protocole  particulier…

L’objet   de   la   discussion   n’est  pas  au  début  de  cette  rubrique.    C’est  exprès.
Proposée  en  introduction  de  l’article,   l’image  multiple  est  délibérément  présentée  en
fin  de  rubrique.   Elle  y  sera  éventuellement  reportée  par  mes  soins,   au  fur  et  à  mesure,
après   le   texte   du   dernier   intervenant.    Ainsi,   un  même  écran  affichera  à  la  fois
l’illustration  proposée  et  les  dernières  lignes  à  son  sujet,   au  cours  d’une
discussion  clarifiée.

Titre de l’article :  “Algorithme d’Euclide”.  Pour peu qu’on sache ce qu’est un algorithme,  on s’attend
à un organigramme figurant un algorithme.  Pourtant,  l’article actuel présente son seul organigramme
dans une sous‑section lointaine,  en première section de la rubrique “Implémentation”.  Et ce titre
rebutera  nombre  de  lecteurs.   Alors,  sans le moindre petit bout de dialecte de programmeur,
exhibons  plutôt  des  algorithmes  pour  introduire  le  sujet.   En  voici  trois  de  notre  temps,
sans  pseudo‑code.   Présentés  à  partir  du  plus  simple  algorithme,   juste  avant  la  première
section  de  l’article,   ils  informeront  les  lecteurs  sur  ce  qu’est  un  algorithme,
et  à  quoi  sert  un  algorithme  d’Euclide.

Par soustractions successives le premier algorithme calcule le reste d’une division euclidienne,
plus précisément   n  modulo  d   pour deux entiers naturels   n  et   d.    L’opération  modulo
sera  ainsi  définie.   Et  notre  entier   d   n’est  pas  nul,   bien  sûr.

En  utilisant  le  mot  “modulo”,   associé  à  “congru”  dans  certains  dictionnaires,
le  deuxième  algorithme  met  à  la  page  celui  d’Euclide.

Enfin  sans  modulo,   le  dernier  algorithme  transforme  s’il  le  faut  la  paire  d’entiers
initiale  en  une  autre,   et  au  besoin  en  une  autre  paire  encore,   dont  l’ensemble
de  communs  diviseurs  est  toujours  le  même.    Poursuivant   l’idée   pas   à   pas,
l’algorithme  remplace  le  plus  grand  élément  de  toute  paire  d’entiers  rencontrée,
par  la  différence  positive  entre ses deux éléments.  Ces soustractions successives
sont   le   support   d’une   preuve  mathématique   de   l’existence   du   “PGCD”,
multiple  de  lui‑même  et  de  tout  autre  commun  diviseur.   L’idée  poursuivie
se fonde sur une assertion assez simple :   une  différence  ou  une  somme
de  deux  multiples  d’un  entier  k   est  encore  un  multiple  de  k. 
Purement mathématique,  le troisième et dernier algorithme s’exécute jusqu’à
rencontrer zéro,  dans la paire initiale ou dans une paire calculée.  Car zéro est
multiple de lui‑même et de tout entier.  Osons capter votre attention,  zéro est
le “PPCM” de l’ensemble  ℕ  des entiers naturels,  ou son “plus grand” élément
pour  la  relation  d'ordre  au  cœur  du  sujet,   la  divisibilité.

Proposés   au   format   SVG,    les   trois   organigrammes   présentent   leurs   légendes
correctement  dans  les  deux  premières  tailles  de  police,   dites  petite  et  standard,
à  la  disposition  des  lecteurs  de  Wikipédia.   Arthur Baelde (discussion) 10 septembre 2024 à 15:37 (CEST)

Le problème c'est que les organigrammes sont largement passés de mode dans la présentation des algorithmes usuels, et pas depuis hier, donc non, on n'attend pas un organigramme en début d'article, et c'est même une mauvaise idée, à mon avis, mais surtout ça ne correspond pas à toute la littérature actuelle. Le Cormen et al Introduction to Algorithms (livre de référence depuis au moins 15 ou 20 ans, 1ère édition 1990, réédité, donné en biblio en licences ou prépa dès la première année) ne les utilise pas. L'usage est plutôt d'utiliser le langage courant, de façon un peu formelle et structurée, ou un pseudo-code pas trop strict (le danger du pseudo-code c'est d'être trop formel), parfois du code dans un langage de programmation de haut niveau style python (mais sans utiliser aucun raffinement, essentiellement comme du pseudo-code), ou de la réécriture équationnelle (très adaptée dans le cas de l'algo d'Euclide) ... Par exemple Demazure dans son Cours d'Algèbre (niveau ~ L3) varie suivant le sujet (code Ruby, réécriture équationnelle quand c'est plus adapté). Donc ce serait une très mauvaise idée d'entamer l'introduction de l'article ainsi.

Accessoirement vous voulez dire trop de choses dans vos schémas qui sont trop chargés, le crobard en png actuellement dans l'article (heureusement assez loin car il n'est pas fondamental), aussi moche soit-il, est pourtant largement plus lisible que votre deuxième organigramme auquel il correspond. Ensuite, hors la question de l'utilisation des organigrammes, présenter un algorithme de calcul du reste par soustraction n'a aucun intérêt : ça se fait tout seul dans la version de l'algo d'Euclide par soustraction. Le seul intérêt d'introduire explicitement la division dans l'algo d'Euclide, c'est qu'on a un algo plus efficace en théorie, en utilisant l'algo de l'école primaire, en base 2 ou en base 10 (mais pas toujours plus efficace en pratique, c'est un autre sujet qui pourrait être développé d'ailleurs, l'algo par soustraction n'est pas obsolète). L'algo du troisième schéma encore plus confus n'a donc pas d'intérêt non plus (organigramme ou pas). Sinon je suis d'accord que de parler des diviseurs communs, plutôt que seulement du plus grand, serait mieux. Proz (discuter) 10 septembre 2024 à 19:26 (CEST)

Bonjour  Proz.

Votre  texte  très  verbeux  s’achève  par  un  point  d’accord :
  Sinon je suis d'accord que de parler des diviseurs communs, plutôt que seulement du plus grand, serait mieux. 
Votre première affirmation est très contestable :   les organigrammes sont largement passés de mode…  Non,  je ne
cherche pas à être dans le vent,  mais autant que possible j’essaie d’intéresser des lecteurs très divers.  Et puis,  profond
désaccord entre nous quand vous m’écrivez ceci :   le crobard en png actuellement dans l'article (heureusement
assez loin car il n'est pas fondamental), aussi moche soit‑il, est pourtant largement plus lisible que votre
deuxième organigramme auquel il correspond.   Parce que le “crobard”,  sans la rigueur de mon
deuxième organigramme,  ne dit pas comment calculer le reste d’une division euclidienne,  en laissant tomber
dans l’oubli son quotient,  et sans utiliser l’opération modulo.  Car je prétends introduire l’article,  notamment cet extrait :
  le PGCD de deux nombres n'est pas changé si on remplace le plus grand d'entre eux par leur différence. 

L’expression  “plus  grand”  prend  là  son  sens  courant.
  Arthur Baelde (discussion) 11 septembre 2024 à 15:09 (CEST)

Algorithme d'Euclide pour deux entiers naturels non nuls

Pour l'algorithme par différence, celui présenté dans l'article est d'une simplicité biblique (il est conçu avec deux entrées non nulles - version anglaise oblige) et consiste à toujours remplacer le plus grand des nombres par la différence des deux nombres. Il ne nécessite pas de registre supplémentaire et donne un organigramme limpide. J'en ai dessiné un croquis. S'il doit exister un organigramme (ce qui n'est absolument pas nécessaire) je ne souhaite pas voir apparaitre le gros pavé bleu, rose, blanc, jaune, vert avec des écritures dans tous les sens et préfèrerais un croquis dans le style que j'ai dessiné. HB (discuter) 11 septembre 2024 à 19:41 (CEST)

Bonjour  Madame.

Nous  pourrions  appeler  sketch_B  le  schéma  “crobard”,   actuellement
inséré   sous   le   titre   “Version   itérative”,    qui  décrit  un  calcul
 d'une simplicité biblique ,   dites‑vous.   Quand  vous  écrivez
qu’il   consiste à toujours remplacer le plus grand des nombres
par la différence des deux nombres ,    vous   vous   trompez.
Cependant,   mes  deux  derniers  algorithmes  ne  refusent
pas  de  calculer  le  PGCD  de  {0,  0}.   Leurs  couleurs
ont  un  sens.   D’ailleurs,   nous  pourrons  remplacer
sketch_B  par  un  lien  vers  les  trois  organigrammes

du  chapeau  de  l’article.
  Arthur Baelde (discussion) 13 septembre 2024 à 15:50 (CEST)

Puisqu'il faut mettre les points sur les i.

• l'algorithme par différence (d'une simplicité biblique) n'est pas la version dite "itérative" mais la version "Algorithme d’Euclide original" comme le montre bien mon schéma Je ne me trompe (sic) donc pas.
• Je ne m'appelle pas "madame" mais HB
• Les relations exécrables que vous entretenez dans les discussions que vous initiez (mâtinées de guerre d'éditions comme sur Modulo (opération)‎ où vous en êtes à votre troisième revert fait que je préfère m'éloigner et cesser de discuter avec quelqu'un qui ne bouge pas d'un pouce ses positions. HB (discuter) 13 septembre 2024 à 17:31 (CEST)

Bonjour  Madame.

Je  vous  cite : celui présenté dans l'article est d'une simplicité biblique
(il est conçu avec deux entrées non nulles - version anglaise oblige)
et consiste à toujours remplacer le plus grand des nombres par la
différence des deux nombres.    Cet  algorithme  ne  calcule
pas  un  PGCD  en  calculant  des  différences  successives, 

mais  en  effectuant  des  divisions  successives,   non ?
  Arthur Baelde (discussion) 14 septembre 2024 à 12:21 (CEST)

a) Je ne m'appelle pas madame mais HB (deuxième demande)

b) Confondriez les mots algorithme et organigramme? (j'ai pourtant bien écrit "Concernant l'algorithme par différence, celui présenté etc et j'ai pourtant bien pris soin de présenter une autre illustration...)

Mais inutile de me répondre, j'ai décidé de laisser la main à d'autres contributeurs qui seront plus à même, j'espère, de vous faire comprendre l'importance de s'appuyer sur des sources tant pour les textes que pour les schémas surtout en cas de litige. Bon courage aux autres contributeurs. HB (discuter) 14 septembre 2024 à 15:23 (CEST)

Bonjour  Madame.

À  moi  aussi  parfois,    il  peut  arriver

que  je  me  trompe.  
  Arthur Baelde (discussion) 17 septembre 2024 à 14:29 (CEST)

Certes. Pouvez-vous être plus explicite : reconnaissez-vous enfin que votre troisième organigramme ne fait que simuler de façon inutilement compliquée l'algorithme d'Euclide par soustractions, comme je vous l'avais signalé dès ma première réponse et comme HB vous l'a soigneusement détaillé, et donc n'a pas lieu d'être ? Proz (discuter) 17 septembre 2024 à 16:54 (CEST)

De toutes façons, comme déjà dit également ci-dessus, les organigramme sont une manière dépassée de représenter un algorithme et peu lisible dès que on dépasse un certain niveau de complexité, que dépasse le troisième. L'article anglais (article de qualité) s'en passe très bien. Des pseudo-codes sont infiniment préférables. De plus, le choix de la présentation, des couleurs etc.. de ces organigrammes est très "personnel" et dépend trop des "goûts et des couleurs" pour Wikipédia. De plus encore, mais c'est mineur par rapport aux deux premier points, seul leur auteur peut facilement les modifier, ce n'est pas très "éditable" et donc pas tellement "Wikipédia". Contrairement aux pseudo-codes. Jean-Christophe BENOIST (discuter) 17 septembre 2024 à 17:05 (CEST)

Bien d'accord. Mais de plus le 3-ième schéma de Baelde serait tout aussi maladroit traduit en pseudo-code, et à exclure sous quelque forme que ce soit. Proz (discuter) 17 septembre 2024 à 23:54 (CEST)

Vous  ne  relevez  donc  aucune  erreur

dans  mes  organigrammes… 
  Arthur Baelde (discussion) 18 septembre 2024 à 14:32 (CEST)

Tout ce qui est non erroné (comme tout ce qui est sourcé) n'est pas forcément pertinent. Jean-Christophe BENOIST (discuter) 18 septembre 2024 à 15:03 (CEST)

n  et  d  sont  deux  entiers  naturels,    d   n’est
pas  nul.   Et  l’algorithme  calcule   n  modulo  d
en  itérant  la soustraction de  d.    Par  exemple,
quand  n  et  d  valent   28  et  8,   la  variable  r  prend  les  valeurs :   28 ↠ 20 ↠ 12 ↠ 4,
en  trois  parcours  de  la  boucle.   Le  reste
de  la  division  euclidienne   de   28  par  8
est  donc    28 – 3 × 8  =  28 modulo 8  =  4.

Par  les  divisions  successives
de  l’algorithme  d’Euclide,   calcul  du  PGCD
de  deux  entiers  naturels  d  et  g.    S’ils  valent
au  départ   8  et  28,    alors  au  fil  de  l’exécution,
les   dividende,   diviseur  et  reste  d’une  même  division  sont  trois  termes  successifs  de  cette  suite :   8,  28,  8,  4,  0   (8  est  multiple  de  4).
Résultat :     PGCD (8,  28)  =  4.

À chaque pas,  {28,  8},  {20,  8},  {12,  8},   et  ainsi  de  suite,   la  paire  conserve  le  même  ensemble  de  diviseurs  communs.   Ainsi  est  calculé  l’entier  multiple  de  lui‑même,   et  de  tout  autre  commun  diviseur  de   8  et  28,   dans  l’exemple.   En  effet,

toute  différence  ou  somme  de deux multiples  d’un  entier   k   est  encore  un  multiple  de   k.

Au  sujet  du  PGCD  de  deux  entiers  naturels,   trois  organigrammes.