计算 2^2⁸ % uint64_t

Question

如何有效计算 2^2⁸ % n，其中 n 为

uint64_t

（且非零）？

如果我能够像 MSVC 的

_udiv128

那样缩小范围，我可以这样做：

uint64_t remainder;
_udiv128(1, 0, n, &remainder);
_udiv128(remainder, 0, n, &remainder);

但这两条指令速度很慢，更不用说像 ARM 这样的 CPU 没有缩小除法。有更好的办法吗？

相关：如何在 C 中计算 2⁶⁴/n？

Answer 1

可以通过一个简单的技巧将缩小划分的数量减少到 1：

uint64_t remainder;
_udiv128(-n % n, 0, n, &remainder);

-n % n

仍然需要 64 位除法，但是除数的上半部分为零的除法往往更有效（当然比“完整”

libdivide_128_div_64_to_64

更有效，使用其慢速路径，这需要花费 2 64 位除法加上一堆额外的东西）。不过，有些处理器不太关心股息的非零上半部分。

这个技巧之所以有效，是因为 2⁶⁴ 肯定大于

n

，所以我们可以从中减去一次

n

，然后我们得到 2⁶⁴-n，它等于

-n

计算模 2⁶⁴ （uint64_t 上的算术以 2⁶⁴ 为模完成）。我们不能只将

-n

放入被除数的高位部分，因为这样商会变得太大并且除法会出错，而是需要使用专用的 128 位乘 64 位 remainder 运算（而不是除法）产生剩余物作为副产品）可以支持这一点。

可以用对

_udiv128

的调用来替换

libdivide_128_div_64_to_64

本质以支持其他平台。

在我看来，似乎有道理（考虑到本案的特殊性）还有更多的技巧，但我不知道它们，也找不到它们。我遇到的一个常见建议是使用平方求幂，但如果从字面上看，首先需要 6 个步骤才能达到

-n % n

（我们也可以从这个开始，然后只做 一个 平方），并且不会没有解决最大的问题：没有

_udiv128

如何做

_udiv128

所做的事情。对

-n % n

求平方，然后减少 mod

n

对我来说似乎并不比将

-n % n

乘以 2⁶⁴ 然后减少 mod

n

更好，它只是花费了额外的乘法（128 位输出） ）然后给我们留下了一个同样烦人的问题。