分治算法大整数相乘python

好的，这里是分治算法实现大整数相乘的 Python 代码：

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

    # 计算位数
    m = max(len(str(x)), len(str(y)))
    m2 = m // 2

    # 分割成高位和低位
    high1, low1 = x // 10**m2, x % 10**m2
    high2, low2 = y // 10**m2, y % 10**m2

    # 递归计算三个乘积
    z0 = karatsuba(low1, low2)
    z1 = karatsuba((low1 + high1), (low2 + high2))
    z2 = karatsuba(high1, high2)

    # 计算结果
    return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**m2) + z0

这个算法的时间复杂度为 $O(n^{\log_2 3})$，比传统的 $O(n^2)$ 算法更快。