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

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

 

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

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

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

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


留言列表 (1)

發表留言
  • 俊騫 黃
  • 請問「從字串讀取」的部份, big[i] = str[i] - '0'; 這一行程式碼是不是寫錯了?看起來 big 跟 str 存數字的順序並不會相反。我想應該要改成 big[len - i - 1] = str[i] - '0'; 請問對嗎?
  • 您說對了,這部份原本程式碼沒做到處理,已修改,謝謝指正。

    edisonx 於 2012/10/18 03:16 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼

【 X 關閉 】

【PIXNET 痞客邦】國外旅遊調查
您是我們挑選到的讀者!

填完問卷將有機會獲得心動好禮哦(注意:關閉此視窗將不再出現)

立即填寫取消