(空白標題)
大數問題我認為是新手必練題型之一，但實在沒時間去 implement 做 sample code，
把目前知道的作法先且粗略紀錄下來，以下探討「暫」以「無號大數」為標的，
下面的 code 憑印象之演示。
覺得這份 code、說明太不實用的話，可翻另一篇。
資料結構
一般可以用 link 去做大數，只要每多一 digit 就去新增一 node，但效能變得非常差，
不論在釋放記憶體還是做 travel 時都很糟，一般還是以 array 居多。
array 方式是將每個位數視為一個整數存進去，假設要存的數字為 763421 ，則儲存方式
為
arr[0]=1, arr[1]=2, arr[2]=4, arr[3]=3, arr[4]=6, arr[5]=7。
再來是該大數要陣列大小要多大、資料型態為何？一般在探討時都簡化問題，假定陣列大小
是固定的，也就是先定義一 macro - MAX。
#define MAX 200
int big[MAX];
這樣便可存下 200 個位數之數字，超過的話就把 MAX 再調大。但說明了這是「簡化問題」
，實際上還是用 malloc/ new 把內容放在 heap 裡面做動態管理好點。
從字串讀取
假設一傳入字串 char str[] = "12345"，代表著
str[0]='1', str[1]='2', str[2]='3', str[3]='4', str[4]='5'
但實際上欲存的大數陣列是從高位存到低位，也就是
big[4]=1, big[3]=2, big[2]=3, big[1]=4, big[0]=5
於是必須反著讀 str，同時還考慮到字串存的為 ascii value (假定為 ascii value)，
'0' 存 48，'1' 存 49... 故存到大數裡面時再扣掉 offset value = '0'
#define MAX 200
int big[MAX];
void read_from_string(int* big, char* str)
{
int i=0, len=strlen(str);
memset(big, 0, sizeof(int)*MAX);
for(i=len-1; i>=0; --i)
big[len - i - 1] = str[i] - '0';
}
memset 指令是用來把 big 陣列先全都清零，要用 for loop 慢慢跑也行。從整數 (正整數)
轉到大數的話就方便多了，觀念是將 x%10 之結果丟給大數 (取最後一位)，再將 x=x/10，
如果最後 x 除到 0 時，就代表轉完了。
void read_from_int(int *big, int x)
{
int i=0;
memset(big, 0, sizeof(int)*MAX); // 將 big 先清 0
while(x!=0){
big[i++]=x%10;
x/=10;
}
}
顯示
顯示時一律從最高位開始顯示，但必須注意，若大數存的是 3 ，整個陣列會是 00.....03，
在 3 前面有 199 個 0，所以必須先把前導 0 全都拿掉後再行輸出。
void big_print(int *big)
{
int i=MAX-1;
for(i=MAX-1;i>=0 && big[i]==0; --i);
while(i>=0) printf("%d", big[i]), --i;
}
但上面的 code 有問題，原因在於這種寫法，數值 0 就不會輸出，於是把去前導0之判別式
小改一下就可用。
void big_print(int *big)
{
int i=MAX-1;
for(i=MAX-1;i>0 && big[i]==0; --i);
while(i>=0) printf("%d", big[i]), --i;
}
這樣便可正常顯示大數。
加法
大數加法沒什麼技巧，和一般的小學的直式減法沒什麼兩樣，假設 rst = a+b
先算 rst[i] = a[i] + b[i] + carry ，其中 carry 代表 "上一筆運算之進位"。
若 rst[i] >=10 時，將 carry 設 1，再把 rst[i] 扣 10；
另一思維是，直接套公式 carry = rst[i] / 10 ，rst[i] = rst[i]%10，這裡採此方式。
void big_add(int *rst, int *a, int *b)
{
int i, sum, carry;
for(carry=i=0; i<MAX; ++i){
rst[i] = a[i] + b[i] + carry;
carry = rst[i] / 10;
rst[i]%=10;
}
}
減法
加法是用 carry，減法是用 borrow，和上敘思考一樣，以直式減法概念下去做。
void big_sub(int *rst, int *a, int *b)
{
int i, borrow;
for(borrow=i=0; i<MAX; ++i) {
rst[i] = a[i]-b[i]-borrow; // 扣上一次借位
if(rst[i]<0) {
borrow=1, rst[i]+=10; // 需借位
} else {
borrow=0; // 無需借位
}
}
}
乘法
照直式之乘法規則，a[i] * b[j] 最後結果是放到 rst[i+j] 裡面去。
正常是每乘完一次之後，去判斷 rst[i+j] 是否大於 10，如果大於 10 就進行進位調整，但
其實不用這麼麻煩，
只要整個乘法都做完後，再對 rst 做一次性調整就好。
有個細節稍注意，如果 a[i] 為 0 的話，就直接做下一個，節省時間
void big_mul(int *rst, int *a, int *b)
{
int i, j, carry;
memset(rst, 0, sizeof(int)*MAX); // 先清0
for(i=0; i<MAX; ++i) {
if(a[i]==0) continue;
for(j=0; i+j<MAX; ++j)
rst[i+j]+= a[i]*b[j];
}
// 一次性調整
for(carry=i=0; i<MAX; ++i) {
rst[i]+=carry;
carry = rst[i] / 10;
rst[i] %= 10;
}
}
比較大小
比較大小時從最高位開始一位逐一比較，code 當參考，
a>b 傳 + ； a<b 傳 -；a=b 傳 0
int big_compare(int *a, int *b)
{
int i=MAX-1;
while(i>0 && a[i]==b[i]) --i;
return a[i]-b[i];
}
除法
除法很麻煩，同時要做除法前，建議再多做下面幾個函式
void big_addi(int *big, int x); // 大數+正整數
void big_subi(int *big, int x); // 大數-正整數
void big_muli(int *big, int x); // 大數*正整數
void big_divi(int *big, int x); // 大數/正整數
要完成 big_div，big_muli 一定要做，big_divi 看個人有沒有興趣做，
其他的用不用得到不一定，要看個人 code 怎麼寫。
欲求 rst = a/b (整數部份)，一種低效但簡單的方式是，
先將 rst 歸零，之後 a 不停減 b，rst 不停加一，直到 b>a 為止，rst 即為所求。
另一種方式概念，先假設 a=123456， b=345，a 用了 6 位數， b 用了 3位數，
直接先把 b 移成 6 位數，得到移動了 delta= (dig of a) - (dig of b) = 3 位數。
a = 123456 ，b = 345000 [ 商=0，餘=123456 ]，b 右移一個 digit
a = 123456， b = 34500 [ 商=3，餘=19956，b 右移一個 digit，
依此類推下去，直到 delta 變負數為止。以此為概念，整個變化如下。
delta=3, a = 123456，b = 345000
Q = a/b = 0，a = a - Q*b = 123456，
b 除 10 (記憶體右搬1個元素)
rst[delta] = Q ，rst[3]=0。
delta=2, a = 123456，b = 34500 [ans=0]
Q = a/b = 3，a = a - Q*b = 19956，
b 除 10 (記憶體右搬1個元素)
rst[delta] = Q ，rst[2]=3。
delta=1, a = 19956， b = 3450 [ans=3]
Q = a/b = 5，a = a - Q*b = 2706，
b 除10 (記憶體右搬1個元素)
rst[delta] = Q ，rst[1]=5。
delta=0, a = 2706， b = 345 [ans=35]
Q = a/b = 7，a = a - Q*b = 291，
b 除10 (記憶體右搬1個元素)
rst[delta] = Q ，rst[0]=7。
所以最後得到之 ans=357，而 a=291 就是餘數，
驗證一下： 123456 = 345 * 357 + 291，無誤。
可想一下如果是 10^8 除以 1，原本慢慢扣要執行 10^8 次，
但這種方式在外回圈執行 8 次，即使用效率最差的線性查找法找商，
內回圈執行 10 次，差別變成 10^8 與 10*8 次 的差別。
類似的方法不只一種，上面這想法是死 K 算盤本想到的，
而算盤本裡面還有其他三、四種除法演算法 (二進位)，
其中還包含了非回復式除法，有興趣可自行看。
上述下來，要將除法做得像樣，又要有額外幾個副函式
1. 陣列左移
2. 陣列右移
* 3. 大數二分法
陣列左移、陣列右移其中一個可以用 memmove (筆者並沒很喜愛用此指令)，
較習慣全用 for loop 慢慢 assigned；
但問題較大的是二分法的實作，有心想做份好一點的大數，這裡將會是第一個瓶頸難題。
以上，本文敘述乃為第一次接觸大數之網友作入門，提醒的是，本篇只是「引入門」，
實際上的大數並不會用這種架構下去，原因在於效率是所有大數架構裡，
算是差很多的架構。至於其他的大數算法架構，擇日再發。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.126.240.19
※ 文章網址: https://www.ptt.cc/bbs/Diary/M.1496395467.A.E12.html
討論串 (同標題文章)