在x86-64平台上计算C(++)中64位无符号参数的(a*b)%m FAST？

Question

我正在寻找一个快速的方法来有效地计算(a⋅ b)模n  (在该数学意义上)的a,b,n类型的uint64_t.我可以忍受诸如n!=0甚至是前提条件a<n && b<n.

请注意,C表达式(a*b)%n不会删除它,因为产品被截断为64位.我正在寻找,(uint64_t)(((uint128_t)a*b)%n)除了我没有uint128_t(我知道,在Visual C++中).

我正在使用Visual C++(最好)或GCC/clang内部,充分利用x86-64平台上可用的底层硬件; 或者如果便携式inline功能无法做到这一点.

Answer 1

好的,这个怎么样(未经测试)

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

前提条件是a * b / n <= ~0ULL,否则会出现除法错误.这是一个稍微不那么严格的条件a < n && m < n,其中一个可以大于n另一个足够小的条件.

不幸的是,它必须单独组装和链接,因为MSVC不支持64位目标的内联asm.

它仍然很慢,真正的问题是64位div,这可能需要近百个周期(严重的是,例如Nehalem上最多90个周期).