Talk:Euclidean algorithm/Archive 1

Pseudocode implementation

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. 202.88.172.204 08:10, 11 August 2002 (UTC)

Agree on pseudocode

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 213.39.193.73 12:53, 17 March 2004 (UTC)

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. 203.62.227.74 10:18, 3 May 2004 (UTC)

Time Complexity

Could someone please tell me the time complexity of the original euclids algorithm. This is the one which uses subtraction only. Thanks. 138.253.176.32 10:31, 16 November 2004 (UTC)

Asymptotically or Worst-Case?

The article states that the binary GCD algorithm is asymptotically $O(n^{2})$. 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. 199.106.52.24 01:31, 19 November 2004 (UTC)

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(n^{2})$ means precisely that, for large enough n, it runs in time at most a constant times n². 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(n^{2})$ 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?). 199.106.52.24 22:57, 24 November 2004 (UTC)

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)

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. Watsonladd 21:48, 24 November 2004 (UTC)

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)

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. Horndude77 00:22, 6 July 2005 (UTC) (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)

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)