View source for Talk:Euclidean algorithm

{{User:MiszaBot/config
|archiveheader = {{aan}}
|maxarchivesize = 128K
|counter = 4
|minthreadsleft = 5
|minthreadstoarchive = 1
|algo = old(30d)
|archive = Talk:Euclidean algorithm/Archive %(counter)d
}}
{{ArticleHistory|action1=PR
|action1date=19:07, 24 April 2009
|action1link=Wikipedia:Peer review/Euclidean algorithm/archive1
|action1result=reviewed
|action1oldid=285904756

|action2=FAC
|action2date=21:05, 19 May 2009
|action2link=Wikipedia:Featured article candidates/Euclidean algorithm/archive1
|action2result=promoted
|action2oldid=290822297

|action3=FAR
|action3date=2015-02-07
|action3link=Wikipedia:Featured article review/Euclidean algorithm/archive1
|action3result=kept
|action3oldid=645941671

|currentstatus=FA
|maindate=June 18, 2009
}}
{{WikiProject banner shell|class=FA|vital=yes|1=
{{WikiProject Mathematics|importance=top}}
{{WikiProject Numbers|importance=}}
{{WikiProject Classical Greece and Rome|importance=mid}}
{{WikiProject Greece|importance=Mid}}
}}
{{Archive box|auto=yes}}

== Inconsistent history ==

The present text of the article says that the Euclidean algorithm was first described in Europe by Bachet in 1624.  This can hardly be true if it was already described in Euclid's Elements, which was known in Europe in various editions and translations long before Bachet.[[Special:Contributions/109.149.2.98|109.149.2.98]] ([[User talk:109.149.2.98|talk]]) 13:49, 7 April 2019 (UTC)
:Point well taken. The source only says that Bachet gave the first ''numerical'' description of the algorithm in Europe. I'll edit this. --[[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 19:02, 7 April 2019 (UTC)

== Section "Non commutative rings" ==

It seems that the only known example is the ring of [[Hurwitz quaternion]]s. This must be clarified. If is true, the section must be renamed "Hurwitz quaternions". Otherwise, it must be named "Non commutative Euclidean rings" and moved to [[Euclidean domain]]. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 08:47, 18 June 2019 (UTC)

== Inaccurate implementations ==

