乘法算法

**乘法算法**是計算兩個數值相乘乘積的算法。為了提高運算效率，不同大小的數字適用不同的乘法算法。自十進位數字系統誕生以來，就已開始發展乘法算法。

## 網格法

網格法 （或盒式法）是一種用於給小學生進行乘法計算啟蒙的簡單乘法算法。自 1990 年代後期以來，它一直是英格蘭和威爾斯公立小學數學課程的標準部分。

將兩個乘數分解（「劃分」）為百位、十位或個位的部分，然後在相對簡單的乘法步驟中直接算出這些部分的乘積，再將其一一相加以算出最終結果。用這種方法計算 $34\times 13$ ，可以畫出如下網格：

　
:

最後再通過一次求和或逐行累加得到結果（見右），實質是計算了 $(300+40)+(90+12)=340+102=442$ 。

這種計算方法（儘管不一定顯式地用網格排列乘數）也稱為「部分乘積算法」。它的本質是分別計算簡單的個位乘法，所有加法都留到最後的「加總」階段。

儘管隨著位數的增加，伴隨的中間過程越來越繁瑣，但網格方法原則上可以應用於任何大小的乘數。一般認為此方式是引入多位乘法概念時，有用的顯式方法，而在當今利用計算器或電子表格就能完成大多數計算的時代，它可能是某些學生唯一需要的乘法算法。

## 長乘法

位值制數字系統在人類社會的壟斷性地位，使得**長乘法**成為最自然的乘法算法，世界各地的學校都會教學生使用這種算法完成日常的乘法計算。其內容是：將一個乘數乘以另一個乘數的每位數字，然後將所有數字按照適當的位置相加得出結果。這需要預先記住所有個位數字兩兩相乘後的結果，即華人世界常見的乘法表。長乘法又被稱為**教科書乘法**或**標準乘法**。

若在十進制下，人工計算較大的數字加乘，長乘法是常見的算法。電腦在二進制下，也有類似的算法「移位和相加」，不少現代的處理器已設計最佳化的乘法線路，以進行快速的乘法計算，但其代價是硬體會變的更加複雜。若是在紙上計算長乘法，會先將所有數字寫下，然後相加，若是使用珠算，會在計算完每一個乘積後，直接和已計算的和加總。

### 示例

此例用長乘法計算 23,958,233（被乘數）乘以 5,830（乘數），結果是 139,676,498,390（積）。

```
        23958233
  ×         5830
  ———————————————
        00000000 ( =      23,958,233 ×     0)
       71874699  ( =      23,958,233 ×    30)
     191665864   ( =      23,958,233 ×   800)
  + 119791165    ( =      23,958,233 × 5,000)
  ———————————————
    139676498390 ( = 139,676,498,390        )
```

以下的虛擬碼描述上述乘法的步驟。此作法會持續的更新乘積，在乘完所有數字後，乘積即為結果。其中 += 運算子用來表示將某變數原有的值加上其他的值，再存回該變數中（類似在 Java 及 C 語言中的用法），以讓程式緊湊。

### 優化空間複雜度

假設在基數為 $D$ ，令 $n$ 為兩個輸入數字位數長度的總和，若其結果需保存在存儲器中，則其空間複雜度通常為 $\Theta (n)$ 。然而在某些應用中，不需要把整個結果保存在內存中，而可以在計算時將數字以字元流的方式輸出（例如輸出到系統終端或文件中）。在這些情況下，長乘法的優勢在於可以將其輕鬆表示為對數空間算法 —— 也就是說，只需要一個工作空間與輸入中位數的對數成正比的算法（ $\Theta (\log n)$ ），這是乘數之積的雙重對數（ $\log \log N$ ）。注意，乘數本身仍保留在內存中，並且在此分析中忽略其 $\Theta (n)$ 的空間。

只要知道之前乘積產生的進位，就可以由最低位起，一位一位的計算乘積的每一位數字，這是優化空間複雜度的關鍵。令 _a_i 和 _b_i 分別是被乘數及乘數的第 _i_ 位數字，_a_ 和 _b_ 的最高位都已補 0，補到 _n_ 位數，而 _r_i 是乘積的第 _i_ 位，而 _c_i 是計算 _r_i 後產生的進位（i=1 表示是個位），則

　
: ${\begin{aligned}r_{i}&=\left(c_{i-1}+\sum _{j+k=i+1}a_{j}b_{k}\right)\mod D\\c_{i}&=\left\lfloor (c_{i-1}+\sum _{j+k=i}a_{j}b_{k})/D\right\rfloor \\c_{0}&=0\end{aligned}}$

