乘法算法

：multiply(a, b, 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 * b)        product = tot mod base        tot = floor(tot / base)    product = tot mod base                   //Last digit of the result comes from last carry    return product

在计算机中的用法

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

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

若要用软件实现，长乘法算法需要处理在加法时会出现的溢位问题，可能会很耗成本。典型的作法是用比较小的基底来进行运算，例如，而让8为机器中表示的整数大小。这样可以进行几次运算之后才会溢位。若数字太大，可以只加数字的一部分到结果中，或是进位，将剩下的数字映射为一个小于的较小数字。此作法称为“正规化”。Richard Brent有在其Fortran软件包MP中使用此一作法。

格子乘法在算法上和长乘法等效。需要在纸上划格子，以引导计算，并且将乘法和加法分为二个步骤进行。这是在1202年在斐波那契的《计算书（英语：Liber Abaci）》中引进到欧洲。斐波那契用此方式心算，用左手和右手处理计算的中间值。16世纪的马特拉克·那西（英语：Matrakçı Nasuh）在《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

二进制或农夫算法

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

在纸上，写下被乘数，被乘数的下方写下被乘数反复除二（且无条件舍去小数）的结果，被乘数的旁边写下乘数，乘数下方写上乘数反复乘二的结果。一直到被乘数那一栏为1为止。将乘数那一栏的数字相加，但若被乘数那一栏为偶数，跳过此数字不累加，所得结果即为乘积。

以下用农夫算法计算11乘以3 。

十進制:     二進制:11   3       1011  115    6       101  1102   12       10  11001   24       1  11000    ——         ——————    33         100001

说明上述的步骤：

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

以下是一个复杂的例子，仍用之前用过的范例（23,958,233 and 5,830）：

Decimal:             Binary:5830  23958233       1011011000110  10110110110010010110110012915  47916466       101101100011  101101101100100101101100101457  95832932       10110110001  101101101100100101101100100728  191665864       1011011000  1011011011001001011011001000364  383331728       101101100  10110110110010010110110010000182  766663456       10110110  10110110110010010110110010000091  1533326912       1011011  101101101100100101101100100000045  3066653824       101101  1011011011001001011011001000000022  6133307648       10110  10110110110010010110110010000000011 12266615296       1011  10110110110010010110110010000000005  24533230592       101  101101101100100101101100100000000002  49066461184       10  1011011011001001011011001000000000001  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年）。

和为整数，若+和−中有一个为奇数，另一个也一定会是奇数，因此上式中若有一项在取整数之前有分数，另一项也会有，两者会相消，不会影响所得的结果。以下是从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的表。

平方的四分之一乘法曾用在模拟计算机上，以形成二讯号相乘的模拟信号。二个输入电压的和或差可以用运算放大器达到。电压平方可以用分段线性（英语：piecewise linear function）电路达成。最后二个平方的四分之一以及两电压的差以及再用运算放大器实现。

Everett L. Johnson在1980年时提出将此方式应用在数码乘法器中。为了产生8位元整数的乘积，数位装置计算两数的和以及差，查表计算平方，计算差值，再往右移位二个位元。

平方的四分之一乘法对8位元的系统有益，可以在没有硬件乘法器的情形下实现乘法。Charles Putney有将此算法实现在MOS 6502中。

复数乘法包括四个实数乘法以及二个加法。

或

不过有办法将实数乘法由四个减少到三个

乘积( + ) · ( + )可以用以下方式计算。

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

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

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

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

Karatsuba算法的时间复杂度是O(log₂3) ≈ O(1.585)，此方式明显的比长乘法要快。因为递归产生的额外计算，若较小时，Karatsuba算法会比长乘法慢，因此在较小时，会切换回长乘法进行计算。

Karatsuba算法是第一个时间复杂度渐进的比长乘法快的算法，也可以视为是快速乘法理论的基础。

1963年时，Peter Ungar建议将改为，以产生快速复数乘法的算法。若要计算 ( + ) · ( + )，可依以下步骤进行：

如同上述复数乘法算法所述的一样，需要三个乘法以及五个加减法。

另一种乘法的算法是Toom-Cook算法，或称为Toom-3算法。Toom-Cook算法将每一个要相乘的数字切成几部分，是Karatsuba算法的推广。三路的Toom-Cook算法可以针对大小为${\displaystyle 3N}$进位的数字相乘，时间复杂度有一个trivial的下界Ω() ，没有更接近实际应用的下界。乘法在AC0（英语：ACC0）以外（为任意整数），意思是不存在固定深度，多项式（甚至是次指数）大小，以AND、OR、NOT、MOD电路组合成的电路可以计算乘法。。

上述的乘法算法也可以用来计算多项式的乘法。例如Strassen算法就可以用来计算多项式的乘积。而Kronecker替代（英语：Kronecker substitution）也可以将多项式的乘法转换为二个整数的乘法。

以下是用长乘法来计算多项式乘法的例子：