Day 10：Karatsuba 乘法

当你在纸上做两个数字的乘法时，一般我们都是用小时候学到的方法：

这个计算方式的时间复杂度是 O(n²)，但是我们有其他的方法加速相乘的计算速度。

Karatsuba 乘法

Karatsuba 乘法是一种快速乘法。此算法在1960年由 Anatolii Alexeevitch Karatsuba 提出，并于1962年得以发表。此算法主要用于两个大数相乘。普通乘法的复杂度是 n²，而 Karatsuba 算法的复杂度仅为 3nlog2(3) 。

算法思路

可以注意到 AD +BC 这个计算需要两个 O(n²/4) 的乘法和一个 O(n) 的加法。

Karatsuba 把这个原始的计算改成上面这个计算，因为 AC 和 BD 是已知的，因此现在的 AD +BC 的时间复杂度变成了 一个 O(n²/4) 的乘法和四个 O(n) 的加法或减法，达到 O(n^log2(3)) 的时间复杂度

算法实现