def karatsuba(x, y):
    if type(x) is not int or type(y) is not int:
        raise TypeError("操作数必须是整数")
    negative = (x < 0) != (y < 0)

    def multiply(a, b):
        if a == 0 or b == 0:
            return 0
        width = max(a.bit_length(), b.bit_length())
        if width <= 8:
            return a * b

        half = width // 2
        mask = (1 << half) - 1
        a_high, a_low = a >> half, a & mask
        b_high, b_low = b >> half, b & mask

        z2 = multiply(a_high, b_high)
        z0 = multiply(a_low, b_low)
        z1 = multiply(a_high + a_low, b_high + b_low)
        middle = z1 - z2 - z0
        return (z2 << (2 * half)) + (middle << half) + z0

    result = multiply(abs(x), abs(y))
    return -result if negative else result


for x, y in [(1234, 5678), (-1234, 5678), (-12, -34), (0, 5678), (1, 999)]:
    print(f"{x} × {y} = {karatsuba(x, y)}")

输出：

1234 × 5678 = 7006652
-1234 × 5678 = -7006652
-12 × -34 = 408
0 × 5678 = 0
1 × 999 = 999

代码没有用十进制字符串确定位数，而是用 bit_length()；低位提取和重组也全部采用二进制操作。阈值8是为了让课堂例子能展示递归，实际工程实现通常会根据运行环境选择更大的阈值。

算法执行过程

主示例中1234有11个二进制位，5678有13个位。因此 width=13、half=6、 $B=64$ ：

1234=19\times64+18,\qquad5678=88\times64+46.

子计算	调用输入	返回结果
高位乘法 $z_2$	`(19, 88)`	1672
低位乘法 $z_0$	`(18, 46)`	828
和的乘法 $z_1$	`(37, 134)`	4958
中间项	$4958-1672-828$	2458
重建乘积	$1672\times4096+2458\times64+828$	7006652

三个子调用的最大操作数都不超过8位，直接触发边界乘法。根调用只做三次子乘法，没有单独计算 $19\times46$ 和 $18\times88$ 。

输入为 (-1234,5678) 时，内部过程完全相同，最终给7006652加上负号。规模更大的整数则会在三条分支继续采用同样的分割规则。

复杂度分析

设两输入绝对值的最大二进制位数为 $w$ ，令 $d=\max(1,w)$ 。采用按位运算成本模型：长度为 $d$ 的整数加减、移位、掩码操作按 $O(d)$ 计，固定8位以内的乘法按常数计。

时间复杂度： 最坏为 $O(d^{\log_2 3})\approx O(d^{1.585})$ 。每次执行三个约半长的子乘法，当前层额外工作为线性；高低位之和可能产生进位，因此更准确的规模上界为：

T(d)\leq3T(\lceil d/2\rceil+1)+O(d).

这个固定的一位增量不改变渐近指数。常见的 $3T(d/2)+O(d)$ 写法是忽略进位后的简化模型。两数位数很不均衡或含0时，实际工作可以更少。传统按位竖式乘法的最坏时间为 $O(d^2)$ 。

辅助空间复杂度： $O(d)$ 位的同时存活的中间整数，递归栈包含 $O(\log(d+1))$ 个调用帧；沿一条调用链的操作数长度按几何级数递减。结果本身需要 $O(d)$ 位。若只数整数对象而不数其位数，会低估大整数存储。

Python 内置大整数乘法自身已有优化，加上本实现的递归开销，不能仅凭渐近式断言这段教学代码会比内置 x * y 更快。

易错点

仍然递归计算四个交叉乘积。 会回到四分支结构，失去 Karatsuba 减少子乘法的关键。
把 $z_1$ 当作中间系数。 它包含 $ac$ 和 $bd$ ，必须再减去 $z_2,z_0$ 。
高位只左移一次。 $z_2$ 对应 $B^2$ ，应左移 2 * half 位。
直接对负数拆位。 负数的移位和掩码含符号语义，本实现先取绝对值再处理。
用数值大小作为递推规模。 分割的是表示长度，应使用位数 $d$ 分析。
把大整数加法视为常数，同时又讨论按位乘法。 分析必须使用一致的计数模型。

课堂练习

取十进制 $B=10$ ，将12与34分割，用三次乘法得到结果。
主示例的中间系数2458，是否等于 $19\times46+18\times88$ ？
同样减半，四次子乘法对应的简化递推是什么？与三次相比结论如何？
输入 (-7,0)、(-7,-9) 及 (7.0,9)，分别有什么结果？

参考答案

$a=1,b=2,c=3,d=4$ 。 $z_2=3,z_0=8,z_1=3\times7=21$ ，中间系数为10，结果为 $3\times100+10\times10+8=408$ 。这是手算公式；代码采用二进制且此例直接触发8位边界。
是。 $19\times46=874$ ， $18\times88=1584$ ，合计2458。
$T(d)=4T(d/2)+O(d)$ ，得到 $O(d^2)$ ；改为三个子乘法得到 $O(d^{\log_2 3})$ 。
分别返回0、63，第三个抛出 TypeError，因为7.0为浮点数。