ใน entry นี้ผมจะกล่าวเกี่ยวกับเทคนิค Bignum ซึ่งมันคืออะไร ลองอ่านต่อได้เลยครับ
หลายคนที่เขียนโปรแกรมคงเคยเจอโจทย์ หรืองานที่เกี่ยวกับตัวเลขซึ่งเกินขอบเขตของตัวแปร
ในภาษานั้นๆ จะรับไหว ยกตัวอย่างเช่น ในภาษา C ตัวแปรประเภท int นั้นบน Unix สามารถ
เก็บข้อมูลประเภทจำนวนเต็มที่มีค่าอยู่ในช่วง [-(232), 231] และถึงแม้จะเป็นแบบ unsigned
(สั้นๆ ง่ายๆ คือไม่เก็บจำนวนเต็มลบ) ก็จะเก็บได้แค่ [0, 232] อยู่ดี
ซึ่งจำนวนเต็มที่อยู่ในช่วงดังกล่าวนั้นมีจำนวนหลักสูงสุดแค่เพียง 10 หลักเท่านั้นเอง แต่ถ้า
หากเราต้องการบวกเลข 100 หลักสองตัวหละ? เราจะใช้ตัวแปรอะไรมารับค่า และจะคำนวณค่ายังไง
นี่ก็คือที่มาของเทคนิคการทำ Bignum ครับ
(ต่อไปนี้ผมจะนำเสนอแนวคิด และวิธีการโดยใช้ภาษา C มาเป็นตัวดำเนินเรื่องนะครับ)
มาเริ่มกันเลยดีกว่าครับ…
สมมติว่าปัญหาของเราคือ “การบวกเลขจำนวนเต็มบวกที่มีจำนวน n หลัก (n เป็นจำนวนเต็ม และ 0 < n <= 100)”
ในทีนี้หากเราจะใช้ตัวแปร int ในการรับค่านั้น ก็จะสามารถคำนวณได้แค่เคสที่จำนวนเต็มที่ input เข้ามา
มีค่าไม่เกิน unsigned int ซึ่งถ้ามองเผินๆ ก็คือไม่เกิน 10 หลักนั่นเอง
แล้วจะรับค่ายังไง?
ให้เรามองตัวเลขที่ input เข้ามาเป็น string แทนครับ ก็จะได้ว่ามันคือ string จำนวน n ตัวอักษรนั่นเอง
ในที่นี้เราจะใช้ Array of Char จำนวน 101 ช่องในการเก็บ input ที่ป้อนเข้ามา
แล้วจะบวกยังไง?
ปกติแล้วถ้าเกิดว่าเรารับจำนวนเต็มเข้ามาใส่ตัวแปร int เนี่ย เราจะสามารถดำเนินการบวกมันได้เลย
ด้วยตัวดำเนินการ + แต่สำหรับตัวแปร string นั้นเราจะบวกมันด้วยตัวดำเนินการ + ไม่ได้
เพราะมันคือ Array of Char
ให้เรานึกย้อนไปสมัยประถม (หรืออนุบาล) ที่คุณครูของเราสอนบวกเลขจำนวนเต็ม นึกกันออกหรือยังครับ?
ถ้าหากว่านึกออกแล้ว ให้ทบทวนกับมันดีๆ ครับ เพราะเราจะเอามันมาใช้ =)
ตอนประถม (หรืออนุบาล) นั้น ไม่สิ ในชีวิตประจำวัน เวลาเราจะบวกเลข เราก็ไล่บวกไปทีละหลัก จับคู่
มันไปเรื่อยๆ จนหมด แล้วก็ดูผลลัพธ์ที่ออกมาใช้ไหมครับ
ตัวอย่างเช่น 12 + 12
เราก็เอา 2 + 2 เอาใส่ไว้ด้านหลังสุด แล้วก็เอา 1 + 1 แล้วใส่ไว้ด้านหน้า 2 ซึ่งผลลัพธ์มันก็คือ 24
แล้วพอโตขึ้นมาหน่อย (หรือเรียนต่อไปอีกหน่อย) เราก็จะพบว่ามันมีสิ่งที่เรียกว่า “การทด” ด้วย
ซึ่งมันก็จะเกิดจากการเอา 19 + 19 เราก็จะมอง 9 + 9 แต่ว่าค่าของ 9 + 9 นั้นมันได้ 18 ซึ่งเป็นเลข
จำนวน 2 หลัก เราไม่สามารถนำมันไปวางได้เลย แต่เราจะนำเลขข้างหลังมาวาง แล้วเอาเลขข้างหน้า
ไปรอบวกกับหลักถัดไป ในทีนี้เราก็จะได้ว่า 8 ของเราเอาไปวางไว้ และ 1 รอไปบวกกับหลักต่อไป
จากนั้นก็มอง 1 + 1 ได้ 2 แต่ว่าเรามีเลข 1 อีกตัวที่มาจากหลักก่อนหน้าอยู่ด้วย ก็จัดการ +1 เพิ่มไปอีก
ก็จะได้ว่าผลลัพธ์ของเราคือ 38
พอจะปิ๊งๆ อะไรขึ้นมาหรือยังครับ ถ้าปิ๊งแล้วก็ไปจัดการลงมือเขียนโค้ดได้เลยครับ แต่ถ้าใครที่ยัง
ไม่ปิ๊ง ก็อ่านต่อเลยครับ
หลังจากระลึกวิธีบวกเลขสมัยประถมกันไปแล้ว เรามากลับเข้าสู่ปัญหาของเราดีกว่าครับ
ตอนนี้เรามี string อยู่สองตัวคือ ตัวตั้ง และ ตัวบวก ซึ่งแยกเป็นหลักๆ อยู่ใน Array แต่ละช่อง
ไว้อยู่แล้ว แล้วทำไมเราไม่ทำแบบตอนประถมหละ? ก็ไล่บวกมันเองทีละหลักเลยสิ
เราก็แค่วน for จากหลักสุดท้ายของตัวตั้งและตัวบวก บวกกันไปทีละหลัก ถ้าหากว่าคู่ไหนที่บวก
กันแล้วได้ > 9 เราก็จัดการทดขึ้นไปให้กับหลักต่อไปด้วย เสร็จแล้วก็แสดงผลคำตอบออกมา
แต่ว่าอย่าลืมนะครับว่า ’1′ + ’1′ มันไม่ได้ ’2′ นะครับ อิอิ
และเนี่ยแหละครับคือ หนึ่งใน Bignum ที่บอกว่าเป็นส่วนหนึ่งก็เพราะว่านี่แค่การบวกเลข
จำนวนเต็มบวกครับ ยังเหลือ Opeartions อื่นๆ อีก เช่น การลบ การคูณ หรือ การหาร
ซึ่งทำยังไงนั้น ถ้าว่างๆ ผมอาจจะมาขยายความอีก หรือถ้าว่างๆ ก็ลองคิดกันดูครับ =)
สำหรับด้านล่างนี่คือตัวอย่างโค้ดที่ผมเขียนครับ (Bignum Positive Integer Addition)
/*Author: Zenn*/
#include <stdio.h>
#include <string.h>
int main(){
char A[101] = {0}, B[101] = {0}, C[102] = {0};
scanf(" %s", A); scanf(" %s", B);
int lenA = strlen(A), lenB = strlen(B);
int i, j, k, t = 0;
for(i = lenA-1, j = lenB-1, k = 0; (i >= 0) || (j >= 0); i--, j--, k++){
if(i >= 0) C[k] += (A[i]-'0');
if(j >= 0) C[k] += (B[j]-'0');
C[k] += t;
t = C[k]/10;
C[k]%=10;
}
if(t > 0){
C[k] = t;
k++;
}
for(i = k-1; i >= 0; i--) printf("%d", C[i]);
return 0;
}