卡拉楚巴算法

Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法（俄語：Алгоритм Карацубы），是一种快速乘法算法，由1960年阿納托利·阿列克謝耶維奇·卡拉楚巴（英语：Anatoly_Karatsuba）提出并于1962年发表。^[1][2][3]它将两个${\displaystyle n}$位数字相乘所需的一位数乘法次数减少到了至多${\displaystyle 3n^{\log _{2}3}\approx 3n^{1.585}}$（如果${\displaystyle n}$是2的乘方，则正好为${\displaystyle n^{\log _{2}3}}$）。因此它比要${\displaystyle n^{2}}$次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（${\displaystyle n=1024=2^{10}}$），卡拉楚巴算法需要${\displaystyle 3^{10}=59049}$次个位数乘法，而经典算法需要${\displaystyle (2^{10})^{2}=1048576}$次。Toom–Cook算法是此算法更快速的泛型。对于充分大的${\displaystyle n(n\gg 1)}$，Schönhage-Strassen演算法甚至更快，算法的时间复杂度为${\displaystyle O(n\log n\log \log n)}$。

洋紅色箭頭表示乘法，琥珀色表示加法，銀色表示減法，淺青色表示左移。A、B、C顯示了用於獲得中間值的遞歸。

Анато́лий Алексе́евич Карацу́ба

Анато́лий Алексе́евич Карацу́ба

值得一提的是，卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。

算法

基本步骤

卡拉楚巴算法主要是用于两个大数的乘法，极大提高了运算效率，相较于普通乘法降低了复杂度，并在其中运用了递归的思想。基本的原理和做法是将位数很多的两个大数${\displaystyle x}$ 和${\displaystyle y}$ 分成位数较少的数，每个数都是原来${\displaystyle x}$ 和${\displaystyle y}$ 位数的一半。这样处理之后，简化为做三次乘法，并附带少量的加法操作和移位操作。

示例

要計算12345和6789的乘積：

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

對只有三個數進行運算的乘法結果：

z₂ = 12 × 6 = 72

z₀ = 345 × 789 = 272205

z₁ = (12 + 345) × (6 + 789) − z₂ − z₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

將三部分結果相加並相應地移位：

結果 = z₂ · (B^m)² + z₁ · (B^m)¹ + z₀ · (B^m)⁰, i.e.

結果 = 72 · 1000² + 11538 · 1000 + 272205 = 83810205.

注意：中間第三次乘法運算的輸入域小於前兩次乘法的兩倍，其輸出域小於前兩次乘法的四倍，並且基數為1000的進位是根據前兩次乘法計算的，在計算這兩個減法時必須考慮。

实现

伪代码实现

procedure karatsuba(num1, num2) if (num1 < 10) or (num2 < 10) return num1*num2 /* calculates the size of the numbers */ m = max(size_base10(num1), size_base10(num2)) m2 = m/2 /* split the digit sequences about the middle */ high1, low1 = split_at(num1, m2) high2, low2 = split_at(num2, m2) /* 3 calls made to numbers approximately half the size */ z0 = karatsuba(low1,low2) z1 = karatsuba((low1+high1),(low2+high2)) z2 = karatsuba(high1,high2) return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

Python代码实现

# Python 2 and 3 def karatsuba(num1, num2): num1Str, num2Str = str(num1), str(num2) if num1Str[0] == '-': return -karatsuba(-num1, num2) if num2Str[0] == '-': return -karatsuba(num1, -num2) if num1 < 10 or num2 < 10: return num1 * num2 maxLength = max(len(num1Str), len(num2Str)) num1Str = ''.join(list('0' * maxLength)[:-len(num1Str)] + list(num1Str)) num2Str = ''.join(list('0' * maxLength)[:-len(num2Str)] + list(num2Str)) splitPosition = maxLength // 2 high1, low1 = int(num1Str[:-splitPosition]), int(num1Str[-splitPosition:]) high2, low2 = int(num2Str[:-splitPosition]), int(num2Str[-splitPosition:]) z0, z2 = karatsuba(low1, low2), karatsuba(high1, high2) z1 = karatsuba((low1 + high1), (low2 + high2)) return z2 * 10 ** (2 * splitPosition) + (z1 - z2 - z0) * 10 ** (splitPosition) + z0 

参考文献

1. A. Karatsuba and Yu. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. Proceedings of the USSR Academy of Sciences. 1962, 145: 293–294. 
2. A. A. Karatsuba. The Complexity of Computations (PDF). Proceedings of the Steklov Institute of Mathematics. 1995, 211: 169–183 [2013-07-25]. （原始内容 (PDF)于2020-03-26）. 
3. Knuth D.E.（1969）The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp.

• Karatsuba's Algorithm for Polynomial Multiplication（页面存档备份，存于互联网档案馆）
• 埃里克·韦斯坦因. Karatsuba Multiplication. MathWorld. 
• Bernstein, D. J., "Multidigit multiplication for mathematicians（页面存档备份，存于互联网档案馆）". Covers Karatsuba and many other multiplication algorithms.

外部鏈接

• 卡拉楚巴多項式乘法算法 （页面存档备份，存于互联网档案馆）
• 埃里克·韦斯坦因. Karatsuba Multiplication（卡拉楚巴乘法）. MathWorld. 
• Bernstein, D. J., "Multidigit multiplication for mathematicians （页面存档备份，存于互联网档案馆）". Covers Karatsuba and many other multiplication algorithms.