BlogGang.com : : Forsberg - Binary GCD algorithm

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

Create Date : 23 ธันวาคม 2548

Last Update : 26 ธันวาคม 2548 2:34:49 น.

0 comments

Counter : 612 Pageviews.