Edison.X. Blog

增加進制位數

在上篇 [大數] C 語言大數演算法 for beginner 已對大數算法有了初步認知，也曾提到一般 coder 在設計時並不會設計如此，原因在於速度太慢。

一個陣列元素裡面只用了 0~9，10 進制，這數值大小其實用不到 int big[MAX] 方式宣告，只要用 char big[MAX] 就行了，這麼一來也只是省空間，對速度沒助益。

由於 int 可表達範圍約 0~ 2.1 * 10 ^ 9 ，若考慮乘法問題，一個數最大可表示到 sqrt (2.1 * 10^9) 約 65536 左右，只用 10 進位方式實在是太慢了，於是改成「萬」進位，原因為 10000 為最接近 65536 之 10^n 數字。

先提，大數演算法效率如何，一半關鍵因素在於儲存進制之方式。

定義 macro

接下來的版本，建議先全用 #define 方式定義起來。

#define MAX 200 
#define CAP 10000 
#define CLEN 4 
typedef int  btype; 

上面有些定義是有爭議的，特別是 CLEN 部份，這裡定義 CLEN 是為了到時輸出用的，要使得 10^CLEN = CAP，但也有些人認為這到時候再用算的就行了，筆者認為既然常用，那就一次定出來就好。而 typedef 部份未必會做，但通常是做了較佳，因擴充性會較好，因 btype 代表的是該大數陣列要用怎樣的資料型態做儲存。

為了程式碼說明方便，這裡只有 typedef 那裡不採用，並採用的是萬進位 (即 CAP 為 10000)，

也假設主程式裡面宣告為 int a[MAX], b[MAX]; 作為大數之用。

從字串讀取

之前有提過，要從字串轉存成大數時，必須從後面開始存起，在萬進位也一樣，考慮 char str[] = "12345" 時，

big[1] = 1，big[0] = 2345。

一樣都是從最後面讀出來，只是多了一個 pwr 做累計，每次都乘 10 ，乘到 CAP 時就回到 1。

void big_read(int *big, const char* str)
{
    int len = strlen(str);
    int i, j, pwr;

    memset(big, 0, MAX*sizeof(big[0]));
    for(j=0, i=len-1; i>=0; ++j)
        for(pwr=1; pwr!=CAP && i>=0; pwr*=10, --i)
            big[j]+=(str[i]-'0')*pwr;
}

顯示

考慮大數為 big[2]=1, big[1]=2, big[2]=3，它所代表的不是 123，而是 100020003。

一開始先去前導 0 ，找到第一個非零之元素，直接輸出；之後的元素全都以  0 填滿其 CLEN 長度。

void big_print(int *big)
{
    int i=MAX-1;
    while(i>=0 && big[i--]==0);
    ++i;
    printf("%d", big[i--]);
    while(i>=0) 
        printf("%0*d", CLEN, big[i--]);
}

加法

仿直接加法沒什麼兩樣，只是把 10 進位換成 CAP 進位而已。

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] / CAP;
        rst[i]%=CAP;
    }
}

減法

仿直接減法，繼續把 10 進位換成 CAP 進位。

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]+=CAP; // 需借位
        } else {
            borrow=0; // 無需借位
        }
    }
}

乘法

這裡再提一下一次進位要注意的地方。

上篇 [大數] C 語言大數演算法 for beginner  裡面，筆者用的是一次進位法則，

可以那麼用是因為原本是 10 進位，要在同一個 rst[i+j] 擠到爆的可能性非常小

(可以推，有興趣可自己推)，但這次已經是用萬進制，若最後 rst[i+j] 是

(9999 * 9999) 累加起來，可容許  rst[i+j]  = a[i] * b[j] 約有 20 次這種情況，

超過這次數的話，到時若不先進位，結果肯定會爆。解決方式有兩種，

一種是將原本的萬進制，調成千進制；另一種是放棄一次進位，直接改逐次進位。

這裡程式碼乃以一次進位為主。

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] / CAP;
        rst[i] %= CAP;
    }
}

比較

觀念參考  上篇 [大數] C 語言大數演算法 for beginner   

這部份一模一樣 (愈寫愈心虛，一直參考上一篇)

int big_compare(int *a, int *b)
{
    int i=MAX-1;
    while(i>0 && a[i]==b[i]) --i;
    return a[i]-b[i];
}

除法

除法關鍵和 上篇 [大數] C 語言大數演算法 for beginner  一樣，

關鍵都在 implement 大數二分法。求單一商數時，

10 進制裡最大差別是 4/10；而萬進制裡最大差別變成了 13 / 10000；

這裡應看出效果到底差在哪了。Implement 等有時間補上。

另，取模運算，實際就是除法運算，只是最後傳回值是餘數不是商數。

其他改善

截至目前為止，以 10^n 進制而言，所有提過的地方有個地方可改善 - 紀錄使用元素個數

假設 rst = a* b，其中 a 佔 n1 位數，b 佔 n2 位數，n = max(n1, n2)，

得到 rst 結果為 x 位數，若增加一數值，紀錄目前這個大數已用了多少元素，

則速度會再快！可應用以下特性

(1) 加法最多只需執行 n 次，x 最大值為 n+1

(2) 減法最多只需執行 n 次，x 最大值為 n

(3) 乘法最多只需執行 min (2n, MAX) 次，x 最大值為 min (2n+1, MAX)

(4) 除法最多只需執行 n 次，x 最大值為 n

(5) 比較 a, b 大小，就直接從 n1, n2 開始比較

(6) 做輸出時直接從 n1 / n2 / n 開始輸出，節省去前導 0 之動作。

(7) size==0 && rst[0]==0 ，可判斷 0；同樣也可判斷 1。

      如此對乘法速度有所幫助，也可防除零問題。

上面 (1) ~ (4) 這些位數關係要推導我懶 (會推，但懶得推)，

不過用「觀查法」就可得到結論，考慮 10 進位模式，對於各運算考慮

9999 (+-*/ ) 9999

9999 (+-*/ ) 1

1 (+-*/ ) 9999

1 (+-*/ ) 1

之四種特例，應不難觀查出結果。

同時，這目前還不是我所知最好的架構，找時間再發一篇 for binary.