Talk:Euclidean algorithm

From Wikipedia, the free encyclopedia

You have new messages (last change).
To-do list for Euclidean algorithm: edit · history · watch · refresh
  • Expand the introduction to cover all major aspects. Done Lemontea
  • Regroup the scattered info on the history of this algorithm, and write a history section on it. Done Lemontea
  • Add detailed description and explanation to the example: it should be more than a table. Done Lemontea
  • But first we have to format the table better - it looks odd now. Done by Dantheox, thanks!
  • Expand the implementation codes - the program should handle varies special cases, such as b bigger than a, negative number, etc. (b>a isn't significant, since in that case, a mod b = a and on the next recursive call, a and b are swapped. Dantheox) (I think the algorithm handles negative numbers by default. Fetofs)
  • Reorganise (and maybe add a section, if there's enough information) the bits about this algorithm applied to objects other than integers, such as polynomial. Done Dantheox
  • Cleanup and maybe expand the history section if possible. (Currently it is just a copyedit)
  • And obviously, clean up and wikify the introduction.


This article is nice, but it would have been nicer, had the reader been not expected to know javascript or python. At least I do not know Javascript and Python, though I'm interested in what is happening in the implementation. It would be great if these things are replaced by a pseudo code, which will be more readable. Thanks.

-- Ramesh, India.

Contents

[edit] I Agree

I agree to Ramesh, PsudoCode is the better way to discribe an algorithm. In special: what means a, b = b, a % b I don't think it's a = b b = a modulo b that doesn't make any sense, after this b would be 0 (in any case it was before) b = a modulo b a = b is also a bit confusing, because in the next run b would become 0 whatever a and b are before. Greetings from Germany

Actually, the real Euclid's Algorithm didn't use division but subtraction - a lot easier with the arithmetic tools available to the classical Greeks, and just as easy to reason about. Division is just an early optimisation. PML.

[edit] Time Complexity

Could someone please tell me the time complexity of the original euclids algorithm. This is the one which uses subtraction only. Thanks.

[edit] Asymptotically or Worst-Case?

The article states that the binary GCD algorithm is asymptotically O(n2). Does this mean that the algorithm's performance degrades as the numbers become larger? It seems like this should be the "worst case" behavior and not the general asymptotic behavior. If not, another sentence about why the asymptotic complexity is so high would help.

You have some confusion over the meaning of asymptotic. Asymptotically simply means "as n becomes very large", and is in fact redundant here, because it's already implied by the big-O notation. The big-O notation also implies worst-case, because O(n2) means precisely that, for large enough n, it runs in time at most a constant times n2. See Big-O notation for more of the formal details; I hope this helps. Deco 01:59, 19 Nov 2004 (UTC)

I understand what asymptotic means. I also understand that the big-O already implies both "asymptotic" and "worst case". However, the intent of the sentence, I believe, is to say that the binary GCD algorithm is fast for most inputs, but there are still some pathological inputs (of all sizes) that trigger O(n2) behavior. This might be better explained by redundantly stressing "worst case" instead of "asymptotic". By stressing "asymptotic", it implies that the algorithm is fast up until a certain input size; after that, it slows down (which I don't think is the case; is it?).

Oh, sorry. Really the main difference is in the constant hidden by the big-O notation, rather than how they compare on small inputs. I attempted to clarify this and remove the asymptotically. Deco 6 July 2005 06:29 (UTC)

[edit] Optimization

In fact Euclid's origonal argorithm is faster. Modulo is implemented by iterated subtraction, so the loop overhead is cut by the origonal method. While it may not seem that way, examining the assembler produced by a C implementation will show Euclid to be correct.

No. Finding modulus by repeated subtraction requires exponential time in the size of the input, and so should never be used by any self-respecting compiler unless the answer is known to be small or the word size is very small. Most desktop machines have a single hardware operation for finding modulus, which makes it much more efficient in general. I can't imagine how you came up with this idea. Deco 6 July 2005 06:25 (UTC)

[edit] puzzling

Under the continued fraction section the article says "if a/b is irrational, then the Euclidean algorithm won't terminate". From the article a and b are "natural numbers" or positive integers. I always thought that if a number could be represented by integers a/b then it is rational. What is this statement trying to say? Is there a way to use the euclid algorithm on irrational numbers? In any case this ought to be fixed somehow. (unsigned by Horndude77)

Yes if a and b are integers then a/b is rational. But the article says: "This method can even be used for real inputs a and b; if a/b is irrational, then ..." So they are any real number, not necessarily integers. Thus a/b could be irrational. Paul August ☎ July 6, 2005 01:05 (UTC)

[edit] Computer code

Shouldn't this computer code be moved to a later part of the article or into a separate article? It should not be considered a prominent part of this topic. Michael Hardy 00:30, 1 October 2005 (UTC)

OK, I've moved it. Michael Hardy 00:33, 1 October 2005 (UTC)

[edit] Optimization

I'm removing this from the "C/C++ Code" section:

An optimization of this algorithm would be:

int gcd(int a, int b) {

 int t;
 while (a %= b)
 {
   t = a;
   a = b;
   b = t;
 }
 return b;

}

This variation does not aid in understanding the Euclidean Algorithm, and is essentially just a rearrangement of the previous code snippet. It's not even clear whether it's an optimization. The two existing code snippets should probably be rewritten in pseudocode, since it's not clear that "%" means "modulo" unless you've used C. --Dantheox 19:31, 23 January 2006 (UTC)

I believe this this optimization makes code slower.

[edit] Explanation of the example of algorithm

I've written a rough explanation of the example of the algorithm, though it can be improved. Besides, I'm not sure whether the explanation should be included in the table or should it be outside the table, having a paragraph of its own, just like other paragraphs of this article. But if we choose the later, I'm not sure how to have the paragraph put side-to-side with the table. Thanks.--Lemontea 02:00, 25 January 2006 (UTC)

All of these are possible. Post your paragraph here and we can help to incorporate it in the best way. Deco 02:01, 25 January 2006 (UTC)
I've tried my best in polishing the description of the algorithm section. Currently the explanation of the example is written on the last column in the table. I hope somebody can now cleanup and finish that part, if anything needs to be done at all. Thanks. --Lemontea 09:18, 26 January 2006 (UTC)

[edit] Technical difficulties

The last edit is me trying to change the double equal sign into a single equal sign in the first pseudocode, however it seems the server cannot complete my edit and screwed the article up. If this comment ever get submitted successfully, could someone please do that minor edit for me. Thanks. --Lemontea 11:16, 28 January 2006 (UTC)

Did you mean the one under Concept block?
I did the edit anyway. I mean "b = 0" instead of the original. Check the history if you want to know exactly where it is. --Lemontea 13:36, 31 January 2006 (UTC)

[edit] Loop unrolling version

Should the following version (using loop unrolling) be mentioned?

int gcd(int a, int b) {

 while(true)
 {
   a = a%b;
   if(a==0)
   {
     return b;
   }
   b = b%a;
   if(b==0)
   {
     return a;
   }
 }

}

For normal C/C++ integers this does not make much difference; in the case of big integers (several hundreds of digits), however, it avoids the cost of unnecessary copies of the integers. --NeoUrfahraner 07:07, 12 April 2006 (UTC)

While personally I think this version, using some optimazation tricks, does save the temporary variable in a clever way, I don't think it is a good idea to optimize this far - this is an article for explaning an algorithm, not a demostration of programming tricks, and thus readibility and ease of comprehension should always come first before efficiency of the code. Nonetheless, it is ultimately, up to the reader(especially those that don't know about this algorithm before and check this for info) to decide which version is better. --Lemontea 07:55, 12 April 2006 (UTC)
Might be a good snippet for wikisource. Is there a collection of implementations of the Euclidean algorithm there? --Dantheox 22:25, 12 April 2006 (UTC)
A search on wikisource returned no results, so yes, go ahead and add it :) --Lemontea 02:24, 13 April 2006 (UTC)
Done, see http://en.wikisource.org/wiki/Euclidean_algorithm. I also added the two basic versions mentioned in the wikipedia article. This is my first contribution to wikisource, so please feel free to adapt it to the conventions used there. In particular, I do not know how to set the interwiki links. --NeoUrfahraner 05:23, 13 April 2006 (UTC)
Apparently Wikisource no longer considers source code to be legitimate content for their site (above link is marked for deletion). I find this odd, since that's the only content I've ever read on Wikisource... does anyone know what the appropriate place to put source code like this is? I saw Wikibooks suggested on Wikisource, but it seems excessive to create a whole book just for the Euclidean algorithm. Perhaps a subpage on Wikipedia, like Euclidean algorithm/Source code would be more appropriate? --Dantheox 16:56, 6 May 2006 (UTC)
Do you have a link to the discussion in Wikisource? In particular, where did they suggested Wikibooks? Actually I think we should not create a special solution for the Euclidean algorithm but as far as possible follow the general solution suggested (if there is any). --NeoUrfahraner 06:04, 8 May 2006 (UTC)
I'm afraid wikibook is not the place for source code either-except appendix for an algorithm book, but for the more general case of source code, this is not a long-term solution. Sadly, now we have only limited solutions: Either get another wikipedia page for it(but don't use subpage, it's not the practice of wikipedia except for project page, user page, or temporary page for article rewrite, etc), maybe called Implementations of euclidean algorithm, because I observe that more detailed proofs of maths theorem take such measure also, like Proofs of Fermat's little theorem; another type of example is Sample chess game; OR, store a private copy in comment of the article itself, in this talk page, in our user page, or local copy: this is of course the very last resort if all else fails. P.S.: Speaking of general solution, unfortunately there isn't any that community consensus has made. I think we've uncovered a rather large problem-that many algorithm page is actually more of a "implementation" page than a description page. --Lemontea 07:56, 9 May 2006 (UTC)


NeoUrfahraner -- some links to check out: [1], and perhaps [2]. Source code is classified as "reference data," akin to the first million digits of Pi. There was a fairly recent vote on whether to include such "reference data" on Wikisource, and it came out rather strongly in favor of exclusion. This seems like a bit of a bombshell.. the only reason I've ever had to go to Wikisource was for extra source code snippets. It is WikiSOURCE, after all. --Dantheox 15:26, 9 May 2006 (UTC)
I see. Fortunately for the special case of the Euclidean algorithm there is no urgent reason to react because the code in Wikisource is additonally available in the article or here at the discussion page. Personally I still think that wikibooks might be a good place for something like "The book of source code". In the German wikibooks, a related case is Archive of (mathematical) proofs, which should become something like Paul Erdős's "The Book," an imaginary book in which God had written down the best and most elegant proofs for mathematical theorems. This book was created because it was agreed that wikipedia is not a good place for mathematical proofs but referenceable place is needed. IMHO source code is a similiar case. --NeoUrfahraner 06:40, 10 May 2006 (UTC)

[edit] Should the code stay?

I know that wikipedia has no set in stone policy for algorithms on wikipedia, on whether code implementations are allowed or not. Of the many random algorithm pages I checked, many don't include an implementation(pseudocode only), while others do the opposite(implementation only), and yet some others do both. While wikipedia is not a code repository, I think we shouldn't be too strict and include *no* implementation at all. Having 50% of the article made up of implementation code is of course a bad thing, but I don't see any reason why the little, short, and concise implementation, as in this case, can't stay, even at the end of the article. Feel free to voice your opinion on this. --Lemontea 09:49, 14 April 2006 (UTC)

I agree that the short implementation in this article was very illustrative and I have no problem when it is inculded again. On the other hand, I copied these code examples (together with my version mentioned above) to Wikisource, so a different solution might be to better crossreference the articles in Wikipedia and Wikisource. --NeoUrfahraner 15:06, 14 April 2006 (UTC)
The code should absolutely stay. Main reason is, readers want it, and this particular piece of code is clear and brief. I don't really believe Wikisource is any better a place for code than Wikipedia - I have a category for the Euclidean algorithm on my own wiki, LiteratePrograms, but that's not a Wikimedia Foundation project. Deco 16:18, 12 May 2006 (UTC)

[edit] Not logical?!

This text is from the begining of the article -

The Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers.

And this after -

Description of the algorithm

Given two natural numbers a and b, and assuming a is greater ...

First we have that a nad b are integers and then natural numbers.

--Čikić Dragan 15:24, 12 May 2006 (UTC)

[edit] Complexity

Shd, I'm reverting your edit because it is wrong on all accounts. First, it is a standard fact that the Euclidean algorithm has time complexity O(n2), although division is not known to be linear time. It works even with the quadratic school-book long division, essentially because the quotients are small (just do the math carefully). Second, it does not make any sense to plug in time complexity of division into the time bound on the original, subtraction-based, Euclid's algorithm, as there are no divisions (or multiplications) performed by the algorithm. -- EJ 17:54, 4 June 2006 (UTC)

I think this section needs a quick sketch of why the algorithm is O(n2) when it requires O(n) divisions, and division is not in general O(n). A reference would also do nicely. As is, this assertion is somewhat surprising, and comes out of nowhere. --Dantheox 17:27, 14 July 2006 (UTC)
Sketch done. As for a reference, both books we have in the "References" section include it as an exersize; I tend to think this is sufficient. -- EJ 15:36, 16 July 2006 (UTC)
Thanks for the correction. However, I was not wrong on all accounts; I changed the bad use of atomic operations. Shd 14:27, 17 July 2006 (UTC)

[edit] Implementation again

I'll add some more souce to the "real programming language vs. pseudocode" flame. Personally me is for pseudocode, but it won't hurt adding an implementation in another langauge, if people here decide, to do so. Here is Haskell (untested, baware of bugs and errors!).

gcd :: Integer -> Integer -> Integer
gcd a 0 = a
gcd a b = gcd b a%b

--88.68.34.243 12:24, 9 June 2006 (UTC)

Notice that the only reason the c++ code stayed here is that wikipedia has no offical policy saying whether to use pseudocode or any programming language to show an algorithm, and so we have pseudocode for non-programmer, and c++ for programmers as c++ is rather popular, which effectively satisfy most people. It would then be unacceptable to add other programming language's code, since wikipedia is not a code repository. (Think again, Haskell? I can imagine people adding code for php, perl, Pascal, python, Prolog...it's endless) Previously, this isn't a big problem, as we can just put all these implementation at wikisource, but now wikisource decided to reject all these, so, unfortunately, there's no place for your code to stay. --Lemontea 03:02, 10 June 2006 (UTC)

[edit] Why Fibonacci numbers?

under "running time", it is not clear why the worst case is when two successive Fibonacci numbers are used...could anyone add some explaination? PIX 17:43, 20 September 2006 (UTC)

I added a parenthetical remark about the way I understand it, but it might be obscure if you're not familiar with continued fractions. A simpler explanation would take up a lot of space. —Keenan Pepper 03:26, 21 September 2006 (UTC)
Retrieved from "http://en.wikipedia.org../../../e/u/c/Talk%7EEuclidean_algorithm_c262.html"