快速乘法算法（Karatsuba 算法）
1. 算法核心思想
快速乘法算法采用 分治法（Divide-and-Conquer） 策略，将大整数乘法问题分解为更小的子问题，通过递归求解并组合结果，显著降低了传统竖式乘法的计算开销。
传统乘法的复杂度是 \(O(n^2)\)，而快速乘法通过减少子问题的数量，把复杂度降到 \(O(n^{\log_2 3}) \approx O(n^{1.585})\)。
2. 基本思路
设 \(a, b\) 为两个 \(n\) 比特整数（假设 \(n = 2^k\) 便于分治）：
其中：
- \(a_L, b_L\)：高 \(n/2\) 位部分
- \(a_R, b_R\)：低 \(n/2\) 位部分
代入展开：
如果直接算，需要 4 次 规模为 \(n/2\) 的乘法。
3. 关键优化：减少乘法次数
算法通过代数变换，将 4 次乘法优化为 3 次：
定义：
则：
最终：
这样只需要 3 次 \(n/2\) 规模的乘法，加上一些加减法和移位（线性开销）。
4. 递归开销分析
设 \(T(n)\) 为乘法开销，则：
其中：
- \(3T(n/2)\)：递归计算 \(P1, P2, P3\)
- \(O(n)\)：加减法、移位、分割数字等线性操作
5. 数学归纳法证明复杂度
目标：证明 \(T(2^k) \leq c(3^k - 2^k)\)，其中 \(c = \max\{T(2), C\}\)。
-
基础情形 \(k=1\)： \(T(2) \leq c(3-2) = c\)，成立。
-
归纳假设： 假设 \(T(2^k) \leq c(3^k - 2^k)\) 成立。
-
归纳步骤：
由等式 A.1 可得: (同时进行一定放缩)
$$ \begin{aligned} T(2^{k+1}) &\leq 3T(2^k) + C\cdot 2^{k+1} \ &\leq 3c(3^k - 2^k) + C\cdot 2^{k+1} \ &\leq 3c(3^k - 2^k) + c\cdot 2^{k+1} \ &\leq c(3^{k+1} - 2^{k+1}) \quad (\text{因 } C \leq c) \end{aligned} $$
归纳成立，得：
6. 时间复杂度结论
因为：
所以：
优于传统乘法的 \(O(n^2)\)。
7. 算法意义
- 显著减少大整数乘法的计算复杂度。
- 实际应用中常与其他算法（如 Toom-Cook、FFT 快速乘法）结合使用。
- 是大数计算库（如 GMP）的基础。
- 在密码学、高精度科学计算中应用广泛。
8. 总结公式
- 分解：
$$ a = 2^{n/2}a_L + a_R, \quad b = 2^{n/2}b_L + b_R $$
- 三个子问题：
$$ P1 = a_L b_L, \quad P2 = a_R b_R, \quad P3 = (a_L + a_R)(b_L + b_R) $$
- 合并结果：
$$ ab = 2^n P1 + 2^{n/2}(P3 - P1 - P2) + P2 $$
- 递归开销：
$$ T(n) = 3T(n/2) + O(n) $$
- 时间复杂度：
$$ T(n) = O(n^{\log_2 3}) \approx O(n^{1.585}) $$