大整数乘法：实现Karatsuba算法

题目

大整数乘法：实现Karatsuba算法

信息

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

考点

分治策略,递归实现,数学优化,大整数运算

快速回答

Karatsuba算法通过分治策略将大整数乘法时间复杂度优化至O(n^log₂3)≈O(n^1.585)。核心步骤：

1. 将两个n位数拆分为高位和低位：x = a·10^m + b, y = c·10^m + d
2. 递归计算三个关键乘积：
   • ac = a * c
   • bd = b * d
   • ad_plus_bc = (a+b)*(c+d) - ac - bd
3. 合并结果：xy = ac·10^2m + ad_plus_bc·10^m + bd

1. 原理说明

Karatsuba算法利用分治思想减少乘法次数：

• 传统方法：4次递归乘法（ac, ad, bc, bd），时间复杂度O(n²)
• Karatsuba：通过代数变换 (a+b)(c+d) = ac + ad + bc + bd，将乘法减至3次：
  ac, bd, 和 (a+b)(c+d) - ac - bd = ad+bc
• 复杂度：T(n) = 3T(n/2) + O(n) → O(n^log₂3)

2. 代码示例（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)

    # 递归计算三个乘积
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_plus_bc = karatsuba(a + b, c + d) - ac - bd

    # 合并结果
    return ac * (10 ** (2 * m)) + ad_plus_bc * (10 ** m) + bd

# 示例：计算1234 × 5678
print(karatsuba(1234, 5678))  # 输出7006652

3. 最佳实践

• 递归终止条件：当数字小于10或达到硬件支持范围时直接相乘
• 奇偶处理：对奇数位数字，高位补0对齐
• 性能优化：
  • 使用位运算替代幂运算（10^m → 1 << m）
  • 设置阈值切换到底层乘法（如数字长度≤32时调用硬件乘法）
• 内存管理：避免中间结果产生过多临时对象

4. 常见错误

• 拆分点错误：未正确处理奇数位导致数字错位（应确保a,b,c,d位数一致）
• 符号处理缺失：未考虑负数情况（可先记录符号位，取绝对值计算）
• 递归深度过大：未设置合适终止条件导致栈溢出
• 中间结果溢出：a+b或c+d可能超出整型范围（需用大整数存储）

5. 扩展知识

• 更优算法：Toom-Cook（分3块，O(n^1.465)）和Schönhage-Strassen（FFT，O(n log n log log n)）
• 实际应用：加密算法（RSA）、高精度科学计算、编译器对大整数的优化
• 复杂度对比：

  算法	时间复杂度	适用场景
  小学乘法	O(n2)	小规模数字
  Karatsuba	O(n1.585)	中等规模（103-104位）
  FFT乘法	O(n log n)	超大规模（>104位）