|
乘法算法乘法算法是计算两个数值相乘乘積的算法。为了提高运算效率，不同大小的数字适用不同的乘法算法。自十进制数字系统诞生以来，就已开始发展乘法算法。 网格法网格法 （或盒式法）是一种用于给小学生进行乘法计算启蒙的简单乘法算法。自1990年代后期以来，它一直是英格兰和威尔士公立小学数学课程的标准部分[1]。 将两个乘数分解（“划分”）为百位、十位或个位的部分，然后在相对简单的乘法步骤中直接算出这些部分的乘积，再将其一一相加以算出最终结果。用这种方法计算 ，可以画出如下网格： 300 40 90 + 12 ———— 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語言中的用法），以讓程式緊湊。 multiply(a[1..p], b[1..q], base) // index 1對應數字的個位數
product = [1..p+q] // 先預留乘積的空間
for b_i = 1 to q // 針對b的每一位數
carry = 0
for a_i = 1 to p // 針對a的每一位數
product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
carry = product[a_i + b_i - 1] / base
product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
product[b_i + p] = carry // 最高位數是最後一次計算乘法的進位
return product
优化空间复杂度假設在基數为，令 为两个输入数字位數長度的總和，若其结果需保存在存储器中，则其空间复杂度通常为。然而在某些应用中，不需要把整个结果保存在内存中，而可以在计算时将数字以字元流的方式输出（例如输出到系统终端或文件中）。在这些情况下，长乘法的优势在于可以将其轻松表示为对数空间算法——也就是说，只需要一个工作空间与输入中位数的对数成正比的算法（），这是乘数之积的雙重对数（）。注意，乘数本身仍保留在内存中，并且在此分析中忽略其 的空间。 只要知道之前乘積產生的進位，就可以由最低位起，一位一位的計算乘積的每一位數字，這是優化空間複雜度的關鍵。令ai和bi分別是被乘數及乘數的第i位數字，a和 b的最高位都已補0，補到n位數，而ri是乘積的第i位，而ci是計算ri後產生的進位（i=1表示是個位），則 or 簡單的推論可以證明進位不會超過n，ri的總和不會超過D * n：第一欄的進位是0，其他欄最多有n個數字，最多也只會從前一欄進位n。總和最多是D * n，進位到下一位的最多是D * n / D或n。因此這些數字都可以用O(log n)位數儲存。 偽代碼下的對數空間演算法為 ：
multiply(a[1..p], b[1..q], base) // Operands containing rightmost digits at index 1
tot = 0
for ri = 1 to p + q - 1 //For each digit of result
for bi = MAX(1, ri - p + 1) to MIN(ri, q) //Digits from b that need to be considered
ai = ri − bi + 1 //Digits from a follow "symmetry"
tot = tot + (a[ai] * b[bi])
product[ri] = tot mod base
tot = floor(tot / base)
product[p+q] = tot mod base //Last digit of the result comes from last carry
return product
在计算机中的用法有些集成电路會實現乘法，可能是用硬件或是微程序，可能針對各種整數及浮點數。在高精度计算中，在乘比較小的數字時，用底數為2w的長乘法，其中w為字元的位元數。 若要用此方式乘二個n位數數字，約需要n2次的運算。若用比較型式的方式表示，用數字位數這個自然的數字大小度量，用長乘法乘二個n位數數字的時間複雜度是Θ(n2)。 若要用軟體實現，長乘法演算法需要處理在加法時會出現的溢位問題，可能會很耗成本。典型的作法是用比較小的基底來進行運算，例如b，而讓8b為機器中表示的整數大小。這樣可以進行幾次運算之後才會溢位。若數字太大，可以只加數字的一部份到結果中，或是進位，將剩下的數字映射為一個小於b的較小數字。此作法稱為「正規化」。Richard Brent有在其Fortran軟體包MP中使用此一作法[2]。 格子乘法  格子乘法在演算法上和長乘法等效。需要在紙上劃格子，以引導計算，並且將乘法和加法分為二個步驟進行。這是在1202年在斐波那契的《計算書》中引進到歐洲。斐波那契用此方式心算，用左手和右手處理計算的中間值。16世紀的馬特拉克·那西在《Umdet-ul Hisab》書籍上列出了此演算法六種不同的變體。在奧斯曼帝國的恩德倫學校中，廣為使用此一演算法[3]。納皮爾的骨頭（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寫在右方。將乘積寫在格子的二個三角形中，將和寫在左邊和下方。結果條列如下：
二進制或農夫演算法農夫演算法是廣為在農民中使用的算法，其中不需要像長乘法一樣記憶乘法表[4][與來源不符]。此演算法曾在古埃及使用[5][6]，農夫演算法的優點是可以快速教授、不需要記憶、若沒有紙筆的話，也可以用其他東西輔助計算（例如籌碼），缺點是步驟比長除法要長，在計算大數字的乘法時不方便， 說明在紙上，寫下被乘數，被乘數的下方寫下被乘數反覆除二（且無條件捨去小數）的結果，被乘數的旁邊寫下乘數，乘數下方寫上乘數反覆乘二的結果。一直到被乘數那一欄為1為止。將乘數那一欄的數字相加，但若被乘數那一欄為偶數，跳過此數字不累加，所得結果即為乘積。 示例以下用農夫演算法計算11乘以3 。 十進制: 二進制: 11 3 1011 11 5 6 101 110 2 說明上述的步驟：
此作法有效的原因是因為乘法滿足分配律，因此： 以下是一個複雜的例子，仍用之前用過的範例（23,958,233 and 5,830）： Decimal: Binary: 5830 電腦中的二進制乘法
這是農夫演算法的變體。 二進制下，長乘法會變成很簡單的處理，針對每一個被乘數位數的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 有時的移位和加減法的組合會比硬體乘法器還快。 若電腦沒有乘法的運算，需要用上述方式來進行計算[7]，若將向左移位表示為相同的數加二次（兩者在邏輯上等價），也可以延伸到浮點數。 平方的四分之一乘法可以用平方的算式，計算二個數的乘積，有些來源的算式中會包括取整函数[8][9]，此方式源自於巴比伦数学（西元前2000-1600年）。 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的表[10]，Joseph Blater在1888年出版了1到200000的表[11]。 平方的四分之一乘法曾用在模拟计算机上，以形成二訊號相乘的模擬信號。二個輸入電壓的和或差可以用运算放大器達到。電壓平方可以用分段線性電路達成。最後二個平方的四分之一以及兩電壓的差以及再用运算放大器實現。 Everett L. Johnson在1980年時提出將此方式應用在數碼乘法器中[12]。為了產生8位元整數的乘積，數位裝置計算兩數的和以及差，查表計算平方，計算差值，再往右移位二個位元。 平方的四分之一乘法對8位元的系統有益，可以在沒有硬體乘法器的情形下實現乘法。Charles Putney有將此演算法實現在MOS 6502中[13]。 複數乘法演算法複數乘法包括四個實數乘法以及二個加法。 或 不過有辦法將實數乘法由四個減少到三個[14] 乘積(a + bi) · (c + di)可以用以下方式計算。
此演算法只用了三個乘法，比原來的四個乘法少一個，但加減法由原來的二個增加到五個。假如乘法的成本遠大於計算加減法的成本，此演算法的速度會比原來的演算法快。在現代先進的電腦上，乘法和加法花的時間可能相同，那麼此演算法就沒有速度上的優勢。若使用浮點數計算，此演算法可能會有精準度下降的問題，因此需要取捨。 在FFT（或是其他的线性映射），若是乘以固定係數（c + di，在FFT中稱為旋轉因子）的複數乘法，其中二個加法（d−c和c+d）可以事先計算，需要即時計算只剩三個乘法以及三個加法[15]。不過若是配合有浮点运算器的處理器，加法的速度和乘法相當，因此減少乘法，增加加減法的演算法，沒有速度上的優勢[16]。 大數字的快速乘法演算法未解決的計算機科學問題：針對二個位數數字的乘法，哪個乘法演算法的速度最快？
 Karatsuba乘法若需要計算到上千位數字相乘的系統，例如計算機代數系統或高精度计算函式庫，長乘法的速度太慢。因此會使用Karatsuba算法，此乘法演算法是Anatoly Karatsuba在1960年發現的，在1962年出版。此乘法演算法的精神在於觀察到二位數的乘法可以不用傳統四個乘法的作法，可以只用三個乘法完成。這是分治法的例子。假設要將二個二位數m進位數字 x1 m + x2和y1 m + y2相乘：
