问Karatsuba算法溢出

EN

以免只考虑正数作为起始点。让我们有8位数字/数字x0,x1,y0,y1。

当我们应用8位乘法时：

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

它将产生多达16位的结果。最重要的是：

FFh*FFh = FE01h
255*255 = 65025

如果我们回到卡拉特赛

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

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

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

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

有关更多细节，请参见以下内容：

• 无asm的32位乘法
• 快速大平方计算