c - 以 64 位整数为模计算 128 位整数的最快方法

Question

我有一个 128 位无符号整数 A 和一个 64 位无符号整数 B。计算 A % B 的最快方法是什么 - 即除以 A 的(64 位)余数由 B?

我想用 C 语言或汇编语言来完成这项工作，但我需要以 32 位 x86 平台为目标。不幸的是，这意味着我无法利用编译器对 128 位整数的支持，也无法利用 x64 架构在单条指令中执行所需操作的能力。

编辑:

感谢您到目前为止的回答。但是，在我看来，建议的算法会非常慢——执行 128 位 x 64 位除法的最快方法不是利用处理器对 64 位 x 32 位除法的 native 支持吗？有谁知道是否有一种方法可以根据几个较小的除法来执行较大的除法？

回复:B多久改变一次？

主要是我对通用解决方案感兴趣 - 如果 A 和 B 每次都可能不同，您将执行什么计算？

但是，第二种可能的情况是 B 不像 A 那样频繁变化 - 每个 B 可能有多达 200 个 A。在这种情况下，您的答案会有何不同？

Answer 1

可以使用Russian Peasant Multiplication的分割版.

要找到余数，执行(伪代码):

X = B;

while (X <= A/2)
{
    X <<= 1;
}

while (A >= B)
{
    if (A >= X)
        A -= X;
    X >>= 1;
}

模数留在A中。

您需要实现移位、比较和减法以对由一对 64 位数字组成的值进行运算，但这相当简单(您可能应该将左移 1 实现为 X + X).

这将最多循环 255 次(使用 128 位 A)。当然，您需要对零除数进行预检查。