若要計算三個m進位數字的乘積，又可以用上述的技巧，使用递归的方式進行（但需要改為其他的進位），此方式。只要計算出乘積數字，再將數字相加，需要n個步驟。 Karatsuba算法的時間複雜度是O(nlog23) ≈ O(n1.585)，此方式明顯的比長乘法要快。因為递归產生的額外計算，若n較小時，Karatsuba算法會比長乘法慢，因此在n較小時，會切換回長乘法進行計算。 Karatsuba算法是第一個時間複雜度漸進的比長乘法快的演算法[17]，也可以視為是快速乘法理論的基礎。 1963年時，Peter Ungar建議將m改為i，以產生快速複數乘法的演算法[14]。若要計算 (a + b i) · (c + d i)，可依以下步驟進行：
如同上述複數乘法演算法所述的一樣，需要三個乘法以及五個加減法。 Toom-Cook 算法另一種乘法的演算法是Toom-Cook算法，或稱為Toom-3算法。Toom-Cook算法將每一個要相乘的數字切成幾部份，是Karatsuba算法的推廣。三路的Toom-Cook演算法可以針對大小為的被乘數和乘數進行乘法，其成本是大小為的被乘數和乘數乘法的5倍，因為運算加速的係數是，Karatsuba算法的加速係數是。 若用遞迴的方式將數字分成更多份，可以再縮減計算時間，但位數管理以及加法的成本也會增加。若位數到上千位數，一般會使用傅立葉轉換，速度多半會比較快，若位數更多，傅立葉轉換的優勢更加明顯。 傅立葉變換法 Strassen（1968年）曾提出用快速多項式乘法來計算快速整數乘法的基本概念。後來在1971年由Strassen和Schönhage找到理論和實務的確認，所得的就是Schönhage-Strassen演算法[18]。 下限若用單一處理器將二個n進位的數字相乘，時間複雜度有一個trivial的下界Ω(n) ，沒有更接近實際應用的下界。乘法在AC0[p]以外（p為任意整數），意思是不存在固定深度，多項式（甚至是次指數）大小，以AND、OR、NOT、MODp電路組合成的電路可以計算乘法。[19]。 多項式乘法上述的乘法演算法也可以用來計算多項式的乘法。例如Strassen演算法就可以用來計算多項式的乘積[20]。而 Kronecker替代也可以將多項式的乘法轉換為二個整數的乘法[21]。 以下是用長乘法來計算多項式乘法的例子： 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
=======================================[22]
相關條目參考資料
延伸閱讀
外部連結基本運算
進階演算法 |
