用于计算64位无符号的参数在C（A * B）％M FAST（++）上的x86-64平台？ [英] Compute (a*b)%m FAST for 64-bit unsigned arguments in C(++) on x86-64 platforms?

问题描述

我在寻找一个快方式有效地计算＆NBSP;（ A ⋅ B ）模 N ＆NBSP; （在该数学意义上）为 A ， B ， N 键入的uint64_t中。我可以忍受preconditions如 N = 0 ，甚至 A＆LT; N！＆放大器;＆安培; B＆LT; N

I'm looking for a fast method to efficiently compute  (a⋅b) modulo n  (in the mathematical sense of that) for a, b, n of type uint64_t. I could live with preconditions such as n!=0, or even a<n && b<n.

请注意，在C前pression （A * B）％N 将不会削减它，因为产品被截断为64位。我在寻找（uint64_t中）（（（uint128_t）A * B）N％）除了我没有一个 uint128_t （据我所知，在Visual C ++）。

Notice that the C expression (a*b)%n won't cut it, because the product is truncated to 64 bits. I'm looking for (uint64_t)(((uint128_t)a*b)%n) except that I do not have a uint128_t (that I know, in Visual C++).

我在为Visual C ++（preferably）或GCC /铛内在使得对X86-64平台提供的底层硬件的最佳使用;或者如果不能为便携式在线函数来完成。

I'm in for a Visual C++ (preferably) or GCC/clang intrinsic making best use of the underlying hardware available on x86-64 platforms; or if that can't be done for a portable inline function.

推荐答案

好吧，这个怎么样（未测试）

Ok, how about this (not tested)

modmul:
; rcx = a
; rdx = b
; r8 = n
mov rax, rdx
mul rcx
div r8
mov rax, rdx
ret

在precondition是 A * B / N＆LT; =〜0ULL ，否则会出现除法错误。这比 A℃的略少严格的条件; N'放大器;＆安培; M＆LT; ñ，其中一人可以比大 N 只要对方是足够小。

The precondition is that a * b / n <= ~0ULL, otherwise there will be a divide error. That's a slightly less strict condition than a < n && m < n, one of them can be bigger than n as long as the other is small enough.

不幸的是它已进行组装，并在单独的联系，因为MSVC不支持内联汇编的64位的目标。

Unfortunately it has to be assembled and linked in separately, because MSVC doesn't support inline asm for 64bit targets.

这也是仍然缓慢，真正的问题是，64 DIV ，这可能要花近百个周期（严重的是，多达90次的Nehalem处理器为例）。

It's also still slow, the real problem is that 64bit div, which can take nearly a hundred cycles (seriously, up to 90 cycles on Nehalem for example).

这篇关于用于计算64位无符号的参数在C（A * B）％M FAST（++）上的x86-64平台？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！