Talk:Euclidean algorithm

From Algorithmist

Still think we should use the common notation of listing the complexity in terms of bits as in common in these kind of algorithms.. Larry 17:05, 3 Dec 2005 (EST)

Ok then, I guess you're right. I've reverted it (almost). Aboyner 17:14, 3 Dec 2005 (EST)

To be honest the previous explanation was more clear to me... Easy step by step proof. And the key is the following sentence:

The fact we need is that gcd(a,b) = gcd(a,b - a).

Actually this algorithm was always hard to see for me why works, but the previous proof was very good. --Tomi 20:01, 3 Dec 2005 (EST)

Ok then, feel free to revert it back. I still feel that gcd(a,b) = gcd(a,a - b) is only a special case of gcd(a,b) = gcd(a,a - kb), and when we can prove the general thing directly, why prove the special thing and then invoke "We can iterate"? But of course, my notion of "simple proof" is "less notation, more high-level simple descriptions in English", but maybe not everyone agrees.

This is better, thanks! ;) --Tomi 04:55, 4 Dec 2005 (EST)

gcd should work for negative numbers also, which is why I made it "b!=0" instead of "b>0". (Note that "a mod b" is defined for all integers, not just positive ones.) Also, is VB the preferred pseudocode style? ;)

Looks to me that there isn't much "pseudo" about the pseudocode in this example, although I guess you could get away with it, since it's such a simple piece of code. (I usually implement gcd as
int gcd(int a, int b) {return b%a?gcd(b%a,a):b;}
myself, but there's even less pseudo there :) Hubert 03:31, 4 Dec 2005 (EST)

Hehe, "pseudocode" just means it should be easy to understand, and should not get into language-specific details... I guess the only way this code can be made more "pseudo" is to change "if (b!=0)" to "If b is not zero", etc. Also, I don't see why VB-style pseudocode ("var a as Integer") is better than C-style pseudocode ("Integer a"). In fact, the "as" confuses me -- shouldn't it be "var a is Integer"? :)

IMHO, gcd is a function that takes in two integers and returns their gcd -- why must pseudocode emphasize that "a" is a "var"? Isn't "var" specific to some programming language? And if you want to emphasize it, then Pascal-style would be best: "variable a : Integer".

Anyway, I must warn you that your code is not entirely bugfree -- try passing a=0 to it! Better would be
int gcd(int a,int b) { return b?gcd(b,a%b):a; }
(which is what this article suggests too). Aboyner 03:50, 4 Dec 2005 (EST)

I think that first of all, pseudocode shall be as readable as possible. For example, instead of "func" use "function". Also, the "var" in some languages means that the variable is passed by reference, i.e., the function can modify it. When calling gcd this is often not wanted, but the curennt header may confuse people that use these languages. Thus the header should only specify the types of the variables, nothing else. Also, it is nice to specify the type of the returned value and to use both indentation and braces to specify blocks of code. (I changed the pseudocode accordingly, feel free to revert it back if the majority disagrees with my opinions ;)

P.S.: Larry (or someone else :), please choose a standard way of writing pseudocode on this wiki, consistency is a Good Thing. misof 4 Dec 2005

Also, I believe that the complexity estimate is wrong. I think that for two n-bit numbers the algorithm makes O(n) recursive calls, and in each of these calls the most expensive operation is computing the modulo. Without checking any referrences I'm not really sure about the fastest way of doing it, but it's clearly at least linear in n (and probably even slower). misof 4 Dec 2005

Wow, this grew fast.

Ya, I agree that there should be some standard pseudo-code guide. Probably stick it in somewhere.

Actually, I think this algorithm runs in quadratic time to the number of bits, since subtraction takes linear time, and there can be linear number of steps.. =)

Larry 06:02, 4 Dec 2005 (EST)