我正在使用 2^64 的基数用 C++ 编写一个多精度库，目前我正在处理 mod 操作。我正在使用 Donald E. Knuth 1998 年版的“计算机编程艺术”卷中描述的算法 D。 2，第 4.3.1 节，用于除法，它产生商和余数。对于 mod 操作，我正在执行除法，最后丢掉商。尽管 Knuth 的算法 D 如果在 C++ 中实现非常快，并且在每个步骤中对部分除法和并发多精度乘法/减法进行了一些 ASM 增强，但我不确定是否有更好的方法，因为丢掉了一个精心计算的结果对我来说似乎效率不高。
不幸的是，不可能摆脱算法 D 中的部分除法，因为计算余数时需要部分商，通过从被除数中迭代地减去部分商和除数的乘积。
我在 Internet 上搜索了替代解决方案，并找到了 Paul Barrett 撰写的有影响力的论文和 Peter L. Montgomery .然而，他们使用的花哨技巧似乎只有在以相同模数连续执行大量 mod 操作时才会奏效，因为它们涉及大量的预计算。在模幂运算等复杂运算中就是这种情况，其中单个模数需要多个平方和乘积的 mod。 Barrett从余数的基本定义开始，r = a - b * (a/b)，将除法改为与的倒数的乘法b。然后，他提出了一种计算此乘法的有效方法，如果对多次类似计算计算一次倒数，这种方法就会得到返回。 Montgomery 将操作数转换为一个完全不同的留数系统，其中模块化运算的成本很低，但要付出来回转换的代价。
此外，这两种算法都引入了一些限制，需要满足这些限制才能正确运行。例如，蒙哥马利通常要求操作数为奇数，这在使用素数的 RSA 计算中就是这种情况，但在一般情况下不能假设。在这些限制之外，需要更多的规范化开销。
所以我需要的是一个高效的一次性 mod 函数，没有开销和特殊限制。因此，我的问题是:是否有可能在不首先计算商的情况下以比除法更有效的方式计算余数？
最佳答案
一个建议是编写一个简单的函数来计算 A%B=C并存储 A , B和 C值放入一个数组，然后将所有结果存储到一个 vector 中。然后将它们打印出来以查看所有输入和输出值之间的关系。
可以做一件事来简化这项工作，那就是了解 mod 函数的一些属性。这两个语句将帮助您了解该功能。
0 mod N = 0 N mod 0 = undefined
自 0 mod N = 0我们可以为 A 放一个测试用例如果是 0我们可以用它来填充我们的数组。同样，如果 B = 0我们可以填充数组的 C值 -1只是代表未定义，因为你不能执行 A mod 0因为编译将因除以 0 而失败。
我写这个函数就是为了做到这一点；然后我通过一个循环运行它 A & B来自 [0,15] .
#include <array>
#include <vector>
#include <iostream>
std::array<int, 3> calculateMod(int A, int B) {
std::array<int, 3 > res;
if (A == 0) {
res = std::array<int, 3>{ 0, B, 0 };
}
else if (B == 0) {
res = std::array<int, 3>{ A, 0, -1 };
}
else {
res = std::array<int, 3>{ A, B, A%B };
}
return res;
}
int main() {
std::vector<std::array<int, 3>> results;
int N = 15;
for (int A = 0; A <= N; A++) {
for (int B = 0; B <= N; B++) {
results.push_back(calculateMod(A, B));
}
}
// Now print out the results in a table form:
int i = 0; // Index for formatting output
for (auto& res : results) {
std::cout << res[0] << " % " << res[1] << " = " << res[2] << '\n';
// just for formatting output data to make it easier to read.
i++;
if ( i > N ) {
std::cout << '\n';
i = 0;
}
}
return 0;
}
这是它的输出:
0 % 0 = 0
0 % 1 = 0
0 % 2 = 0
0 % 3 = 0
0 % 4 = 0
0 % 5 = 0
0 % 6 = 0
0 % 7 = 0
0 % 8 = 0
0 % 9 = 0
0 % 10 = 0
0 % 11 = 0
0 % 12 = 0
0 % 13 = 0
0 % 14 = 0
0 % 15 = 0
1 % 0 = -1
1 % 1 = 0
1 % 2 = 1
1 % 3 = 1
1 % 4 = 1
1 % 5 = 1
1 % 6 = 1
1 % 7 = 1
1 % 8 = 1
1 % 9 = 1
1 % 10 = 1
1 % 11 = 1
1 % 12 = 1
1 % 13 = 1
1 % 14 = 1
1 % 15 = 1
2 % 0 = -1
2 % 1 = 0
2 % 2 = 0
2 % 3 = 2
2 % 4 = 2
2 % 5 = 2
2 % 6 = 2
2 % 7 = 2
2 % 8 = 2
2 % 9 = 2
2 % 10 = 2
2 % 11 = 2
2 % 12 = 2
2 % 13 = 2
2 % 14 = 2
2 % 15 = 2
3 % 0 = -1
3 % 1 = 0
3 % 2 = 1
3 % 3 = 0
3 % 4 = 3
3 % 5 = 3
3 % 6 = 3
3 % 7 = 3
3 % 8 = 3
3 % 9 = 3
3 % 10 = 3
3 % 11 = 3
3 % 12 = 3
3 % 13 = 3
3 % 14 = 3
3 % 15 = 3
4 % 0 = -1
4 % 1 = 0
4 % 2 = 0
4 % 3 = 1
4 % 4 = 0
4 % 5 = 4
4 % 6 = 4
4 % 7 = 4
4 % 8 = 4
4 % 9 = 4
4 % 10 = 4
4 % 11 = 4
4 % 12 = 4
4 % 13 = 4
4 % 14 = 4
4 % 15 = 4
5 % 0 = -1
5 % 1 = 0
5 % 2 = 1
5 % 3 = 2
5 % 4 = 1
5 % 5 = 0
5 % 6 = 5
5 % 7 = 5
5 % 8 = 5
5 % 9 = 5
5 % 10 = 5
5 % 11 = 5
5 % 12 = 5
5 % 13 = 5
5 % 14 = 5
5 % 15 = 5
6 % 0 = -1
6 % 1 = 0
6 % 2 = 0
6 % 3 = 0
6 % 4 = 2
6 % 5 = 1
6 % 6 = 0
6 % 7 = 6
6 % 8 = 6
6 % 9 = 6
6 % 10 = 6
6 % 11 = 6
6 % 12 = 6
6 % 13 = 6
6 % 14 = 6
6 % 15 = 6
7 % 0 = -1
7 % 1 = 0
7 % 2 = 1
7 % 3 = 1
7 % 4 = 3
7 % 5 = 2
7 % 6 = 1
7 % 7 = 0
7 % 8 = 7
7 % 9 = 7
7 % 10 = 7
7 % 11 = 7
7 % 12 = 7
7 % 13 = 7
7 % 14 = 7
7 % 15 = 7
8 % 0 = -1
8 % 1 = 0
8 % 2 = 0
8 % 3 = 2
8 % 4 = 0
8 % 5 = 3
8 % 6 = 2
8 % 7 = 1
8 % 8 = 0
8 % 9 = 8
8 % 10 = 8
8 % 11 = 8
8 % 12 = 8
8 % 13 = 8
8 % 14 = 8
8 % 15 = 8
9 % 0 = -1
9 % 1 = 0
9 % 2 = 1
9 % 3 = 0
9 % 4 = 1
9 % 5 = 4
9 % 6 = 3
9 % 7 = 2
9 % 8 = 1
9 % 9 = 0
9 % 10 = 9
9 % 11 = 9
9 % 12 = 9
9 % 13 = 9
9 % 14 = 9
9 % 15 = 9
10 % 0 = -1
10 % 1 = 0
10 % 2 = 0
10 % 3 = 1
10 % 4 = 2
10 % 5 = 0
10 % 6 = 4
10 % 7 = 3
10 % 8 = 2
10 % 9 = 1
10 % 10 = 0
10 % 11 = 10
10 % 12 = 10
10 % 13 = 10
10 % 14 = 10
10 % 15 = 10
11 % 0 = -1
11 % 1 = 0
11 % 2 = 1
11 % 3 = 2
11 % 4 = 3
11 % 5 = 1
11 % 6 = 5
11 % 7 = 4
11 % 8 = 3
11 % 9 = 2
11 % 10 = 1
11 % 11 = 0
11 % 12 = 11
11 % 13 = 11
11 % 14 = 11
11 % 15 = 11
12 % 0 = -1
12 % 1 = 0
12 % 2 = 0
12 % 3 = 0
12 % 4 = 0
12 % 5 = 2
12 % 6 = 0
12 % 7 = 5
12 % 8 = 4
12 % 9 = 3
12 % 10 = 2
12 % 11 = 1
12 % 12 = 0
12 % 13 = 12
12 % 14 = 12
12 % 15 = 12
13 % 0 = -1
13 % 1 = 0
13 % 2 = 1
13 % 3 = 1
13 % 4 = 1
13 % 5 = 3
13 % 6 = 1
13 % 7 = 6
13 % 8 = 5
13 % 9 = 4
13 % 10 = 3
13 % 11 = 2
13 % 12 = 1
13 % 13 = 0
13 % 14 = 13
13 % 15 = 13
14 % 0 = -1
14 % 1 = 0
14 % 2 = 0
14 % 3 = 2
14 % 4 = 2
14 % 5 = 4
14 % 6 = 2
14 % 7 = 0
14 % 8 = 6
14 % 9 = 5
14 % 10 = 4
14 % 11 = 3
14 % 12 = 2
14 % 13 = 1
14 % 14 = 0
14 % 15 = 14
15 % 0 = -1
15 % 1 = 0
15 % 2 = 1
15 % 3 = 0
15 % 4 = 3
15 % 5 = 0
15 % 6 = 3
15 % 7 = 1
15 % 8 = 7
15 % 9 = 6
15 % 10 = 5
15 % 11 = 4
15 % 12 = 3
15 % 13 = 2
15 % 14 = 1
15 % 15 = 0
从上面的数据我们可以看出，如果A == B结果将是 0 .我们还可以看到，如果 B > A然后 B == A .最后我们可以看到 odd 之间存在模式。和 even A 的值同时 B < A .如果你能理解这些模式，那么其中大部分就变成了代数运算。从这里开始，下一步将是创建一个算法，该算法将获取所有这些数据并将其转换为二进制等价物。
我选择了 N 的值以上为15因为某种原因。这是由于二进制数字在再次重复之前所有可能组合的二进制表示。我们知道一个字节的数据是8位；我们知道 [0,15] 中的值将适合其中的一半；例如:
binary byte: hex decimal
0000 0000 0x00 0
...
0000 1111 0xFF 15
在这 15 个不同的 0 和 1 序列之后，这些模式将重复。因此，通过使用上表，您可以将它们转换为二进制表示形式。现在，一旦您检查了 A & B 的表示输入 C以二进制输出并理解我上面提到的结果的 3 个属性；你应该能够设计一个算法来快速计算任何 A 的模数B组合相当容易。要记住的一个技巧是，还有 3 件其他事情需要考虑。首先是什么用户eerokia曾经说过:
"In particular, modulo with a power of 2 can be replaced by a bitwise operations."
接下来是偶数或奇数的值，因为偶数和奇数情况确实呈现出不同的 A mod B 模式。什么时候B < A .
我已经为您提供了一些信息工具供您开始使用，但其余的我会留给您，包括转换 A 的任务。 , B , 和 C值转化为二进制表示。
一旦你知道 A 的二进制模式和 B根据他们的输入 C输出并且您了解逻辑门的真值表 - 运算符，例如 And - & , Or - | , Nand - (!&) , Nor - (!|) , Xor - ^ Xnor - (!^)和 Not - !以及赞美(~) .您应该能够高效地设计算法。
关于c++ - 是否可以在不必计算 A/B 的情况下有效地计算 A % B？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55573924/