Karatsuba 算法

定义

Karatsuba 算法是快速大整数乘法算法,由苏联数学家 Anatoly Karatsuba 于 1960 年提出,推翻了 Kolmogorov 关于乘法需要 Ω(n²) 步的猜想,是分治思想的里程碑成果。

原理

把 n 位数 x、y 各拆成高低两半:x = a·B + b,y = c·B + d(B 为基数的幂)。朴素展开需要 ac、ad、bc、bd 四次子乘法,而 Karatsuba 注意到 ad + bc = (a+b)(c+d) - ac - bd,于是只需 ac、bd、(a+b)(c+d) 三次乘法加若干次加减与移位。递归应用得复杂度 O(n^log₂3) ≈ O(n^1.585)。

应用

GMP、Java BigInteger、Python 大整数运算等库在中等规模数上采用 Karatsuba,规模更大时切换到 Toom-Cook 或基于 FFT 的 Schönhage-Strassen 算法;密码学中的大数运算也广泛受益。

意义

它展示了分治可以突破直觉下界,启发了后续一系列快速算术算法。