Big Integer Multiplication Algorithms

先讲卡拉楚巴算法，它是一种快速的大整数乘法算法，相比于传统的朴素乘法算法，该算法使用了分治法。
假设有两个整数X和Y，长度都为n，可以将它们表示为：





其中和是高位部分，和是低位部分，。
传统的乘法需要计算以下四项：

这其中需要进行四次乘法操作：

卡拉楚巴算法通过减少乘法的数量优化了计算，它只需要三次乘法：

1. (高位相乘)
2. (低位相乘)
3. (混合项)
4. (组合结果)

时间复杂度分析：

其将n的问题划分为三个n/2的子问题：



根据递归主定理:

代码实现：

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y

    n = max(len(str(x)), len(str(y)))
    m = n // 2

    high_x, low_x = divmod(x, 10**m)
    high_y, low_y = divmod(y, 10**m)

    z2 = karatsuba(high_x, high_y)
    z0 = karatsuba(low_x, low_y)
    z1 = karatsuba(high_x + low_x, high_y + low_y) - z2 - z0

    return z2 * 10**(2*m) + z1 * 10**m + z0

x = 12345678
y = 87654321
print(f"{x} * {y} = {karatsuba(x, y)}")

在python的源代码中也有实现Karatsuba算法，具体可见longobject.c。

具体的视频可以看cs170

算法比较

算法	时间复杂度	适用场景	优点	缺点	相关论文链接
普通乘法		小整数乘法	简单直接	对大整数极其低效	无
Karatsuba		小到中等大小整数	简单，适合实现递归分治	不适合超大整数	The Complexity of Computations
Toom-Cook	或更低	中等到大整数	高效扩展卡拉楚巴	实现复杂	ToomCook
Schönhage-Strassen		超大整数（百万位以上）	高效，经典算法	对小规模整数效果较差	Fast Multiplication of Large Integers
Fürer		超大整数	理论性能优于 Schönhage-Strassen	实现难度高，适用性有限	Faster Integer Multiplication (2007)
Harvey-Hoeven		超大整数（理论最佳）	理论极限性能	实现复杂，尚未广泛应用	Integer Multiplication in Time O(n log n) (2019)

On Integer Multiplication in the (Asymptotic) Limit ,这篇论文对整数乘法复杂度的理论极限进行了深入分析。

这里讲的都是整数乘法，优化的重点在于减少单次乘法操作的次数，矩阵乘法是处理多个元素的乘法与求和，两者的核心都是分治法。