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     0 comment Last Update : 26 ธันวาคม 2548 2:34:49 น.     Counter : 683 Pageviews.   Share Tweet

Greatest Common Divisor วันนี้กลับไปอ่านหนังสือ discrete math สมัยเรียนมหาลัย ไปเจอบทนึงพูดถึงเรื่อง GCD หรือ Great Common Divisor หรือในไทยก็ ห.ร.ม. หรือ หารร่วมมาก วิธีการหาหารร่วมมากโดยปรกติ ก็ คือ แยก factor ของตัวเลข 2 ตัวที่ต้องการหา GCD แล้วก็นำมาหารกันจนเหลือตัวที่ไม่สามารถหารกันลงแล้ว เช่น GCD(14, 56) = 2x7 and 2x2x2x7 = 1 and 2x7 = 14 วิธีเขียน Program ก็อาจจะทำได้โดย int GCD(int a, int b) { int temp = a; int temp2 = b; int gcd = 1; while((temp % 2 == 0) && (temp2 % 2 == 0)) { temp /= 2; temp2 /= 2; gcd *= 2; } for(int i = 3; i <= a && i <= b; i+=2) { while((temp % i == 0) && (temp2 % i == 0)) { temp /= i; temp2 /= i; gcd *= i; } } return gcd; } แต่มีอีกหลายวิธีที่ทำได้รวดเร็วกว่าวิธีที่เสนอมานี้เยอะมาก วิธีนึงก็คือ วิธี Euclidean วิธีให้ความคิดไว้ว่า GCD ของ a กับ b เท่ากับ GCD ของ b กับ abs(a-b) หรือสามารถเขียนเป็น program ได้ดังนี้ int GCD(int a, int b) { if(a % b == 0) { return b; } else { return GCD(b, abs(a - b)); } } จะเห็นได้ว่า วิธี Euclidean ทำให้ program ง่ายขึ้นและรวดเร็วขึ้นด้วย   Create Date : 22 ธันวาคม 2548     1 comment Last Update : 22 ธันวาคม 2548 21:38:22 น.     Counter : 594 Pageviews.   Share Tweet

Pointer Arithmetics in C/C++ เวลาที่เราเราแสดงผลตัวแปรที่เป็น pointer ปรกติค่าที่พิมพ์ได้ก่อน dereference จะเป็นค่าตำแหน่งของตัวแปรที่มันชี้อยู่ เช่น int i = 10; int *p = &i; cout << p << endl; ผลที่ได้จะคล้าย ๆ กะค่าข้างล่างนี้ ffbefa80 ทีนี้มีข้อสงสัยอยู่หนึ่งอย่างคือ ถ้าเราเอาเลขของ pointer 2 ตัวนี้มาลบกันในขณะที่เป็น pointer อยู่ หรือนำค่า pointer มาบวกกับตัวเลขจะเกิดอะไรขึ้น ขั้นแรกเรามาดูก่อนกะ operator + กับ pointer int i = 10; int *p = &i; cout << p << endl; cout << p + 1 << endl; ผลลัพธ์ที่ได้ไม่ใช่ ffbefa80 ffbefa81 นะครับแต่ผลที่ได้จะคล้าย ๆ กะค่าข้างล่างนี้ ffbefa80 ffbefa84 คือค่าที่เพิ่มขึ้นมาจะเป็น 1*sizeof(datatype) นั้น ๆ เช่นเดียวกันกับ operator - คือถ้าเอา address ของตัวแปรนั้น ๆ มาลบกันค่าที่ได้ก็ไม่ใช่ ค่าที่เป็น address มาลบกันเฉย ๆ แต่จะเป็น ค่าในลักษณะเดียวกันกับ operator + มาดู Program ตัวอย่างกันดีกว่า #include <iostream> #include <iomanip> using namespace std; int main() { int a; int b; cout << "&a = " << setw(8) << setfill('0') << hex << &a << endl << "&b = " << setw(8) << setfill('0') << hex << &b << endl << "&a - &b = " << (&a - &b) << endl << endl; return 0; } &a = ffbefa80 &b = ffbefa7c &a - &b = 1   Create Date : 21 ธันวาคม 2548     0 comment Last Update : 21 ธันวาคม 2548 22:13:03 น.     Counter : 421 Pageviews.   Share Tweet

