Friday, July 10, 2009

Binary GCD algorithm


Here is a sample code for calculating GCD bitwise:

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...

3 comments:

  1. btw, who will ever need this... only good for assembly programming.

    ReplyDelete
  2. so, u mean that that entire whole code above is equivalent to below small one??

    int gcd(int a, int b)
    {
    while(b) b ^= a ^= b ^= a %= b;
    return a;
    }

    ReplyDelete
    Replies
    1. 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?

      int 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.

      Delete