快速乘法算法（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 = 2^{n/2}a_L + a_R, \quad b = 2^{n/2}b_L + b_R\]其中：
- $a_L, b_L$：高 $n/2$ 位部分
- $a_R, b_R$：低 $n/2$ 位部分
代入展开：
\[ab = (2^{n/2} a_L + a_R)(2^{n/2} b_L + b_R) = 2^n a_L b_L + 2^{n/2}(a_L b_R + a_R b_L) + a_R b_R\]如果直接算，需要 4 次 规模为 $n/2$ 的乘法。
3. 关键优化：减少乘法次数
算法通过代数变换，将 4 次乘法优化为 3 次：
定义：
\[P1 = a_L b_L, \quad P2 = a_R b_R, \quad P3 = (a_L + a_R)(b_L + b_R)\]则：
\[a_L b_R + a_R b_L = P3 - P1 - P2\]最终：
\[ab = 2^n P1 + 2^{n/2}(P3 - P1 - P2) + P2\]这样只需要 3 次 $n/2$ 规模的乘法，加上一些加减法和移位（线性开销）。
4. 递归开销分析
设 $T(n)$ 为乘法开销，则：
\[T(n) = 3T(n/2) + O(n) \tag{A.1}\]其中：
- $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 可得: (同时进行一定放缩)
归纳成立，得：
\[T(2^k) \leq c(3^k - 2^k)\]6. 时间复杂度结论
因为：
\[3^k = 3^{\log_2 n} = n^{\log_2 3}\]所以：
\[T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})\]优于传统乘法的 $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})\]