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 相比之下，實在是多很多很多。
- struct BigNumber
- {
- int array[1000]; // 一個欄位存一個數字，可以存 1000 位數
- bool sign; // 正負號
- int length; // 位數
- };
通常我們習慣將低位數放在索引值（ index ）比較小的位置，高位數放在索引值比較大的位置。假設要存放 680468975231245 。
每個人對陣列的思考模式不一樣，像這裡就是由左至右的，另外也有人覺得陣列是由右至左、由上至下、彎彎曲曲的、 …… 。要怎麼思考都是可以的，一以貫之就好囉。
陣列右端劃上橫線的格子，通常我喜歡存 0 進去，這樣子做運算的時候會比較方便；如果將橫線的部分設成 -1 ，在運算時會出現點麻煩，所以我不喜歡、也不建議這麼做。
大數的各種功能
設計好了資料結構之後，接下來便要開始設計大數的各種功能，例如說顯示大數，以及大數的四則運算。
為了讓初學者能夠清楚了解大數運算的方式，以下的程式碼舉要治繁，而不修邊幅。各位了解箇中道理之後，可以自行添加修改，讓程式碼更美觀。
顯示大數
在螢幕上印出大數可以這麼做。
- void print(int a[100])
- {
- int i = 100 - 1; // 要印的數字位置
- while (a[i] == 0) i--; // 數字開頭的零都不印
- while (i >= 0) cout << a[i--];
- }
如果這個大數有可能是零，就得加個幾行程式碼。
- void print(int a[100])
- {
- int i = 100 - 1;
- while (i >= 0 && a[i] == 0) i--;
- if (i < 0)
- cout << '0';
- else
- while (i >= 0) cout << a[i--];
- }
比較大小
比較哪個數字比較大。
- // a > b
- bool largerthan(int a[100], int b[100])
- {
- for (int i=100-1; i>=0; i--) // 從高位數開始比，對應的位數相比較。
- if (a[i] != b[i]) // 發現 a b 不一樣大，馬上回傳結果。
- return a[i] > b[i];
- return false; // 完全相等
- }
加法運算
大數的四則運算不會很困難。這裡提供大數加法的粗略程式碼，希望能一目瞭然。
- // c = a + b;
- void add(int a[100], int b[100], int c[100])
- {
- for (int i=0; i<100; i++) // 對應的位數相加
- c[i] = a[i] + b[i];
- for (int i=0; i<100-1; i++) // 一口氣進位
- {
- c[i+1] += c[i] / 10; // 進位
- c[i] %= 10; // 進位後餘下的數
- }
- }
大數的運算有個有趣的地方，就是運算時不用立即進位，可以後來再去一口氣進位。這件事情值得細想。
UVa 10035
減法運算
這裡繼續提供大數減法的粗略程式碼。
- void sub(int a[100], int b[100], int c[100])
- {
- for (int i=0; i<100; i++)
- c[i] = a[i] - b[i];
- for (int i=0; i<100-1; i++) // 一口氣借位和補位
- if (c[i] < 0)
- {
- c[i+1]--; // 借位
- c[i] += 10; // 補位
- }
- }
乘法運算
大數乘法的粗略程式碼。我一定要強調它是粗略的。
- void mul(int a[100], int b[100], int c[100])
- {
- for (int i=0; i<100; i++)
- c[i] = 0;
- for (int i=0; i<100; i++)
- for (int j=0; j<100; j++)
- if (i+j < 100)
- c[i+j] += a[i] * b[j];
- for (int i=0; i<100-1; i++) // 一口氣進位
- {
- c[i+1] += c[i] / 10;
- c[i] %= 10;
- }
- }
至於大數乘以 int 是比較容易的。
- void mul(int a[100], int b, int c[100])
- {
- for (int i=0; i<100; i++)
- c[i] = a[i] * b;
- for (int i=0; i<100-1; i++) // 一口氣進位
- {
- c[i+1] += c[i] / 10;
- c[i] %= 10;
- }
- }
在「多項式乘法」章節將介紹更快的方法。
除法運算
大數除法可直接使用長除法。還滿複雜的。程式碼就隨便寫寫囉！
- void div(int a[100], int b[100], int c[100])
- {
- int t[100];
- for (int i=100-1; i>=0; i--)
- for (int k=9; k>0; k--) // 嘗試商數
- {
- mul(b+i, k, t);
- if (largerthan(a+i, t))
- {
- sub(a+i, t, c+i);
- break;
- }
- }
- }
商數範圍是零到九，所以必須一一嘗試。可以利用高位數相除來估計商數的範圍，便不必一一嘗試。這裡不加說明。
至於大數除以 int 是比較容易的。
- void div(int a[100], int b, int c[100])
- {
- int r = 0;
- for (int i=100-1; i>=0; i--)
- {
- r = r * 10 + a[i];
- c[i] = r / b;
- r %= b;
- }
- }
