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.