我正在为一个数论研究项目编写一些 C 代码，该项目需要使用许多不同的模数进行大量模算术运算。简单来说:我需要多次执行 (a * b) % n 操作。
该代码旨在使用 64 位字在 PC 上运行，并且已知所有模数都小于 2^64，因此所有操作数均由无符号 64 位整数实现。
我的问题是:是否会使用蒙哥马利模乘法(仅使用加法和乘法)而不是 C 模运算符 %(转换为 a % n = a - n *(a/n) 并且还使用除法)导致执行速度更快？
直觉上，我会说答案是:不，因为 PC 上的(字大小)除法在计算上并不比(字大小)乘法昂贵太多，而且蒙哥马利缩减实际上会导致开销。
感谢任何建议。
更新:一方面，根据 Paul Ogilvie(请参阅下面的评论)，(a * b) % n 需要 1 次乘法和 1 次除法。另一方面，蒙哥马利乘法需要(忽略将操作数转换和转换回蒙哥马利表示形式所需的操作，因为它们只对每个模 n 和二进制移位完成一次)3 次乘法。因此，一旦乘法比除法快两倍，蒙哥马利似乎就比“%”快...
最佳答案
你的直觉是错误的。除法比乘法慢很多倍，无论是整数还是 float 。参见 this excellent answer关于类似的问题。速度的确切差异取决于您在哪个 CPU 上运行，代码是否可以矢量化，甚至取决于代码的其余部分大约在同一时间在做什么。
如果你用一个常数除以整数，例如，如果你在编译时知道 n，那么编译器可以将其转换为一系列乘法和移位，甚至可能与蒙哥马利模乘法。如果 n 在编译时未知，那么实现蒙哥马利模乘法可能是值得的。
但是，当您实现代码的两个版本并对其进行基准测试时，您会得到最好的答案。
关于c - PC 上的蒙哥马利乘法与字长模数。这值得么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59823320/