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

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