typedef unsigned int ui;
ui gcd(ui u, ui v)
{
ui shift, diff;
if (u == 0 || v == 0)
return u | v;
/* Let shift := lg K,
where K is the greatest power of 2 dividing both u and v. */
for (shift = 0; ((u | v) & 1) == 0; ++shift)
{
u >>= 1;
v >>= 1;
}
while ((u & 1) == 0)
u >>= 1;
/* From here on, u is always odd. */
do {
while ((v & 1) == 0)
v >>= 1;
/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
if (u < v)
v -= u;
else
{
diff = u - v;
u = v;
v = diff;
}
v >>= 1;
} while (v != 0);
return u << shift;
}
Actually, this algorithm outperforms the basic euclidean algorithm, so their asymptotic performance are same. According to Wikipedia, it is sometimes 60% faster than normal euclidean algorithm [proven].
But who needs it when he can do the following:
int gcd(int a, int b)
{
while(b) b ^= a ^= b ^= a %= b;
return a;
}
Stunned? oh that's normal...
btw, who will ever need this... only good for assembly programming.
ReplyDeleteso, u mean that that entire whole code above is equivalent to below small one??
ReplyDeleteint gcd(int a, int b)
{
while(b) b ^= a ^= b ^= a %= b;
return a;
}
No, did I say they are same? Shall I break it down and make you see that this is just a normal gcd with a bitwise swap? can't you see the same old '%' (mod) operation the code?
Deleteint gcd(int a, int b) {
while(b) {
a = a % b;
b = b ^ a;
a = a ^ b;
b = b ^ a;
}
return a;
}
This is just a one liner for typical gcd to save you from the hassle. Nothing else. Who needs a bitwise gcd anyway unless you are doing an assembly language project.