乘法算法

乘法算法是计算两个数值相乘乘积的算法。为了提高运算效率，不同大小的数字适用不同的乘法算法。自十进制数字系统诞生以来，就已开始发展乘法算法。

网格法

主条目：网格式乘法

网格法 （或盒式法）是一种用于给小学生进行乘法计算启蒙的简单乘法算法。自1990年代后期以来，它一直是英格兰和威尔士公立小学数学课程的标准部分。

将两个乘数分解（“划分”）为百位、十位或个位的部分，然后在相对简单的乘法步骤中直接算出这些部分的乘积，再将其一一相加以算出最终结果。用这种方法计算 $34\times 13$，可以画出如下网格：

  300
   40
   90
 + 12
 ————
  442

×	30	4
10	300	40
3	90	12

最后再通过一次求和或逐行累加得到结果（见右），实质是计算了 $(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语言中的用法），以让程式紧凑。

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

优化空间复杂度

假设在基数为$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)位数储存。

伪代码下的对数空间算法为

：
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

在计算机中的用法

有些集成电路会实现乘法，可能是用硬件或是微程序，可能针对各种整数及浮点数。在高精度计算中，在乘比较小的数字时，用底数为2^w的长乘法，其中w为字元的位元数。

若要用此方式乘二个n位数数字，约需要n²次的运算。若用比较型式的方式表示，用数字位数这个自然的数字大小度量，用长乘法乘二个n位数数字的时间复杂度是Θ(n²)。

若要用软件实现，长乘法算法需要处理在加法时会出现的溢位问题，可能会很耗成本。典型的作法是用比较小的基底来进行运算，例如b，而让8b为机器中表示的整数大小。这样可以进行几次运算之后才会溢位。若数字太大，可以只加数字的一部分到结果中，或是进位，将剩下的数字映射为一个小于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写在右方。将乘积写在格子的二个三角形中，将和写在左边和下方。结果条列如下：

2 3 9 5 8 2 3 3 +---+---+---+---+---+---+---+---+- |1 /|1 /|4 /|2 /|4 /|1 /|1 /|1 /| | / | / | / | / | / | / | / | / | 5 01|/ 0|/ 5|/ 5|/ 5|/ 0|/ 0|/ 5|/ 5| +---+---+---+---+---+---+---+---+- |1 /|2 /|7 /|4 /|6 /|1 /|2 /|2 /| | / | / | / | / | / | / | / | / | 8 02|/ 6|/ 4|/ 2|/ 0|/ 4|/ 6|/ 4|/ 4| +---+---+---+---+---+---+---+---+- |0 /|0 /|2 /|1 /|2 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 3 17|/ 6|/ 9|/ 7|/ 5|/ 4|/ 6|/ 9|/ 9| +---+---+---+---+---+---+---+---+- |0 /|0 /|0 /|0 /|0 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 0 24|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0| +---+---+---+---+---+---+---+---+- 26 15 13 18 17 13 09 00

01 002 0017 00024 000026 0000015 00000013 000000018 0000000017 00000000013 000000000009 0000000000000 ————————————— 139676498390

= 139,676,498,390

二进制或农夫算法

主条目：农夫算法

农夫算法是广为在农民中使用的算法，其中不需要像长乘法一样记忆乘法表。此算法曾在古埃及使用，农夫算法的优点是可以快速教授、不需要记忆、若没有纸笔的话，也可以用其他东西辅助计算（例如筹码），缺点是步骤比长除法要长，在计算大数字的乘法时不方便，

说明

在纸上，写下被乘数，被乘数的下方写下被乘数反复除二（且无条件舍去小数）的结果，被乘数的旁边写下乘数，乘数下方写上乘数反复乘二的结果。一直到被乘数那一栏为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以内的乘法：

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
⌊n2/4⌋	0	0	1	2	4	6	9	12	16	20	25	30	36	42	49	56	64	72	81

若要计算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₁ = c · (a + b)

k₂ = a · (d − c)

k₃ = b · (c + d)

实部 = k₁ − k₃

虚部 = k₁ + k₂.

此算法只用了三个乘法，比原来的四个乘法少一个，但加减法由原来的二个增加到五个。假如乘法的成本远大于计算加减法的成本，此算法的速度会比原来的算法快。在现代先进的电脑上，乘法和加法花的时间可能相同，那么此算法就没有速度上的优势。若使用浮点数计算，此算法可能会有精准度下降的问题，因此需要取舍。

在FFT（或是其他的线性映射），若是乘以固定系数（c + di，在FFT中称为旋转因子）的复数乘法，其中二个加法（d−c和c+d）可以事先计算，需要即时计算只剩三个乘法以及三个加法。不过若是配合有浮点运算器的处理器，加法的速度和乘法相当，因此减少乘法，增加加减法的算法，没有速度上的优势。

大数字的快速乘法算法

Karatsuba乘法

主条目：Karatsuba算法

若需要计算到上千位数字相乘的系统，例如计算机代数系统或高精度计算函式库，长乘法的速度太慢。因此会使用Karatsuba算法，此乘法算法是Anatoly Karatsuba在1960年发现的，在1962年出版。此乘法算法的精神在于观察到二位数的乘法可以不用传统四个乘法的作法，可以只用三个乘法完成。这是分治法的例子。假设要将二个二位数m进位数字 x₁ m + x₂和y₁ m + y₂相乘：

1. 计算x₁ · y₁，称此结果是F
2. 计算x₂ · y₂，称此结果是G
3. 计算(x₁ + x₂) · (y₁ + y₂)，称此结果是H
4. 计算H − F − G，称此结果是K，此数字等于x₁ · y₂ + x₂ · y₁
5. 计算F · m² + K · m + G.

若要计算三个m进位数字的乘积，又可以用上述的技巧，使用递归的方式进行（但需要改为其他的进位），此方式。只要计算出乘积数字，再将数字相加，需要n个步骤。

Karatsuba算法的时间复杂度是O(n^log₂3) ≈ 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-Cook算法，或称为Toom-3算法。Toom-Cook算法将每一个要相乘的数字切成几部分，是Karatsuba算法的推广。三路的Toom-Cook算法可以针对大小为$3N$的被乘数和乘数进行乘法，其成本是大小为$N$的被乘数和乘数乘法的5倍，因为运算加速的系数是$9/5$，Karatsuba算法的加速系数是$4/3$。

若用递回的方式将数字分成更多份，可以再缩减计算时间，但位数管理以及加法的成本也会增加。若位数到上千位数，一般会使用傅立叶转换，速度多半会比较快，若位数更多，傅立叶转换的优势更加明显。

傅立叶变换法

说明用快速傅立叶变换（FFT）计算1234 × 5678 = 7006652的作法。其中有使用模数为337的数论转换，选择85为1的8次方根。

Strassen（1968年）曾提出用快速多项式乘法来计算快速整数乘法的基本概念。后来在1971年由Strassen和Schönhage找到理论和实务的确认，所得的就是Schönhage-Strassen算法。

下限

若用单一处理器将二个n进位的数字相乘，时间复杂度有一个trivial的下界Ω(n) ，没有更接近实际应用的下界。乘法在AC⁰[p]以外（p为任意整数），意思是不存在固定深度，多项式（甚至是次指数）大小，以AND、OR、NOT、MOD_p电路组合成的电路可以计算乘法。。

多项式乘法

上述的乘法算法也可以用来计算多项式的乘法。例如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 （页面存档备份，存于互联网档案馆）