大整数乘法（Karatsuba算法）
📌 定义
大整数乘法是指计算两个位数很多的整数的乘积。传统的竖式乘法时间复杂度为O(n²)，而Karatsuba算法通过分治思想将复杂度优化到O(n
示例:
1234 × 5678
传统方法: 需要16次乘法
Karatsuba: 只需要3次递归乘法
核心思路
将大整数拆分成两部分，使用分治法减少乘法次数：
对于两个n位数 x 和 y:
x = a × 10^(n/2) + b
y = c × 10^(n/2) + d
传统方法:
x × y = (a × 10^(n/2) + b) × (c × 10^(n/2) + d)
= ac × 10^n + (ad + bc) × 10^(n/2) + bd
需要4次乘法: ac, ad, bc, bd
Karatsuba优化:
设:
z0 = ac
z1 = bd
z2 = (a + b)(c + d) - ac - bd = ad + bc
则: x × y = z0 × 10^n + z2 × 10^(n/2) + z1
只需3次乘法: ac, bd, (a+b)(c+d)
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 竖式乘法 | O(n²) | O(1) | 传统方法 |
| Karatsuba | O(n^1.585) | O(n) | 分治优化 |
| Toom-Cook | O(n^1.465) | O(n) | 更复杂的分治 |
| FFT | O(n log n) | O(n) | 最快但实现复杂 |
其中 1.585 ≈ log₂(3)
Go 代码
Go 实现
package main
import (
"fmt"
"math"
)
func karatsuba(x, y int64) int64 {
// 基准情况
if x < 10 || y < 10 {
return x * y
}
// 计算位数
n := max(numDigits(x), numDigits(y))
m := n / 2
power := int64(math.Pow10(m))
// 分割数字
a, b := x/power, x%power
c, d := y/power, y%power
// 三次递归乘法
z0 := karatsuba(a, c)
z1 := karatsuba(b, d)
z2 := karatsuba(a+b, c+d) - z0 - z1
// 组合结果
return z0*int64(math.Pow10(2*m)) + z2*int64(math.Pow10(m)) + z1
}
func numDigits(n int64) int {
if n == 0 {
return 1
}
count := 0
for n > 0 {
n /= 10
count++
}
return count
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
var x, y int64 = 1234, 5678
result := karatsuba(x, y)
fmt.Printf("%d × %d = %d\n", x, y, result)
fmt.Printf("验证: %d × %d = %d\n", x, y, x*y)
}思路展开
递归树示例（1234 × 5678）
1234 × 5678
/ | \
/ | \
12×56 (12+34)×(56+78) 34×78
672 46×134 2652
/ | \ / | \ / | \
1×5 (1+2)×(5+6) 2×6 ... 3×7 (3+4)×(7+8) 4×8
最终计算:
z0 = 672
z1 = 2652
z2 = 46×134 - 672 - 2652 = 6164 - 672 - 2652 = 2840
结果 = 672×10000 + 2840×100 + 2652
= 6720000 + 284000 + 2652
= 7006652
复杂度推导
T(n) = 递归求解n位数乘法的时间
传统方法:
T(n) = 4T(n/2) + O(n)
= O(n²)
Karatsuba:
T(n) = 3T(n/2) + O(n)
根据主定理:
T(n) = aT(n/b) + f(n)
a = 3, b = 2, f(n) = O(n)
log_b(a) = log_2(3) ≈ 1.585
因为 f(n) = O(n) < O(n^1.585)
所以 T(n) = O(n^log_2(3)) = O(n^1.585)
经典题目
应用场景
- 大整数计算库
- 密码学运算
- 科学计算
- 高精度数值计算
相关算法
- Toom-Cook算法（更高阶的分治）
- Schönhage-Strassen算法（FFT based）
- 大整数除法
⚖️ 优缺点
优点
- ✅ 时间优化：O(n^1.585) vs O(n²)
- ✅ 分治思想：经典的分治应用
- ✅ 易于实现：相比FFT方法更简单
缺点
- ❌ 常数因子大：小数字时不如直接乘法
- ❌ 空间开销：递归需要O(n)空间
- ❌ 实际应用：现代库通常使用FFT方法
🎨 应用场景
- 大整数库：Python的大整数运算内部使用
- 密码学：RSA等算法中的大数运算
- 科学计算：高精度数值计算
- 数学研究：数论问题求解