or

　
: $c_{i}=\left(\sum _{m=0}^{i-2}\sum _{j+k=i-m}a_{j}b_{k}\right)/D.$

簡單的推論可以證明進位不會超過 _n_，_r_i 的總和不會超過 _D_ \* _n_：第一欄的進位是 0，其他欄最多有 _n_ 個數字，最多也只會從前一欄進位 _n_。總和最多是 _D_ \* _n_，進位到下一位的最多是 _D_ \* _n_ / _D_ 或 _n_。因此這些數字都可以用 O (log _n_) 位數儲存。

偽代碼下的對數空間演算法為

### 在計算機中的用法

有些集成電路會實現乘法，可能是用硬體或是微程序，可能針對各種整數及浮點數。在高精度計算中，在乘比較小的數字時，用底數為 2w 的長乘法，其中 _w_ 為字元的位元數。

若要用此方式乘二個 _n_ 位數數字，約需要 _n_2 次的運算。若用比較型式的方式表示，用數字位數這個自然的數字大小度量，用長乘法乘二個 _n_ 位數數字的時間複雜度是 Θ(_n_2)。

若要用軟體實現，長乘法演算法需要處理在加法時會出現的溢位問題，可能會很耗成本。典型的作法是用比較小的基底來進行運算，例如 _b_，而讓 8_b_ 為機器中表示的整數大小。這樣可以進行幾次運算之後才會溢位。若數字太大，可以只加數字的一部份到結果中，或是進位，將剩下的數字映射為一個小於 _b_ 的較小數字。此作法稱為「正規化」。Richard Brent 有在其 Fortran 軟體包 MP 中使用此一作法。

## 格子乘法

格子乘法在演算法上和長乘法等效。需要在紙上劃格子，以引導計算，並且將乘法和加法分為二個步驟進行。這是在 1202 年在斐波那契的《計算書》中引進到歐洲。斐波那契用此方式心算，用左手和右手處理計算的中間值。16 世紀的馬特拉克・那西在《Umdet-ul Hisab》書籍上列出了此演算法六種不同的變體。在奧斯曼帝國的恩德倫學校中，廣為使用此一演算法。納皮爾的骨頭（Napier's bones）或稱為納皮爾算籌（Napier's rods）也是用此方式，是約翰・納皮爾過世的 1617 年發表。

如圖所示，被乘數和乘數寫在格子的上方和右邊，此方法在花拉子米的《算數》（Arithmetic）書中有提到，這是斐波那契的來源之一，曾被 Sigler 在 2002 年的《Fibonacci's Liber Abaci》中提到。

* 在乘法階段，格子中會填上其對應行和列上所寫，被乘數和乘數的位數相乘後的二位數乘積：格子中左上方的三角形會列十位數字，格子中右下方的三角形會列個位數字。
* 在加法階段，會延著斜線將數字相加，將相加後的個位數寫在格子的最下方，對應斜線，若有進位，將進位寫在下一個斜線區域格子的右方或上方。
* 下方的數字即為兩數字相乘的積。

### 示例

考慮以下較複雜的計算，考慮 23,958,233 乘以 5,830，結果是 139,676,498,390。不過以下計算中，其中的 23,958,233 是寫在格子的上方，5,830 寫在右方。將乘積寫在格子的二個三角形中，將和寫在左邊和下方。結果條列如下：

## 二進制或農夫演算法

農夫演算法是廣為在農民中使用的算法，其中不需要像長乘法一樣記憶乘法表。此演算法曾在古埃及使用，農夫演算法的優點是可以快速教授、不需要記憶、若沒有紙筆的話，也可以用其他東西輔助計算（例如籌碼），缺點是步驟比長除法要長，在計算大數字的乘法時不方便，

### 說明

在紙上，寫下被乘數，被乘數的下方寫下被乘數反覆除二（且無條件捨去小數）的結果，被乘數的旁邊寫下乘數，乘數下方寫上乘數反覆乘二的結果。一直到被乘數那一欄為 1 為止。將乘數那一欄的數字相加，但若被乘數那一欄為偶數，跳過此數字不累加，所得結果即為乘積。

### 示例

以下用農夫演算法計算 11 乘以 3 。

