给出低位字产品，计算两个单词的双字产品（签名）

在Hacker的喜悦中，有一种算法来计算两个（带符号）单词的双字产品 。

函数muldws1使用四次乘法和五次加法来计算两个单词的双字。

在该代码的末尾有一行注释掉

 /* w[1] = u*v; // Alternative. */ 

该替代方案使用五次乘法和四次加法，即它为乘法交换加法。

但我认为这种替代方法可以改进。 我还没有说过硬件。 让我们假设一个假设的CPU，它可以计算两个字但不是高位字的乘积的低位字（例如，对于32位字32×32到低32）。 在这种情况下，在我看来，这个算法可以改进。 这就是我假设的32位字（相同的概念适用于64位字）。

 void muldws1_improved(int w[], int32_t x, int32_t y) { uint16_t xl = x; int16_t xh = x >> 16; uint16_t yl = y; int16_t yh = y >> 16; uint32 lo = x*y; int32_t t = xl*yh + xh*yl; uint16_t tl = t; int16_t th = t >>16; uint16_t loh = lo >> 16; int32_t cy = loh<tl; //carry int32_t hi = xh*yh + th + cy; w[0] = hi; w[1] = lo; } 

这使用了四次乘法，三次加法和一次比较。 这是我希望的一个小改进。

这可以改善吗？ 有没有更好的方法来确定进位标志？ 我应该指出我也假设硬件没有进位标志（例如没有ADDC指令）但可以比较word1<word （例如word1<word ）。

编辑：正如Sander De Dycker指出我的function未通过unit testing。 这是一个通过unit testing的版本，但效率较低。 我认为它可以改进。

 void muldws1_improved_v2(int w[], int32_t x, int32_t y) { uint16_t xl = x; int16_t xh = x >> 16; uint16_t yl = y; int16_t yh = y >> 16; uint32_t lo = x*y; int32_t t2 = xl*yh; int32_t t3 = xh*yl; int32_t t4 = xh*yh; uint16_t t2l = t2; int16_t t2h = t2 >>16; uint16_t t3l = t3; int16_t t3h = t3 >>16; uint16_t loh = lo >> 16; uint16_t t = t2l + t3l; int32_t carry = (t<t2l) + (loh<t); int32_t hi = t4 + t2h + t3h + carry; w[0] = hi; w[1] = lo; } 

这使用了四次乘法，五次加法和两次比较，这比原始函数更糟糕。

Answer 1

在我的问题中，我的muldws1_improved函数存在两个问题。 其中一个是当我做xl*yh + xh*yl时它错过了一个进位。 这就是unit testing失败的原因。 但另一个是签名*无符号产品需要比C代码中更多的机器逻辑。 （见下面的编辑）。 我找到了一个更好的解决方案 ，首先优化未签名的产品函数muldwu1然后再做

 muldwu1(w,x,y); w[0] -= ((x<0) ? y : 0) + ((y<0) ? x : 0); 

纠正标志。

这是我尝试使用低级词lo = x*y来改进muldwu1 （是的，这个函数通过了Hacker的喜悦中的unit testing）。

 void muldwu1_improved(uint32_t w[], uint32_t x, uint32_t y) { uint16_t xl = x; uint16_t xh = x >> 16; uint16_t yl = y; uint16_t yh = y >> 16; uint32_t lo = x*y; //32x32 to 32 uint32_t t1 = xl*yh; //16x16 to 32 uint32_t t2 = xh*yl; //16x16 to 32 uint32_t t3 = xh*yh; //16x16 to 32 uint32_t t = t1 + t2; uint32_t tl = 0xFFFF & t; uint32_t th = t >> 16; uint32_t loh = lo >> 16; uint32_t cy = ((t 

这比Hacker的喜悦中使用的原始函数少一个，但它必须进行两次比较

  1 mul32x32 to 32 3 mul16x16 to 32 4 add32 5 shift logical (or shuffles) 1 and 2 compare32 *********** 16 operations 

编辑：

我对Hacker's Delight（第2版）中的一个声明感到困扰，该声明就mulhs和mulhu算法而言。

该算法在有符号或无符号版本中需要16个基本RISC指令，其中四个是乘法。

我仅在16个SSE指令中实现了无符号算法，但我的签名版本需要更多指令。 我弄明白为什么，我现在可以回答我自己的问题。

我在Hacker's Delight中找不到更好的版本的原因是他们的假设RISC处理器有一个指令来计算两个单词的乘积的低位字。 换句话说，他们的算法已针对这种情况进行了优化，因此不太可能存在比他们已有的更好的版本。

他们列出替代方案的原因是因为他们假设乘法（和除法）可能比其他指令更昂贵，因此他们将备选方案作为优化的案例。

因此C代码不会隐藏重要的机器逻辑。 它假设机器可以用单词*单词来降低单词。

为什么这很重要？ 在他们的算法中，他们首先做

 u0 = u >> 16; 

然后

 t = u0*v1 + k; 

如果u = 0x80000000 u0 = 0xffff8000 。 但是，如果您的CPU只能使用半字产品来获得完整的字，则忽略u0的上半字，并且您得到错误的签名结果。

在这种情况下，你应该计算无符号高位字，然后使用hi -= ((x<0) ? y : 0) + ((y<0) ? x : 0);进行校正hi -= ((x<0) ? y : 0) + ((y<0) ? x : 0); 正如我已经说过的那样

我对此感兴趣的原因是英特尔的SIMD指令（SSE2到AVX2）没有64x64到64的指令，它们只有32x32到64.这就是我的签名版本需要更多指令的原因。

但是AVX512有64x64到64的指令。 因此，对于AVX512，签名版本应采用与unsigned相同数量的指令。 但是，由于64x64到64指令可能比32x32到64指令慢得多，因此无论如何都可以更有意义地执行无符号版本然后更正。