Edison.X. Blog

大數問題我認為是新手必練題型之一，但實在沒時間去 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；

但問題較大的是二分法的實作，有心想做份好一點的大數，這裡將會是第一個瓶頸難題。

以上，本文敘述乃為第一次接觸大數之網友作入門，提醒的是，本篇只是「引入門」，

實際上的大數並不會用這種架構下去，原因在於效率是所有大數架構裡，

算是差很多的架構。至於其他的大數算法架構，擇日再發。