Karatsuba算法

Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法（俄語：Алгоритм Карацубы），是一种快速乘法算法，由1960年提出并于1962年发表。它将两个位数字相乘所需的一位数乘法次数减少到了至多（如果是2的乘方，则正好为）。因此它比要次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（），卡拉楚巴算法需要次个位数乘法，而经典算法需要次。Toom–Cook算法是此算法更快速的泛型。对于充分大的，Schönhage-Strassen演算法甚至更快，算法的时间复杂度为。 值得一提的是，卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。