【演算】大數運算 Part 3

　　緊接著加法與減法之後，讓我們來看看，該怎麼做大數乘法的運算。


　　一開始實作乘法運算時，我使用的是最直觀的想法：假設要求出 A * B 之值，則先將 A 乘以 B 的第一位，再加上 A 乘以 B 的第二位乘以 10，再加上 A 乘以 B 的第三位乘以 10²，......，再加上 A 乘以 B 的第 n 位乘以 10^n-1。然後實際執行測試時，兩個整數只要超過九位數程式就跑不動了！

　　該怎麼辦呢？顯然我們必須將演算原理作必要的簡化。仔細再將這個方法分析一下，可以發現：若假設 A * B = C，則 C 的第一位會等於 A 的第一位乘以 B 的第一位；C 的第二位會等於 A 的第一位乘以 B 的第二位加上 A 的第二位乘以 B 的第一位；C 的第三位會等於 A 的第一位乘以 B 的第三位加上 A 的第二位乘以 B 的第二位加上 A 的第三位乘以 B 的第一位，......。

　　讓我們整理一下，設 A, B, C 的第 i 位分別為 a_i, b_i, c_i，就可以得出以下公式：




　　最後還有個問題，若是 n 位的 A 與 m 位的 B 相乘之後所得的 C 總共有幾位？最簡單的方法，就是兩者的最小可能值與最大可能值。C的位數就會落在 A 的最小可能值與 B 的最小可能值相乘的位數，和 A 的最大可能值與 B 的最大可能值相乘的位數之間。

　　有點抽象？我們舉個例：若 A 有 5 位，B 有 3 位，則 A 的最小可能值為 10000，B 的最小可能值為 100，兩者相乘為 7 位；A 的最大可能值為 99999，B 的最大可能值為 999，兩者相乘為 8 位。所以可以得知 C 會落在 7 到 8 位之間。

　　多做幾次試驗，就可以發現：n 位的 A 與 m 位的 B 相乘之後所得的 C，其位數會介於 n + m - 1 到 n + m 之間。


　　整個乘法原理就差不多這樣了。其實作的虛擬碼大致如下：

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

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

        for (j = 1 to i)
        {
            n = n + A 的第 j 位 * B 的第 i + 1 - j 位;
        }

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

    while (carry != 0)
    {
        C 的第 i 位 = carry % 10;

        carry = carry / 10;
        i = i + 1;
    }

    print C;
}

To Be Continued . . .