algorithm - Karatsuba 算法溢出

Question

我一直在学习Karatsuba's algorithm on Wikipedia我在这个让我困惑的部分停了下来。为什么这个算法会溢出，我不明白他为解决这个问题所做的步骤。这是我的问题的截图

Answer 1

以免只为初学者考虑正数。让我们有 8 位数字/数字 x0,x1,y0,y1。

当我们应用 8 位乘法时:

x0*y0 -> 8bit * 8bit -> 16 bit

它将产生最多 16 位的结果。最高值是:

FFh*FFh = FE01h
255*255 = 65025

现在如果我们回到Karatsuba让

X = x0 + x1<<8
Y = y0 + y1<<8
Z = X*Y = z0 + z1<<8 + z2<<16

现在让我们看看zi的位宽

z2 = x1*y1         -> 16 bit
z1 = x1*y0 + x0*y1 -> 17 bit
z0 = x0*y0         -> 16 bit

注意 z1 是 17 位，因为 top 值是

65025+65025 = 130050

所以每个 zi 都溢出了 8bit。要处理这个问题，您只需取最低的 8 位，其余的添加到更高的数字(如进位传播)。所以:

z1 += z0>>8;   z0 &= 255;
z2 += z1>>8;   z1 &= 255;
z3  = z2>>8;
Z = z0 + z1<<8 + z2<<16 + z3<<24

但通常乘法的硬件实现会自行处理这个问题，并以两个单词而不是一个单词的形式给出结果。见Cant make value propagate through carry

所以16位乘法的结果是32位。请注意，要添加 8 位子结果，您至少需要 10 位，因为我们将 3 个数字加在一起，或者使用 9 位(或 8 位 + 1 进位)将它们逐一添加和传播。

如果您向其中添加带符号的值，您还需要一位用于符号。为避免这种情况，请记住操作数的符号并使用 abs 值...并根据原始符号设置结果符号。

有关详细信息，请参阅以下内容:

• C++ 32bit * 32bit multiplication without asm
• Fast bignum square computation