I feel the implementations given in the Implementations sections are all inaccurate.
For example, gcd(-6, 0) is 6, but the implementations return -6.
This is wrong because GCDs are always non-negative. [[User:Hexagonalpedia|Hexagonalpedia]] ([[User talk:Hexagonalpedia|talk]]) 12:18, 23 May 2021 (UTC)
:{{fixed}} [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 16:39, 24 May 2021 (UTC)

== Flowcharts ==

At least one flowchart that represents an '''Euclidean algorithm''' could be expected.  Now no flowchart in the [[Special:PermanentLink/1241456074|current article]].  So here are flowcharts.

As though there is no instruction '''modulo''' in computing,  neither in Python nor in JavaScript for example,  the first algorithm computes a [[remainder]] through successive subtractions.  The second algorithm uses successive modulo operations  — % in Python or in JavaScript —,  in order to yield the GCD of two natural numbers.  A little more complicated,  the third algorith is conceived for the easiest '''mathematical proof''' of the existence of this “great” divisor,  which is multiple of every common divisor of a given pair of natural numbers.  This last algorithm keeps unchanged the common divisors of such a pair at every step,  by replacing the greatest integer with the positive difference between the two.

{{multiple image
| total_width = 1059 | image_gap = 15 | align = left | footer_align = center
| footer      = <div style="font-size:135%">About  the  [[greatest  common  divisor]]  of  two  [[natural  number]]s,   three  [[flowchart]]s.</div>
| image1  = Iterated_subtraction of_d until_modulo_d.svg
| link1   = c:File:Iterated_subtraction of_d until_modulo_d.svg
| caption1  = By  [[Iterated function|iterating]]  the  subtraction  of  number   {{mvar|d}},<br/>calculation  {{nobr|of   {{mvar|n }} '''[[modulo]]'''  {{mvar|d }} }} for  {{nobr|{{mvar|n }} and  {{mvar|d}}}}<br/>[[Natural number|members  of  ℕ]],    when  {{mvar|d }} is  not  zero.   Example''':<br/>{{nobr|1=if   {{mvar|n}} = 85  and  {{mvar|d}} = 20,  }}''' then  variable   '''{{mvar|r  }}''' passes<br/>through  the  {{nobr|values''':     85 ↠ 65 ↠ 45 ↠ 25 ↠ 5'''}},<br/>along   four   courses   of   [[Control flow#Loops|the   loop]].    Therefore,<br/>according  to  the  [[algorithm]],   divide   85  by  20<br/>yields   the   [[remainder]]<br/>{{nobr|1=85 – 4 × 20  =  85 '''modulo''' 20  =  5.}}
| image2  = GCD_through successive_divisions.svg
| link2   = c:File:GCD_through successive_divisions.svg
| caption2  = Through  the  successive  divisions  of  the<br/>'''Euclidean  algorithm''',   calculation  of  the  [[Greatest common divisor|GCD]]<br/>of   natural   numbers    {{mvar|d }} and  {{mvar|g.  }} For  example,<br/>if  their  starting  values  {{nobr|are   '''20  and  85''',  }} then<br/>dividend,   divisor  and  remainder  of  the  unique<br/>division   of   the   loop   are,    at  every  step,<br/>three  successive  terms  of  this  {{nobr|[[sequence]]''':<br/>20,  85,  20,  5,  0'''   (5  being  a  [[divisor]]  of  20).}}<br/>Result''':    gcd(20, 85)  =  5'''.
| image3  = GCD_through successive_subtractions.svg
| link3   = c:File:GCD_through successive_subtractions.svg
| caption3  = <br/>Every  pair  of  such  a  sequence''':<br/>{85,  20},   {65,  20},   {45,  20}''',<br/>and  so  on,   has  [[Invariant (mathematics)|the  same]]  set  of<br/>common   divisors   at   every   step.<br/>So  the  “great”  divisor,   [[Multiple (mathematics)|multiple]]  of<br/>every  divisor  of   85  and  20   in  this<br/>example,   can  be  computed  simply<br/>through  successive  subtractions.
}}{{Clr}}
<div style="background:#def;padding:1em;width:1020px;text-align:center">If  either  given  integer  is  '''zero''',   then  their  greatest  common  divisor<br/>is  the  other  number,   because  '''zero ''' is  the  only  multiple<br/>of  every  integer,   the  “greatest”  for  the  [[Order theory#Partially ordered sets|divisibility]].</div>

These three algorithms could be inserted in introduction just after the text,  while [[c:File:Euclid's algorithm Book VII Proposition 2 3.svg|the antique diagram]],<br/>less comprehensible than a flowchart,  could be transfered in section<br/>[[Special:PermanentLink/1241456074#Background: greatest common divisor|“Background: greatest common divisor”]] on the right,<br/>[[c:File:24x60.svg|the   rectangle]]   being   placed   on   the   left.<br/>All  '''captions'''  of  this  multiple  image  are<br/>'''well  presented  in  the  first  two  available  font‑sizes'''.<br/> &nbsp; [[User:Arthur_Baelde|Arthur&nbsp;Baelde]]&nbsp;([[User_talk:Arthur_Baelde|talk]]) 14:28, 5 September 2024 (UTC)

:Flowcharts were a popular method for describing algorithms whent the main control instruction of programming languages was the "go to". Presently, flowcharts are generally replaced by [[pseudo-code]], which is more concise, easier to understand because of its linear structure, and more powerful (it describes programs that cannot be described with flowcharts). The article [[Flowchart]] contains {{tqq|The flowchart became a popular tool for describing [[Computer algorithm|computer algorithms]], but its popularity decreased in the 1970s, when interactive [[Computer terminal|computer terminals]] and [[Third-generation programming language|third-generation programming languages]] became common tools for [[computer programming]], since algorithms can be expressed more concisely as [[source code]] in such [[Programming language|languages]]. Often [[pseudo-code]] is used, which uses the common idioms of such languages without strictly adhering to the details of a particular one. Also, flowcharts are not well-suited for new programming techniques such as [[Recursion (computer science)|recursive programming]].}}
:Also, the manual of style of Wikipedia [[MOS:MATH#Algorithms]] says {{tqq|An article about an [[algorithm]] may include [[pseudocode]] or in some cases [[source code]] in some [[programming language]].}}, and does not mention flowcharts at all. Effectively, there are many Wikipedia articles that contain pseudocode, and very few that contain flowcharts.
:Presently, the section {{alink|Implementations}} contains the pseudo-code of three versions of the Euclidean algorithm. The most complicate one consists of 7 short lines, and the third one can definitively not be converted into a flow chart. Also, the second one is a much better implementation than your thirs flowcharts.
:So, there is no reason for introducing flowcharts in this article, and, in any case, their place is not in the lead. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 16:26, 5 September 2024 (UTC)
:I think it would be okay in principle to have a flowchart somewhere in this article, though an algorithm this simple can also be described as a paragraph or written as pseudocode.
:I find these particular flow charts pretty hard to read and visually distracting. The most important feature of flow charts is organizing information spatially so it can be easily visually scanned. –[[user:jacobolus|jacobolus]] [[user_talk:jacobolus|(t)]] 17:16, 5 September 2024 (UTC)

== Interactive worked examples ==

<div style="min-width:100px; max-width:35%;border: grey thin solid;padding-left:8px;padding-right:8px;float:right;">{{User:Bawolff/euclidean}}</div>
I've noticed that a lot of Wikipedia articles on algorithms have worked examples or sometimes GIF animations showing the algorithm step by step. I was thinking it would be cool if there could be an interactive worked example, where the reader can chose the inputs and then see the algorithm work step-by-step. I decided to have a go at trying to create something like that - see my demo on the right. I was wondering what people think of the idea? [[User:Bawolff|Bawolff]] ([[User talk:Bawolff|talk]]) 16:42, 14 November 2024 (UTC)

:I think this is fantastic. Unfortunately though, it doesn't show some of the numbers on dark mode, and doesn't work at all in the actual article for me. [[User:It is a wonderful world|IAWW]] ([[User talk:It is a wonderful world|talk]]) 21:08, 7 April 2025 (UTC)
::I think i fixed the dark mode issues. Can you describe what's happening for you in the article? Does it not show up at all? Does it show up but the buttons don't work? [[User:Bawolff|Bawolff]] ([[User talk:Bawolff|talk]]) 04:46, 9 April 2025 (UTC)
:::@[[User:Bawolff|Bawolff]] Ah yes you have fixed the dark mode issues. Thank you!
:::When I click the start button in the article it doesn't do anything. Interestingly, it works on Chrome (I just tested it). It only happens on Firefox when on the article itself, and there are no errors in the console. I wouldn't worry about it, maybe it is one of my extensions messing things up. [[User:It is a wonderful world|IAWW]] ([[User talk:It is a wonderful world|talk]]) 08:15, 9 April 2025 (UTC)
::::Hmm, i tried on firefox and it seems to work for me. Hopefully its just a conflict with some other user script but i'll try and keep an eye out for anyone reporting a similar issue. [[User:Bawolff|Bawolff]] ([[User talk:Bawolff|talk]]) 10:27, 9 April 2025 (UTC)
:::::Great, must be something about my browser or scripts. Thanks for the great work! [[User:It is a wonderful world|IAWW]] ([[User talk:It is a wonderful world|talk]]) 11:22, 9 April 2025 (UTC)