增加進制位數

 

上篇 [大數] 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.

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()