【演算】大數運算 Part 2

　　決定大數的儲存方式後，接下來要怎麼運算呢？由於全部解釋完實在太佔篇幅，又因為加法與減法其實是一體兩面的(減一個正數就是加一個負數)，讓我們姑且先解釋大數的加減法。


　　大數的加法原理，有點像是一個十進位版的全加器。所有數字的第 n 位相加，再加上第 n - 1 位的進位數，就是答案的第 n 位數字。若有進位，則將此數作為第 n + 1 位加法的輸入。若是減法，則同樣是將所有數字的第 n 位相減。假如此數字差小於零，就跟第 n + 1 位數字"借"數。也就是將此數加 10，並將下一位數減 1 (還記得國小學過的減法定理嗎？)。

　　以上兩種的虛擬碼實作出來大致如下：

void add(large A, large B)
{
    Index i;
    int carry = 0;

    for (i = 1 to maximun(A 的位數, B 的位數))
    {
        int n;

        n = A 的第 i 位 + B 的第 i 位 + carry;
        C 的第 i 位 = n % 10;
        carry = n / 10;
    }

    if (carry != 0)
    {
        C 的第 i 位 = carry;
    }

    print C;
}

void sub(large A, large B)
{
    Index i;
    int borrow = 0;

    for (i = 1 to maximun(A 的位數, B 的位數))
    {
        int n;

        n = A 的第 i 位 - B 的第 i 位 - borrow;
        if (n < 0)
        {
            n = n + 10;
            borrow = 1;
        }
        else
        {
            borrow = 0;
        }

        C 的第 i 位 = n;
    }

    print C;
}

※注意：在這裡，我們一律假設是 A, B ≧ 0。且在 sub() 函式中的 A ≧ B，因此結果並不會出現負數。以下會繼續說明。


　　不同於電腦為了用加法表示減法，把"減一個數字"當成"加一個該數字的負數"。由於我的正負號是交由布林植表示，實際代表數字的向量並不能有負數。為了省去處理負號的麻煩，因此我的作法剛好相反，希望能以"正數之間的相加減"，代表所有情況(不管哪個數是正數、哪個數是負數)的加減法，必要時再改變結果的正負號。

　　以加法為例，我把兩數相加：a + b 分成以下六種情況：



　　同樣的，兩數相減：a + b 也可以分成六種情況：



　　可能有點複雜，不過若仔細看可以發現，我把負數(< 0)的數字全都"正數化"了。並且可以確定，在括號(包含中括號與小括號)中的數字必為正數。

　　這樣做有什麼好處呢？

　　例如加法只要在第二種與最後兩種情況中，我們可以確定結果必定為負數。因此只要出現這種情況，我們只要把算式做適當的轉換(例如在 a, b < 0 的情況下，將 a + b 轉換成 -[(-a) + (-b)])，就可以確定運算過程中，純數字部份(向量儲存的內容)必不會出現負數，並且因為在早已知道正負號的情況，可以直接設定代表正負號的布林變數。

To Be Continued . . .