算法與數據結構——大整數的乘法

大整數的乘法

問題描述

參考解答

設X和Y都是n位的二進制整數，現在要計算它們的乘積XY。我們可以用小學所學的方法來設計一個計算乘積XY的算法，但是這樣做計算步驟太多，顯得效率較低。如果將每2個1位數的乘法或加法看作一步運算，那麼這種方法要作O(n²)步運算才能求出乘積XY。下面我們用分治法來設計一個更有效的大整數乘積算法。

　

圖6-3 大整數X和Y的分段　

我們將n位的二進制整數X和Y各分為2段，每段的長為n/2位(為簡單起見，假設n是2的冪)，如圖6-3所示。

由此，X=A2^n/2+B ，Y=C2^n/2+D。這樣，X和Y的乘積為：

XY=(A2^n/2+B)(C2^n/2+D)=AC2ⁿ+(AD+CB)2^n/2+BD (1)

如果按式(1)計算XY，則我們必須進行4次n/2位整數的乘法(AC，AD，BC和BD)，
以及3次不超過n位的整數加法(分別對應於式(1)中的加號)，此外還要做2次移位(分別對應於式(1)中乘2ⁿ和乘2^n/2)。所有這些加法和移位共用O(n)步運算。設T(n)是2個n位整數相乘所需的運算總數，則由式(1)，我們有:

(2)

由此可得T(n)=O(n²)。因此，用(1)式來計算X和Y的乘積並不比小學生的方法更有效。要想改進算法的計算複雜性，必須減少乘法次數。為此我們把XY寫成另一種形式:

XY=AC2ⁿ+[(A-B)(D-C)+AC+BD]2^n/2+BD (3)

雖然，式(3)看起來比式(1)複雜些，但它僅需做3次n/2位整數的乘法(AC，BD和(A-B)(D-C))，6次加、減法和2次移位。由此可得:

(4)

用解遞歸方程的套用公式法馬上可得其解為T(n)=O(n^log3)=O(n^1.59)。利用式(3)，並考慮到X和Y的符號對結果的影響，我們給出大整數相乘的完整算法MULT如下:

function MULT(X，Y，n); {X和Y為2個小於2n的整數，返回結果為X和Y的乘積XY}
begin
S:=SIGN(X)*SIGN(Y); {S為X和Y的符號乘積}
X:=ABS(X);
Y:=ABS(Y); {X和Y分別取絕對值}
if n=1 then
   if (X=1)and(Y=1) then return(S)
                    else return(0)
       else begin
              A:=X的左邊n/2位;
              B:=X的右邊n/2位;
              C:=Y的左邊n/2位;
              D:=Y的右邊n/2位;
              ml:=MULT(A,C,n/2);
              m2:=MULT(A-B,D-C,n/2);
              m3:=MULT(B,D,n/2);
              S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
              return(S);
            end;
end;

上述二進制大整數乘法同樣可應用於十進制大整數的乘法以提高乘法的效率減少乘法次數。下面的例子演示了算法的計算過程。

設X=314l,Y=5327，用上述算法計算XY的計算過程可列表如下，其中帶^'號的數值是在計算完成AC，BD，和(A-B)(D-C)之後才填入的。

---

X=3141 A=31 B=41 A-B=-10

Y=5327 C=53 D=27 D-C=-26

AC=(1643)^'

BD=(1107)^'

(A-B)(D-C)=(260)^'

XY=(1643)^'10⁴+[(1643)^'+(260)^'+(1107)^']10²+(1107)^'

=(16732107)^'

---

A=31 A₁=3 B₁=1 A₁-B₁=2

C=53 C₁=5 D₁=3 D₁-C₁=-2

A₁C₁=15 B₁D₁=3 (A₁-B₁)(D₁-C₁)=-4

AC=1500+(15+3-4)10+3=1643

---

B=41 A₂=4 B₂=1 A₂-B₂=3

D=27 C₂=2 D₂=7 D₂-C₂=5

A₂C₂=8 B₂D₂=7 (A₂-B₂)(D₂-C₂)=15

BD=800+(8+7+15)10+7=1107

---

|A-B|=10 A₃=1 B₃=0 A₃-B₃=1

|D-C|=26 C₃=2 D₃=6 D₃-C₃=4

A₃C₃=2 B₃D₃=0 (A₃-B₃)(D₃-C₃)=4

(A-B)(D-C)=200+(2+0+4)10+0=260

---

如果將一個大整數分成3段或4段做乘法，計算複雜性會發生會麼變化呢?是否優於分成2段做的乘法？這個問題請大家自己考慮。