```
十進制:     二進制:
11   3       1011  11
5    6       101  110
2   ~~12~~       10  ~~1100~~
1   24       1  11000
    ——         ——————
    33         100001
```

說明上述的步驟：

* 二欄的最上方分別是 11 和 3。
* 11 除以 2（5.5）無條件捨去，變成 5，3 乘以 2（6）。
* 5 除以 2（2.5）無條件捨去，變成 2，6 乘以 2（12），這一行的最左邊（2）是偶數，因此 12 要劃掉，不能累加到乘積中。
* 2 除以 2（1），12 乘以 2（24）
* 將沒有劃掉的數字相加：3 + 6 + 24 = 33.

此作法有效的原因是因為乘法滿足分配律，因此：

　
: ${\begin{aligned}3\times 11&=3\times (1\times 2^{0}+1\times 2^{1}+0\times 2^{2}+1\times 2^{3})\\&=3\times (1+2+8)\\&=3+6+24\\&=33.\end{aligned}}$

以下是一個複雜的例子，仍用之前用過的範例（23,958,233 and 5,830）：

```
Decimal:             Binary:
5830  ~~23958233~~       1011011000110  ~~1011011011001001011011001~~
2915  47916466       101101100011  10110110110010010110110010
1457  95832932       10110110001  101101101100100101101100100
728  ~~191665864~~       1011011000  ~~1011011011001001011011001000~~
364  ~~383331728~~       101101100  ~~10110110110010010110110010000~~
182  ~~766663456~~       10110110  ~~101101101100100101101100100000~~
91  1533326912       1011011  1011011011001001011011001000000
45  3066653824       101101  10110110110010010110110010000000
22  ~~6133307648~~       10110  ~~101101101100100101101100100000000~~
11 12266615296       1011  1011011011001001011011001000000000
5  24533230592       101  10110110110010010110110010000000000
2  ~~49066461184~~       10  ~~101101101100100101101100100000000000~~
1  98132922368       1  1011011011001001011011001000000000000
  ————————————          1022143253354344244353353243222210110 （進位前）
  139676498390         10000010000101010111100011100111010110
```

## 電腦中的二進制乘法

這是農夫演算法的變體。

二進制下，長乘法會變成很簡單的處理，針對每一個被乘數位數的 1，將乘數往左位移適當的位元數，將乘數各次位移的結果相加，即為乘積。在一些中央處理器中，加法和位移的速度會比乘法要快，尤其被乘數不大，或是幾乎是定值的情形。

## 移位和相加

以往的電腦會用「移位和相加」的乘法來計算小整數的乘法。二進制的長乘法和農夫演算法都可以簡化到相同的演算法。
在二進制下，將數字和二進制的一個位元相乘，可以簡化為各位元的邏輯與運算。會將算出來的部份和相加。，大部份目前的微處理器都會以此方式或是其他類似方式（例如布斯乘法算法）實現不同整數以及浮點長度的乘法，，可能是用乘法器中或是微程序。

目前的處理器，位元的移位運算會比乘法要快很多，因此可以用往左移位代替乘以 2 的次冪。乘以常數的乘法也可以用一連串的移位和加減法來代替。例如，以下是只有移位及相加來表示乘以 10 的演算法。

```
((x << 2) + x) << 1 # 此處是用 (x*2^2 + x)*2 來計算 10*x
(x << 3) + (x << 1) # 此處是用 x*2^3 + x*2 來計算 10*x
```

有時的移位和加減法的組合會比硬體乘法器還快。

若電腦沒有乘法的運算，需要用上述方式來進行計算，若將向左移位表示為相同的數加二次（兩者在邏輯上等價），也可以延伸到浮點數。

## 平方的四分之一乘法

可以用平方的算式，計算二個數的乘積，有些來源的算式中會包括取整函數，此方式源自於巴比倫數學（西元前 2000-1600 年）。

　
: $\left\lfloor {\frac {\left(x+y\right)^{2}}{4}}\right\rfloor -\left\lfloor {\frac {\left(x-y\right)^{2}}{4}}\right\rfloor ={\frac {1}{4}}\left(\left(x^{2}+2xy+y^{2}\right)-\left(x^{2}-2xy+y^{2}\right)\right)={\frac {1}{4}}\left(4xy\right)=xy.$

