- 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