我正在寻找一种有效(可选的标准,优雅且易于实现)的解决方案来乘以相对较大的数字,并将结果存储为一个或多个整数:
假设我有两个64位整数,如下所示:
uint64_t a = xxx, b = yyy;
当我这样做时a * b,如何检测操作是否导致溢出,并且在这种情况下将进位存储在某处？
请注意,我不想使用任何大号库,因为我对存储数字的方式有限制.
在C++中,说:
uint64_t i;
uint64_t j;
然后i * j将产生一个uint64_t值为i和之间的乘法的下半部分j,即(i * j) mod 2^64.现在,如果我想要乘法的较高部分怎么办？我知道在使用32位整数时,存在一个汇编指令做类似的事情,但我对汇编并不熟悉,所以我希望得到帮助.
制作以下内容的最有效方法是:
uint64_t k = mulhi(i, j);
AXV2没有任何整数乘法,其源大于32位.它提供32 x 32 - > 32乘法,以及32 x 32 - > 64乘以1,但没有64位源.
假设我需要一个输入大于32位但小于或等于52位的无符号乘法 - 我可以简单地使用浮点DP乘法或FMA指令,并且当整数输入和输出时输出将是位精确的结果可以用52或更少的比特表示(即,在[0,2 ^ 52-1]范围内)？
如果我想要产品的所有104位更一般的情况怎么样？或整数乘积超过52位的情况(即,产品在位索引中的非零值> 52) - 但我只想要低52位？在后一种情况下,它MUL会给我更高的位并舍去一些低位(也许这就是IFMA帮助的？).
编辑:事实上,根据这个答案,也许它可以做任何高达2 ^ 53的事情- 我忘记了1在尾数之前隐含的领先有效地给了你一点.
1有趣的是,正如Mysticial 在评论中所解释的那样,64位产品PMULDQ操作的延迟是32位PMULLD版本的一半,吞吐量是32位版本的两倍.
我创建了一个使用SIMD进行64位*64位到128位的功能.目前我已经使用SSE2(acutally SSE4.1)实现了它.这意味着它可以同时运行两个64b*64b到128b的产品.同样的想法可以扩展到AVX2或AVX512,同时提供四个或八个64b*64到128b的产品.我的算法基于http://www.hackersdelight.org/hdcodetxt/muldws.c.txt
该算法进行一次无符号乘法,一次有符号乘法和两次有符号*无符号乘法.签名的*signed和unsigned*unsigned操作很容易使用_mm_mul_epi32和_mm_mul_epu32.但混合签名和未签名的产品给我带来了麻烦.例如,考虑一下.
int32_t x = 0x80000000;
uint32_t y = 0x7fffffff;
int64_t z = (int64_t)x*y;
双字产品应该是0xc000000080000000.但是如果你假设你的编译器知道如何处理混合类型,你怎么能得到这个呢？这就是我想出的:
int64_t sign = x<0; sign*=-1; //get the sign and make it all ones
uint32_t t = abs(x); //if x<0 take two's complement again
uint64_t prod = (uint64_t)t*y; //unsigned product
int64_t z = (prod ^ sign) - sign; //take two's complement based on the sign
使用SSE可以这样做
__m128i xh; //(xl2, xh2, xl1, xh1) high is signed, low unsigned
__m128i …我想在不使用64位数据类型的情况下进行32位有符号整数乘法.我的输入是Q1.31(两种)格式.
input1 = A32 (Ah Al) - higher, lower half's of A32
input2 = B32 (Bh Bl) - higher, lower half's of B32
结果应为Q1.31格式,保留溢出情况.
我需要C代码.请提供格式说明.