Karatsuba 算法溢出
Karatsuba Algorithm Overflow
我一直在学习Karatsuba's algorithm on Wikipedia
我在这个让我困惑的部分停了下来。为什么这个算法会溢出，我不明白他为解决这个问题所做的步骤。这是我的问题的截图
以免只为初学者考虑正数。让我们有 8 位 numbers/digits x0,x1,y0,y1.
当我们应用8位乘法时：
x0*y0 -> 8bit * 8bit -> 16 bit
它将产生最多 16 位的结果。最高值为：
FFh*FFh = FE01h
255*255 = 65025
现在如果我们 return 到 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都溢出了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 进位）将它们逐一添加和传播。
如果您向其中添加有符号值，您还需要一位符号。为避免它记住操作数的符号并使用绝对值...并根据原始符号设置结果符号。
有关详细信息，请参阅这些：
- Fast bignum square computation
我一直在学习Karatsuba's algorithm on Wikipedia 我在这个让我困惑的部分停了下来。为什么这个算法会溢出，我不明白他为解决这个问题所做的步骤。这是我的问题的截图
以免只为初学者考虑正数。让我们有 8 位 numbers/digits x0,x1,y0,y1.
当我们应用8位乘法时：
x0*y0 -> 8bit * 8bit -> 16 bit
它将产生最多 16 位的结果。最高值为：
FFh*FFh = FE01h
255*255 = 65025
现在如果我们 return 到 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都溢出了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 进位）将它们逐一添加和传播。
如果您向其中添加有符号值，您还需要一位符号。为避免它记住操作数的符号并使用绝对值...并根据原始符号设置结果符号。
有关详细信息，请参阅这些：
- Fast bignum square computation