大數 Big Number

Big Number

源自於  http://www.csie.ntnu.edu.tw/~u91029/Number.html

Big Number

「大數」就是很大的數字，大到無法以一個簡單的變數型態儲存這個值。

一般來說， int 這個變數型態，記憶體大小為 32 bit ，可以儲存數值範圍為 -2^31 到 2^31 - 1 的整數，大約是 1 後面再接九個零；而 long long 這個變數型態是 64 bit 的，可以儲存數值範圍為 -2^63 到 2^63 - 1 的整數。另外還有 unsigned 這個關鍵字，它能讓原本的變數型態能夠存入更大一點的正整數。

雖然 int 、 long long 的數值大小已經夠用了，但是人的慾望是無止盡的，總是想讓電腦能夠處理更大的數字、算得更精準。於是大數的技術就這樣產生了。

資料結構

要讓電腦存放這麼大的數字，有個好方法就是使用陣列。陣列有很多格子，一個格子存一個數字；只要宣告 1000 格大小的 int 陣列，就可以存 1000 位數了！至於一個 int 變數，充其量也不過十位數而已──陣列能存放的數值大小，和 int 相比之下，實在是多很多很多。

 

1. struct BigNumber
2. {
3.     int array[1000];    // 一個欄位存一個數字，可以存 1000 位數
4.     bool sign;          // 正負號
5.     int length;         // 位數
6. };

通常我們習慣將低位數放在索引值（ index ）比較小的位置，高位數放在索引值比較大的位置。假設要存放 680468975231245 。

每個人對陣列的思考模式不一樣，像這裡就是由左至右的，另外也有人覺得陣列是由右至左、由上至下、彎彎曲曲的、 …… 。要怎麼思考都是可以的，一以貫之就好囉。

陣列右端劃上橫線的格子，通常我喜歡存 0 進去，這樣子做運算的時候會比較方便；如果將橫線的部分設成 -1 ，在運算時會出現點麻煩，所以我不喜歡、也不建議這麼做。

大數的各種功能

設計好了資料結構之後，接下來便要開始設計大數的各種功能，例如說顯示大數，以及大數的四則運算。

為了讓初學者能夠清楚了解大數運算的方式，以下的程式碼舉要治繁，而不修邊幅。各位了解箇中道理之後，可以自行添加修改，讓程式碼更美觀。

顯示大數

在螢幕上印出大數可以這麼做。

 

1. void print(int a[100])
2. {
3.     int i = 100 - 1;            // 要印的數字位置
4.     while (a[i] == 0) i--;      // 數字開頭的零都不印
5.     while (i >= 0) cout << a[i--];
6. }

如果這個大數有可能是零，就得加個幾行程式碼。

 

1. void print(int a[100])
2. {
3.     int i = 100 - 1;
4.     while (i >= 0 && a[i] == 0) i--;
5.     
6.     if (i < 0)
7.         cout << '0';
8.     else
9.         while (i >= 0) cout << a[i--];
10. }

比較大小

比較哪個數字比較大。

 

1. // a > b
2. bool largerthan(int a[100], int b[100])
3. {
4.     for (int i=100-1; i>=0; i--)    // 從高位數開始比，對應的位數相比較。
5.         if (a[i] != b[i])       // 發現 a b 不一樣大，馬上回傳結果。
6.             return a[i] > b[i];
7.     return false;       // 完全相等
8. }

加法運算

大數的四則運算不會很困難。這裡提供大數加法的粗略程式碼，希望能一目瞭然。

 

1. // c = a + b;
2. void add(int a[100], int b[100], int c[100])
3. {
4.     for (int i=0; i<100; i++)   // 對應的位數相加
5.         c[i] = a[i] + b[i];
6.         
7.     for (int i=0; i<100-1; i++) // 一口氣進位
8.     {
9.         c[i+1] += c[i] / 10;    // 進位
10.         c[i] %= 10;             // 進位後餘下的數
11.     }
12. }

大數的運算有個有趣的地方，就是運算時不用立即進位，可以後來再去一口氣進位。這件事情值得細想。

UVa 10035

減法運算

這裡繼續提供大數減法的粗略程式碼。

 

1. void sub(int a[100], int b[100], int c[100])
2. {
3.     for (int i=0; i<100; i++)
4.         c[i] = a[i] - b[i];
5.         
6.     for (int i=0; i<100-1; i++) // 一口氣借位和補位
7.         if (c[i] < 0)
8.         {
9.             c[i+1]--;           // 借位
10.             c[i] += 10;         // 補位
11.         }
12. }

乘法運算

大數乘法的粗略程式碼。我一定要強調它是粗略的。

 

1. void mul(int a[100], int b[100], int c[100])
2. {
3.     for (int i=0; i<100; i++)
4.         c[i] = 0;
5.  
6.     for (int i=0; i<100; i++)
7.         for (int j=0; j<100; j++)
8.             if (i+j < 100)
9.                 c[i+j] += a[i] * b[j];
10.                 
11.     for (int i=0; i<100-1; i++) // 一口氣進位
12.     {
13.         c[i+1] += c[i] / 10;
14.         c[i] %= 10;
15.     }
16. }

至於大數乘以 int 是比較容易的。

 

1. void mul(int a[100], int b, int c[100])
2. {
3.     for (int i=0; i<100; i++)
4.         c[i] = a[i] * b;
5.                 
6.     for (int i=0; i<100-1; i++) // 一口氣進位
7.     {
8.         c[i+1] += c[i] / 10;
9.         c[i] %= 10;
10.     }
11. }

在「多項式乘法」章節將介紹更快的方法。

UVa 338 10106

除法運算

大數除法可直接使用長除法。還滿複雜的。程式碼就隨便寫寫囉！

 

1. void div(int a[100], int b[100], int c[100])
2. {
3.     int t[100];
4.     
5.     for (int i=100-1; i>=0; i--)
6.         for (int k=9; k>0; k--) // 嘗試商數
7.         {
8.             mul(b+i, k, t);
9.             if (largerthan(a+i, t))
10.             {
11.                 sub(a+i, t, c+i);
12.                 break;
13.             }
14.         }
15. }

商數範圍是零到九，所以必須一一嘗試。可以利用高位數相除來估計商數的範圍，便不必一一嘗試。這裡不加說明。

至於大數除以 int 是比較容易的。

 

1. void div(int a[100], int b, int c[100])
2. {
3.     int r = 0;
4.     for (int i=100-1; i>=0; i--)
5.     {
6.         r = r * 10 + a[i];
7.         c[i] = r / b;
8.         r %= b;
9.     }
10. }