5月 01, 2008

【演算】大數運算 Part 4

@
  介紹完加法、減法、乘法之後,最後就是除法了。當初要作加減法時,我都可以在短時間內迅速構思、完成。作乘法時雖然碰上了 9 位相乘就會當掉的問題,不過也沒花上太多時間就解決了。到最後,最令我苦惱(或許是我頭腦不太靈光?)該怎麼實現的,就是除法了。


  除法該怎麼實現呢?首先,我們應該要知道的是,因為是整數除法的關係,所以相除結果亦是整數,小數點的部份會無條件捨去。因此以下解釋 A / B 時,皆是 A ≧ B 的情況(若 A < B 則結果必為 0)。

  我的作法是,先將 B 乘以 10n - m。再使用迴圈,找出一個數字 i 符合 B * i ≦ A < B * (i + 1)。此時的這個 i 就是商的第 n - m + 1 位數字。之後,我們再將 A 減去 B * i,並將 B 除以 10,並重複以上動作,即可得到商的第 n - m 位數字 。接著再重複一次以上的動作......。直到求出商的第 1 位數字為止。而這些運算所得的各位數字,就是我們需要求得的答案。

  不太瞭?看看下圖:



  熟悉吧!這個是長除法。我剛剛說明的拉裡拉扎一大串,其實就是長除法形式的實現。為了給大家一點思考時間(也給我一點偷懶空間),在這裡我不解釋,請自行把我上面的文字,對照到實際的長除法上,你就會發現兩者間的共通性。假如有不懂的部份可以提出來。


  以下是實現除法運算的程式虛擬碼:

void div(large A, large B)
{
    Index i, j;

    B = B * 10 ^ (A 的位數 - B 的位數 + 1);
    for (i = A 的位數 - B 的位數 + 1 to 1)
    {
        for (j = 1 to 10)
        {
            if (B * j > A)
            {
                A = A - B * (j - 1);
                break;
            }
        }

        C 的第 i 位 = j mod 10;

        B = B / 10;
    }

    print C;
}

※注意:以上虛擬碼的「^」符號代表的是「次方」的意思。

  做一個小小的總結。費了幾天時間,把我自己實作大數運算的大致想法打出來。假如有哪裡不太好懂,我為我拙劣的文字表達致歉。並請把不懂的地方隨時提出來,好讓我知道有哪裡可以加以改進。

  以上公佈的這些都只是我個人的實現法而已,並沒有什麼統一的寫法。或許我的方法有某些優點,或是某些缺失。重點是該如何學習別人的想法,並與自己的想法結合,寫出屬於自己的程式。你也可以有你自己的方法,提出你的意見,我們可以討論討論!

  對於四則運算以外的內容,像是標準輸出、標準輸入、與邏輯運算等,我想暫時是不會把這些實現想法貼出來了。這部份就請各位自行去挖掘囉。

  至於我自己寫出來的結果,已經張貼在這篇文章裡了,有興趣的人歡迎使用看看。

The End.

2 回覆:

匿名 提到...

那個10次方應該會拖慢了很多

Unknown 提到...

well, 理論上您說的沒錯
不過由於目前我的大數是利用string型態儲存
所以其實"乘以10的n次方"只是在結尾補零罷了
我想應該不會拖慢太多效率才是?

張貼留言