Just Like That .. (^-^)v

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 : 411 Pageviews.  

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิกช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 

Forsberg
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed

ผู้ติดตามบล็อก : 1 คน [?]




[Add Forsberg's blog to your web]