Talk:Greatest common divisor

---

I don't know about you, but as far as I know (and forgive my Year 11 barin) in West Australian schools at least, this is known as the 'Highest Common Factor', not 'Greatest Common Divisor' - Mark Ryan

True... and its not just WA, its NSW (and VIC i think) as well -- in primary and high school they call it a HCF... but get to university, and they call it a GCD... I think GCD is the proper maths term, and HCF is just something the teaching profession in Australia invented, because they thought it would be easier to understand than GCD... -- SJK

---

When analyzing the runtime of Euclid's algorithm, it turns out that the inputs requiring the most steps are two successive Fibonacci numbers, and the worst case runtime is O(n), where n is the number of digits in the input (see Big O).

That's the case in Modified Euclid's Algorithm (with division modulo), not in Original Euclid's Algorithm (with subtraction). --Taw

---

What's this GCD algorithm called ? --Taw

def bgcd(a,b)
    g=1
    while(a&1==0 && b&1==0)
        g<<=1
        a>>=1
        b>>=1
    end
    while b!=0
        if a&1 == 0
            a>>=1
        elsif b&1 == 0
            b>>=1
        else
            if (a>b)
                a-=b
                a>>=1
            else
                b-=a
                b>>=1
            end
        end
    end
    return g*a
end

I don't know, but it is cool. Runtime is O(lg(n)); I wonder if it is faster than the ordinary division method? (I changed one line to make it a tiny bit simpler.) --AxelBoldt

It's much faster on most hardware because it doesn't use these slow modulo divisions, only ultra-fast shifts and substractions. If we're simplifying, here's an additional simplification. --Taw

Quicker GCD method

There is a possible quicker way to calculate Greatest Common Divisor at least on a computer anyway. This is because division by 2 in a computer is one of the quickest operations. The base ideas behind this algorithm are shown on the following link im not sure what the time complexity is but it should run faster. [1] (http://www.cut-the-knot.org/blue/binary.shtml)

Examples of no gcd

Would this article be the right place to put an example of an integral domain with two elements that don't have a gcd?

I think of this example:

<math>R = \mathbb{Z}[\sqrt{-3}], a = 4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3}), b = (1+\sqrt{-3})\cdot 2<math>

where <math>1+\sqrt{-3}<math> and <math>2<math> are two "maximal common divisors" but they are not associated, so there is no greatest common divisor.

--SirJective 17:40, 25 Nov 2004 (UTC)

I now inserted the example. --SirJective 22:53, 26 Jan 2005 (UTC)

greatest common denominator

KneeLess wrote:

rv, a denominator IS a divisor, just another name.

You are of course right! What you are not right about is saying that a greatest common divisor is a greatest common denominator.

For example, I give you two integers, 6 and 9. Their greatest common divisor if of course 18. How about their greatest common denominator? There is none, because there are no denominators and no fractions around whatsoever.

So, I explained in my edit summary, the greatest common divisor is a more general thing than the greatest common denonminator. They coincide only when we talk about fractions, but the notion of greatest common divisor has meaning way beyond that. As such, these concepts are not equivalent, and are not synonimous. Oleg Alexandrov 16:56, 2 Apr 2005 (UTC)

Oh, I see. Thanks for actually telling me what the problem is, instead of having a revert war. I did make a redirect from Greatest common denominator to this article, is that a problem? -- KneeLess 18:42, 2 Apr 2005 (UTC)

No revert wars (TM) :) The redirect is all right. Oleg Alexandrov 18:53, 2 Apr 2005 (UTC)

Actually we were both wrong. Greatest common divisor of 6 and 9 is 3. We meant the least common multiple, which for 6 and 9 is 18. Oleg Alexandrov 19:29, 2 Apr 2005 (UTC)