GNU C(gcc、clang或ICC)在大多数64位平台上支持has unsigned __int128(或者在旧版本中支持__uint128_t)。不过GCC在32位平台上不支持这种类型。 这是让编译器发出64位全乘指令并保留高半部分的一种简单而有效的方法(GCC知道,一个转换为128位整数的uint64_t指令的上半部分仍然是全零,所以你不会使用三个64位乘法来得到一个128位乘法)。 MSVC also has a __umulh intrinsic用于64位高半乘法,但同样,它仅在64位平台(特别是x86-64和AArch 64)上可用。文档还提到IPF(IA-64)有_umul128可用,但我没有用于安腾的MSVC可用。
#define HAVE_FAST_mul64 1
#ifdef __SIZEOF_INT128__ // GNU C
static inline
uint64_t mulhi64(uint64_t a, uint64_t b) {
unsigned __int128 prod = a * (unsigned __int128)b;
return prod >> 64;
}
#elif defined(_M_X64) || defined(_M_ARM64) // MSVC
// MSVC for x86-64 or AArch64
// possibly also || defined(_M_IA64) || defined(_WIN64)
// but the docs only guarantee x86-64! Don't use *just* _WIN64; it doesn't include AArch64 Android / Linux
// https://learn.microsoft.com/en-gb/cpp/intrinsics/umulh
#include <intrin.h>
#define mulhi64 __umulh
#elif defined(_M_IA64) // || defined(_M_ARM) // MSVC again
// https://learn.microsoft.com/en-gb/cpp/intrinsics/umul128
// incorrectly say that _umul128 is available for ARM
// which would be weird because there's no single insn on AArch32
#include <intrin.h>
static inline
uint64_t mulhi64(uint64_t a, uint64_t b) {
unsigned __int64 HighProduct;
(void)_umul128(a, b, &HighProduct);
return HighProduct;
}
#else
# undef HAVE_FAST_mul64
uint64_t mulhi64(uint64_t a, uint64_t b); // non-inline prototype
// or you might want to define @craigster0's version here so it can inline.
#endif
# x86-64 gcc7.3. clang and ICC are the same. (x86-64 System V calling convention)
# MSVC makes basically the same function, but with different regs for x64 __fastcall
mov rax, rsi
mul rdi # RDX:RAX = RAX * RDI
mov rax, rdx
ret
5条答案
按热度按时间bq9c1y661#
以下是ARMv8或Aarch64版本的asm:
下面是旧DEC编译器的asm:
如果您有x86的BMI2,并希望使用
mulxq
:通用x86乘法使用
mulq
:gajydyqb2#
如果你使用的是gcc,并且你的版本支持128位数(尝试使用__uint128_t),那么执行128乘法并提取高64位可能是获得结果的最有效方法。
如果你的编译器不支持128位数,那么Yakk的答案是正确的。然而,对于一般的消费者来说,它可能太简短了。特别是,实际的实现必须小心溢出64位整数。
他提出的简单而便携的解决方案是将a和b分别分解为2个32位数,然后使用64位乘法运算将这些32位数相乘。
那么很明显:
以及:
假设使用128位(或更大)算术来执行计算。
但是这个问题要求我们使用64位算术来执行所有的计算,所以我们不得不担心溢出。
由于a_hi、a_lo、b_hi和b_lo都是无符号的32位数,因此它们的乘积将适合无符号的64位数而不会溢出。
下面的代码将在数学运算必须以2^64为模时实现mulhi(a,b):
正如Yakk所指出的,如果不介意高64位相差+1,可以省略进位位的计算。
2jcobegt3#
**64位伊萨的TL:DR和GCC:
(a * (unsigned __int128)b) >> 64
可以很好地编译为一条全乘或高半乘指令。**无需再使用内联asm。不幸的是,目前的编译器 * 没有 * 优化@craigster0的可移植版本,所以如果你想利用64位CPU,你不能使用它,除非作为你没有
#ifdef
的目标的后备。你需要一个128位的类型或者一个内在的。)GNU C(gcc、clang或ICC)在大多数64位平台上支持has
unsigned __int128
(或者在旧版本中支持__uint128_t
)。不过GCC在32位平台上不支持这种类型。这是让编译器发出64位全乘指令并保留高半部分的一种简单而有效的方法(GCC知道,一个转换为128位整数的uint64_t指令的上半部分仍然是全零,所以你不会使用三个64位乘法来得到一个128位乘法)。
MSVC also has a
__umulh
intrinsic用于64位高半乘法,但同样,它仅在64位平台(特别是x86-64和AArch 64)上可用。文档还提到IPF(IA-64)有_umul128
可用,但我没有用于安腾的MSVC可用。对于x86-64、AArch 64和PowerPC 64(以及其他),这将编译为一条
mul
指令和几条mov
指令来处理调用约定(在此内联之后应该会优化掉)。从Godbolt编译器资源管理器(对于x86-64、PowerPC 64和AArch 64,使用source + asm):(or使用
clang -march=haswell
启用BMI 2:mov rdx, rsi
/mulx rax, rcx, rdi
将高半部分直接放入RAX中。gcc是哑的,仍然使用额外的mov
。)对于AArch 64(带有gcc
unsigned __int128
或带有__umulh
的MSVC):使用编译时常数2的乘方乘法器,我们通常会得到预期的右移来获取一些高位,但是gcc有趣地使用了
shld
(参见Godbolt链接)。不幸的是,当前的编译器 * 没有 * 优化@craigster0的便携版本。您将获得8倍
shr r64,32
、4倍imul r64,r64
、以及一串用于x86-64的add
/mov
指令,即,它编译成大量32 × 32 =〉64位乘法并解包结果。因此,如果您想要利用64位CPU的东西,您需要一些#ifdef
。全乘
mul 64
指令在Intel CPU上为2个uop,但仍然只有3个周期的延迟,与imul r64,r64
相同,imul r64,r64
只产生64位结果。因此,__int128
/ intrinsic版本在延迟和吞吐量方面要便宜5到10倍(对周围代码的影响)在现代x86-64上比便携式版本,从基于http://agner.org/optimize/的快速眼球猜测。在Godbolt编译器资源管理器的上面链接中查看它。
gcc在乘以16时完全优化了该函数,但是:得到一个右移,比
unsigned __int128
乘法更有效。g6ll5ycj4#
这是我今晚提出的一个单元测试版本,它提供了完整的128位产品。通过检查,它似乎比大多数其他在线解决方案(例如Botan库和其他答案)更简单,因为它利用了代码注解中解释的中间部分不会溢出的优点。
我为这个github项目写了这段代码:https://github.com/catid/fp61
o2g1uqev5#
长乘法应该可以表现。
将
a*b
拆分为(hia+loa)*(hib+lob)
,得到4个32位乘法和一些移位,用64位进行,手工进位,得到高位部分。注意,高部分的近似值可以用较少的乘法来完成--用1次乘法精确到2^33左右,用3次乘法精确到1以内。
我不认为有一个便携式的替代品。