4月 30, 2008

【演算】大數運算 Part 3

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


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

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

  讓我們整理一下,設 A, B, C 的第 i 位分別為 ai, bi, ci,就可以得出以下公式:




  最後還有個問題,若是 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 . . .

4 回覆:

匿名 提到...

用了2次for應該會拖慢很多

小參 提到...

關於這點, 其實我也不曉得該如何在效率上做優化
請問您有什麼建議能夠提供嗎?

謝謝您的回應:)

CxxlMan 提到...

99999 * 999 = 99899001
仍然是 8 位數

C.E.W. 提到...

原來我把 10000 * 100 跟 99999 * 999 乘出的結果都多算了一個位數,感謝你的指正:)

張貼留言