1

我一直在 Wikipedia 上研究 Karatsuba 的算法 ，我停在这让我感到困惑的部分。为什么这个算法会溢出，我不明白他为解决这个问题所采取的步骤。这是我的问题的截图

截屏

4

1 回答 1

2

以免仅将正数视为初学者。让我们有 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 位，因为最高值是

65025+65025 = 130050

所以每个zi溢出8位。要处理这个问题，您只需使用最低的 8 位，其余的添加到更高的数字（如进位的传播）。所以：

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

但通常乘法的硬件实现会自行处理这个问题，并将结果作为两个单词而不是一个单词给出。见不能通过进位使价值传播

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

如果向其中添加有符号值，则需要另外一位符号。为了避免它记住操作数的符号并使用 abs 值......并根据原始符号设置结果的符号。

有关更多详细信息，请参阅这些：

于 2017-12-18T18:40:04.183 回答