大整数乘法实现

题目

大整数乘法实现

信息

• 类型：问答
• 难度：⭐⭐

考点

分治算法,数学优化,递归应用,大数处理

快速回答

使用分治策略的 Karatsuba 算法实现大整数乘法：

• 将大整数拆分为高位和低位两部分
• 递归计算三个关键子乘积
• 组合子结果时使用公式：z = z2 × 102m + (z1 - z2 - z0) × 10m + z0
• 当数字足够小时转为直接乘法（递归基）
• 时间复杂度优化至 O(n^log₂3) ≈ O(n^1.585)

原理说明

Karatsuba 算法利用分治思想优化大整数乘法。对于 n 位整数 x 和 y：

1. 分解：x = a × 10^m + b, y = c × 10^m + d（m = n/2）
2. 计算三个子乘积：
   • z0 = b × d
   • z1 = (a + b) × (c + d)
   • z2 = a × c
3. 组合结果：xy = z2 × 10^2m + (z1 - z2 - z0) × 10^m + z0

通过减少乘法次数（传统需要 4 次，Karatsuba 只需 3 次），显著降低时间复杂度。

代码示例（Python）

def karatsuba(x, y):
    # 递归终止条件：小整数直接相乘
    if x < 10 or y < 10:
        return x * y

    # 计算位数和分割点
    n = max(len(str(x)), len(str(y)))
    m = n // 2

    # 分割数字
    a = x // (10**m)
    b = x % (10**m)
    c = y // (10**m)
    d = y % (10**m)

    # 递归计算子问题
    z0 = karatsuba(b, d)
    z1 = karatsuba((a + b), (c + d))
    z2 = karatsuba(a, c)

    # 组合结果
    return (z2 * 10**(2*m)) + ((z1 - z2 - z0) * 10**m) + z0

# 测试
print(karatsuba(123456, 789012))  # 输出 97408265472

最佳实践

• 阈值优化：当整数小于特定阈值（如 1000）时切换为直接乘法，减少递归开销
• 奇偶处理：对奇数位数字补零对齐，确保正确分割
• 内存管理：避免字符串转换开销，直接用整数运算
• 并行计算：三个子任务可并行执行提升性能

常见错误

• 递归终止条件缺失：导致无限递归
• 位数计算错误：未处理数字位数奇偶差异
• 符号处理遗漏：未考虑负数场景
• 中间结果溢出：a+b 或 c+d 可能超出整型范围
• 低效的位数计算：使用 len(str(x)) 有性能瓶颈，建议用对数计算

扩展知识

• Toom-Cook 算法：将数字分为 k 块，复杂度 O(n^{log(2k-1)/log(k)})，k=3 时优于 Karatsuba
• Schönhage–Strassen 算法：基于 FFT 的 O(n log n log log n) 算法，适用于超大整数（>10,000 位）
• 实际应用场景：
  • 密码学（RSA 密钥生成）
  • 高精度科学计算
  • 编译器对大整数的优化
• 时间复杂度对比：

  算法	时间复杂度	适用场景
  小学乘法	O(n2)	小整数
  Karatsuba	O(n1.585)	中等整数（100-10,000位）
  FFT-based	O(n log n)	超大整数（>10,000位）