Karatsuba 乘法

执行 大数 的乘法，可以使用比通常的蛮力“长乘法”技术更少（很多）操作的方法。正如 Karatsuba (Karatsuba 和 Ofman 1962) 发现的那样，两个 -位 数字的乘法 可以通过小于 的 位复杂度 来完成，使用 以下形式 的恒等式

(1)

递归地进行下去，则得到 位复杂度 ，其中 (Borwein et al. 1989)。已知的最佳界限是 步，对于 (Schönhage 和 Strassen 1971, Knuth 1998)。然而，这个 算法 难以实现，但是基于 快速傅里叶变换 的程序很容易实现，并且给出了 位复杂度 (Brigham 1974, Borodin 和 Munro 1975, Borwein et al. 1989, Knuth 1998)。

作为一个具体的例子，考虑在基数 中，两个都只有两位“数字”长的数字的乘法，

			(2)
			(3)

那么它们的乘积是

			(4)
			(5)
			(6)

与其评估各个数字的乘积，现在写成

			(7)
			(8)
			(9)

关键项是 ，它可以展开、重新分组，并用 表示为

(10)

然而，由于 和 ，立即得出

			(11)
			(12)
			(13)

因此， 的三个“数字”已使用三次乘法而不是四次乘法进行评估。该技术可以推广到多位数字，但权衡是需要更多的加法和减法。

现在考虑四位“数字”的数字

(14)

它可以写成以基数 表示的两位“数字”的数字，

(15)

新基数中的“数字”现在是

			(16)
			(17)

并且 Karatsuba 算法可以应用于这种形式的 和 。因此，Karatsuba 算法不限于乘以两位数，而更一般地将两个数字的乘法表示为大小减半的数字的乘法。算法通过递归应用于较小的所需子产品所获得的渐近速度是 (Knuth 1998)。

当此技术递归应用于多位数字时，在递归中会达到一个点，此时加法和减法的开销使得使用通常的 乘法 算法来评估部分乘积更有效。因此，最有效的总体方法依赖于 Karatsuba 和传统乘法的组合。