_x_ 和 _y_ 為整數，若 _x_+_y_ 和 _x_−_y_ 中有一個為奇數，另一個也一定會是奇數，因此上式中若有一項在取整數之前有分數，另一項也會有，兩者會相消，不會影響所得的結果。以下是從 0 到 18 計算平方的四分之一取整數的對照表，可以計算 9×9 以內的乘法：

若要計算 9 乘 3，其和以及差分別是 12 以及 6，根據上式可得 36 和 9，兩者的差是 27，這就是 9 乘 3 的乘積。

Antoine Voisin 在 1817 年有出版一個平方的四分之一的表，從 1 列到 1000，可以幫助乘法的運算。Samuel Laundy 在 1856 年有出版過 1 到 100000 的表，Joseph Blater 在 1888 年出版了 1 到 200000 的表。

平方的四分之一乘法曾用在模擬計算機上，以形成二訊號相乘的模擬信號。二個輸入電壓的和或差可以用運算放大器達到。電壓平方可以用分段線性電路達成。最後二個平方的四分之一以及兩電壓的差以及再用運算放大器實現。

Everett L. Johnson 在 1980 年時提出將此方式應用在數碼乘法器中。為了產生 8 位元整數的乘積，數位裝置計算兩數的和以及差，查表計算平方，計算差值，再往右移位二個位元。

平方的四分之一乘法對 8 位元的系統有益，可以在沒有硬體乘法器的情形下實現乘法。Charles Putney 有將此演算法實現在 MOS 6502 中。

## 複數乘法演算法

複數乘法包括四個實數乘法以及二個加法。

　
: $(a+bi)(c+di)=(ac-bd)+(bc+ad)i.$

或

　
: ${\begin{array}{c|c|c}\times &a&bi\\\hline c&ac&bci\\\hline di&adi&-bd\end{array}}$

不過有辦法將實數乘法由四個減少到三個

乘積 (_a_ + _bi_) · (_c_ + _di_) 可以用以下方式計算。

　
: _k_1 = _c_ · (_a_ + _b_)

　
: _k_2 = _a_ · (_d_ − _c_)

　
: _k_3 = _b_ · (_c_ + _d_)

　
: 實部 = _k_1 − _k_3

　
: 虛部 = _k_1 + _k_2.

此演算法只用了三個乘法，比原來的四個乘法少一個，但加減法由原來的二個增加到五個。假如乘法的成本遠大於計算加減法的成本，此演算法的速度會比原來的演算法快。在現代先進的電腦上，乘法和加法花的時間可能相同，那麼此演算法就沒有速度上的優勢。若使用浮點數計算，此演算法可能會有精準度下降的問題，因此需要取捨。

在 FFT（或是其他的線性映射），若是乘以固定係數（_c_ + _di_，在 FFT 中稱為旋轉因子）的複數乘法，其中二個加法（_d_−_c_ 和 _c_+_d_）可以事先計算，需要即時計算只剩三個乘法以及三個加法。不過若是配合有浮點運算器的處理器，加法的速度和乘法相當，因此減少乘法，增加加減法的演算法，沒有速度上的優勢。

## 大數字的快速乘法演算法

### Karatsuba 乘法

若需要計算到上千位數字相乘的系統，例如計算機代數系統或高精度計算函式庫，長乘法的速度太慢。因此會使用 Karatsuba 算法，此乘法演算法是 Anatoly Karatsuba 在 1960 年發現的，在 1962 年出版。此乘法演算法的精神在於觀察到二位數的乘法可以不用傳統四個乘法的作法，可以只用三個乘法完成。這是分治法的例子。假設要將二個二位數 _m_ 進位數字 _x_1 _m + x_2 和 _y_1 _m + y_2 相乘：

1. 計算 _x_1 · _y_1，稱此結果是 _F_
2. 計算 _x_2 · _y_2，稱此結果是 _G_
3. 計算 (_x_1 + _x_2) · (_y_1 + _y_2)，稱此結果是 _H_
4. 計算 _H_ − _F_ − _G_，稱此結果是 _K_，此數字等於 _x_1 · _y_2 + _x_2 · _y_1
5. 計算 _F_ · _m_2 + _K_ · _m_ + _G_.

若要計算三個 _m_ 進位數字的乘積，又可以用上述的技巧，使用遞歸的方式進行（但需要改為其他的進位），此方式。只要計算出乘積數字，再將數字相加，需要 _n_ 個步驟。

