【演算】大數運算 Part 4

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


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

　　我的作法是，先將 B 乘以 10^{n - 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.