union กะที่ใช้ที่น่าสนใจ union ในภาษา C/C++ เป็นส่วนที่มีที่ใช้ไม่ค่อยมากมายนัก วันนี้ผมจะมาแสดงที่ใช้งานนึงที่น่าสนใจของ union ก่อนอื่นก็ขอพูดถีึง union ก่อนนะครับ union เป็น type นึงของ data ก็ตามชื่อคือ มัน union ใช้พื้นที่จัดเก็บร่วมกันใน union type นั้น ๆ ขนาดของมันก็จะมีขนาดเท่ากับ max ของขนาดที่อยู่ใน union นั้น ๆ แต่ถ้ามีขนาดเท่ากัน เราสามารถนำมันไปใช้งานได้ตามตัวอย่างข้างล่างนี้คือ เรารู้ว่า data type นึงของเรามีขนาดเท่าไหร่ เราก็ประกาศ char array ให้มีขนาดเท่ากันเพื่อที่มันจะ share พื้นที่กันได้เต็มที ในตัวอย่างแสดงให้เห็นว่า เราสามารถ แสดง int ออกมาเป็น char array ได้โดยไม่ต้องเขียนอะไรเพิ่มมากเลยเพียงแค่ใช้ union นอกจากนี้เรายังสามารถ demonstrate endianess ของแต่ละ　cpu architecture ด้วย #include <iostream> #include <iomanip> using namespace std; union testunion { int i; char c[4]; }; int main() { union testunion a; a.i = 0x01020304; cout << setw(8) << hex << setfill('0') << a.i << " : " << setw(2) << setfill('0') << hex << (int)a.c[0] << setw(2) << setfill('0') << hex << (int)a.c[1] << setw(2) << setfill('0') << hex << (int)a.c[2] << setw(2) << setfill('0') << hex << (int)a.c[3] << endl; return 0; } Windows Intel (of course) 01020304 : 04030201 Solaris Sparc 01020304 : 01020304 Solaris Intel 01020304 : 04030201 หวังว่า ตัวอย่างนี้จะทำให้เข้าใจการ concept และการใช้งานของ union ได้มากขึ้น   Create Date : 20 ธันวาคม 2548     0 comment Last Update : 20 ธันวาคม 2548 22:40:43 น.     Counter : 410 Pageviews.   Share Tweet

XOR เอาไปทำอะไรได้บ้าง bitwise XOR operator หรือ ^ เป็น operator ที่ไม่ค่อยได้เห็นที่ใช้เท่าไหร่นัก 1st tip วันนี้จะเป็นการใช้ XOR เพื่อทำการ swap ค่าของตัวแปร ก่อนอื่นก็ขออธิบายว่า XOR มันทำงานอย่างไร XOR operands ทั้ง 2 ตัวถ้าค่าเหมือนกันจะ return false ไม่เหมือนกัน return true ตัวอย่างเช่น true xor true ==> false true xor false ==> true etc. หรือถ้าเขียนเป็น 1 กะ 0 ก็จะได้ 1 xor 1 ==> 0 1 xor 0 ==> 1 xor มีคุณสมบัติอีกอย่างนึงคือ ค่าใดก็แล้วแต่ ถ้านำไป xor กะค่าอื่น 2 ครั้ง ค่าที่ได้ก็จะกลับคืนไปเป็นค่าเดิม เช่น 1 xor 0 ==> 1 นำไป xor 0 อีกที ก็จะได้ 1 1 xor 1 ==> 0 นำไป xor 1 อีกทีี ก็จะได้ 1 น่าแปลกนะครับ และนี่ก็เป็นคุณสมบัติที่ทำให้เราสามารถเอาไปใช้เพื่อทำการ swap ค่า ถ้าให้ a xor b xor b ==> a b xor a xor a ==> b มาถึงการ swap ละครับ โดยทั่วไปการ swap ค่าก็จะทำได้โดย temp = a; a = b; b = temp; เราก็จะได้ค่า a สลับกะ b แต่ในที่นี้เราต้องทำการเพิ่มตัวแปรเข้าไปอีก 1 ตัว สมมติเรามีตัวแปรแค่ 2 ตัวละครับ เราก็สามารถทำได้ดังนี้ครับ a = a ^ b;　// a' = a ^ b b = a ^ b; // b' = a' ^ b ซึ่งก็คือ b' = a ^ b ^ b ซึ่งก็เป็น a นั่นเอง a = a ^ b; // a'' = a' ^ b' ซึ่งก็คือ a'' = a ^ b ^ a ซึ่งก็เป็น b นั่นเอง นี่เป็นที่ใช้หนึ่งของ XOR   Create Date : 19 ธันวาคม 2548     2 comment Last Update : 19 ธันวาคม 2548 23:55:06 น.     Counter : 585 Pageviews.   Share Tweet