Talk:Euclidean algorithm
|
|
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 |
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.
Time Complexity
Could someone please tell me the time complexity of the original euclids algorithm. This is the one which uses subtraction only. Thanks.
Asymptotically or Worst-Case?
The article states that the binary GCD algorithm is asymptotically <math>O(n^2)<math>. 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 <math>O(n^2)<math> 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 <math>O(n^2)<math> 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?).
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.