Binary GCD algorithm

จากที่เห็นกันมาแล้วว่า Euclidean algorithm ง่ายต่อการเข้าใจแล้วก็ง่ายต่อการเขียน อีกทั้งยังเร็วกว่าวิธีที่เราคิดกันขึ้นมาเอง แต่ว่า ความเร็วของ Euclidean algorithm ก็ยังไม่สามารถเทียบเท่ากับ binary GCD algorithm ข้อดีอีกอย่างของ algorithm นี้คือสามารถนำมาเขียนบน computer programming ได้ง่ายเช่นเดียวกับ Euclidean algorithm
Binary GCD algorithm มีวิธีการดังนี้

1. ถ้า a = 0 จะทำให้ gcd(a, b) = b เพราะอะไรก็ตามนำมาหาร 0 ก็ได้ 0 แน่นอนอยู่แล้ว และ b ก็เป็นตัวนึง
2. ถ้าทั้ง a และ b เป็นเลขคู่ gcd(a, b) = 2*gcd(a/2, b/2)
3. ถ้า a เป็นเลขคู่ และ b เป็นเลขคี่ gcd(a, b) = gcd(a/2, b) เพราะว่ายังไงซะ 2 ก็ไม่ใช่ ตัวประกอบนึงแน่ ๆ
4. ถ้า a เป็นเลขคี่ และ b เป็นเลขคู่ gcd(a, b) = gcd(a, b/2) เหตุผลเหมือนข้อ 3
5. ถ้าทั้ง a และ b เป็นเลขคี่ gcd(a, b) = gcd(abs((a – b)/2), b) = gcd(a, abs((a – b)/2)) เหตุผลมาจาก Euclidean algorithm รวมกะ ข้อ 3 และ 4

เขียนเป็น C/C++ ได้ดังนี้

unsigned int gcd(unsigned int a, unsigned int b)
{
  unsigned int c = 0;
  while((a & 1) == 0 && (b & 1) == 0) // both are even number
  {
      a >>= 1;    // divided by 2
      b >>= 1;    // divided by 2
      c++;        // power of 2 to multiply back
  }

  do
  {
      if((a & 1) == 0)
          a >>= 1;
      else if((b & 1) == 0)
          b >>= 1;
      else if(a >= b)
          a = (a - b) >> 1;
      else  
          b = (b - a) >> 1;
  } while (a > 0);
  return b << c;
}

เขียนแบบ Recursive ได้เป็น

unsigned int gcd(unsigned int a, unsigned int b)
{
  if(a == 0)
      return b;
  else if((a & 1) == 0 && (b & 1) == 0)
      return 2 * gcd(a >> 1, b >> 1);
  else if((a & 1) == 0)
      return gcd(a >> 1, b);
  else if((b & 1) == 0)
      return gcd(a, b >> 1);
  else if(a >= b)
      return gcd((a - b) >> 1, b);
  else
      return gcd(a, (b - a) >> 1);
}

ที่มา และข้อมูลเพิ่มเติม

Binary GCD algorithm at answers.com

Eucledian algorithm at my blog or at my blogger.com