Karatsuba 算法的時間複雜度是 O (_n_log23) ≈ O(_n_1.585)，此方式明顯的比長乘法要快。因為遞歸產生的額外計算，若 _n_ 較小時，Karatsuba 算法會比長乘法慢，因此在 _n_ 較小時，會切換回長乘法進行計算。

Karatsuba 算法是第一個時間複雜度漸進的比長乘法快的演算法，也可以視為是快速乘法理論的基礎。

1963 年時，Peter Ungar 建議將 _m_ 改為 _i_，以產生快速複數乘法的演算法。若要計算 (_a_ + _b i_) · (_c_ + _d i_)，可依以下步驟進行：

1. 計算 _b_ · _d_，稱結果為 _F_
2. 計算 _a_ · _c_，稱結果為 _G_
3. 計算 (_a_ + _b_) · (_c_ + _d_)，稱結果為 _H_
4. 結果的實部是 _K_ = _H_ − _F_ − _G_ = _a_ · _d_ + _b_ · _c_
5. 結果的虛部是 _G_ − _F_ = _a_ · _c_ − _b_ · _d_

如同上述複數乘法演算法所述的一樣，需要三個乘法以及五個加減法。

### Toom-Cook 算法

另一種乘法的演算法是 Toom-Cook 算法，或稱為 Toom-3 算法。Toom-Cook 算法將每一個要相乘的數字切成幾部份，是 Karatsuba 算法的推廣。三路的 Toom-Cook 演算法可以針對大小為 $3N$ 的被乘數和乘數進行乘法，其成本是大小為 $N$ 的被乘數和乘數乘法的 5 倍，因為運算加速的係數是 $9/5$ ，Karatsuba 算法的加速係數是 $4/3$ 。

若用遞迴的方式將數字分成更多份，可以再縮減計算時間，但位數管理以及加法的成本也會增加。若位數到上千位數，一般會使用傅立葉轉換，速度多半會比較快，若位數更多，傅立葉轉換的優勢更加明顯。

### 傅立葉變換法

Strassen（1968 年）曾提出用快速多項式乘法來計算快速整數乘法的基本概念。後來在 1971 年由 Strassen 和 Schönhage 找到理論和實務的確認，所得的就是 Schönhage-Strassen 演算法。

## 下限

若用單一處理器將二個 _n_ 進位的數字相乘，時間複雜度有一個 trivial 的下界 Ω(_n_) ，沒有更接近實際應用的下界。乘法在 AC0[_p_]以外（_p_ 為任意整數），意思是不存在固定深度，多項式（甚至是次指數）大小，以 AND、OR、NOT、MODp 電路組合成的電路可以計算乘法。。

## 多項式乘法

上述的乘法演算法也可以用來計算多項式的乘法。例如 Strassen 演算法就可以用來計算多項式的乘積。而 Kronecker 替代也可以將多項式的乘法轉換為二個整數的乘法。

以下是用長乘法來計算多項式乘法的例子：

```
 14ac - 3ab + 2 乘以 ac - ab + 1
```

```
 14ac  -3ab   2
   ac   -ab   1
 ————————————————————
 14a2c2  -3a2bc   2ac
        -14a2bc         3 a2b2  -2ab
                 14ac           -3ab   2
 ———————————————————————————————————————
 14a2c2 -17a2bc   16ac  3a2b2    -5ab  +2
 =======================================
```

## 相關條目

* 乘法器
* 除法器
* 對數
* 心算
* 積化和差
* 計算尺
* 特拉亨伯格速算系統
* 秦九韶算法，計算多項式的演算法
* Dadda 乘法器
* Wallace 樹

## 參考資料

## 延伸閱讀

* Warren Jr., Henry S. Hacker's Delight 2. Addison Wesley - Pearson Education, Inc. 2013. ISBN 978-0-321-84268-8.
* Savard, John J. G. Advanced Arithmetic Techniques. quadibloc. 2018 [2006] [2018-07-16]. （原始內容存檔於 2018-07-03）.

## 外部連結

### 基本運算

* The Many Ways of Arithmetic in UCSMP Everyday Mathematics （頁面存檔備份，存於網際網路檔案館）
* A Powerpoint presentation about ancient mathematics （頁面存檔備份，存於網際網路檔案館）
* Lattice Multiplication Flash Video （頁面存檔備份，存於網際網路檔案館）

### 進階演算法

* Multiplication Algorithms used by GMP （頁面存檔備份，存於網際網路檔案館）