我正在用C ++编写一个多精度库，使用2 ^ 64的基础，目前我正在研究mod操作。我正在使用Donald E. Knuth 1998年出版的“The Art Of Computer Programming”Vol。 2，第4.3.1节，用于除法，产生商和余数。对于mod操作，我正在执行一个师，最后扔掉了商。虽然如果在C ++中实现Knuth的算法D非常快，并且在每个步骤中对部分除法和并发多精度乘法/减法进行了一些ASM增强，我不确定是否有更好的方法，因为丢掉了一个精心计算的算法结果对我来说似乎没有效率。
不幸的是，不可能摆脱算法D中的部分除法，因为需要部分商来计算余数，通过迭代地从除数中减去部分商和除数的乘积。
我在互联网上寻找替代解决方案，并找到了由Paul Barrett和Peter L. Montgomery撰写的有影响力的论文。然而，他们使用的花哨技巧似乎只有在大量的mod操作连续执行具有相同模数的情况下才能得到回报，因为它们涉及大量的预计算。在模幂运算等复杂操作中就是这种情况，其中单个模数需要几个正方形和乘积的mod。 Barrett从余数的基本定义开始，r = a - b * (a / b)，并将除法改为与b的倒数相乘。然后他提出了一种计算这种乘法的有效方法，如果对于几次类似的计算计算一次倒数，则会得到回报。蒙哥马利将操作数转换为完全不同的残留系统，其中模块化算法很便宜，但是转换的价格是来回的。
此外，两种算法都引入了一些限制，需要满足这些限制才能正确操作。例如，蒙哥马利通常要求操作数是奇数，这在质数的RSA计算中是这种情况，但在一般情况下不能假设。除了这些限制之外，还需要更多的规范化开销。
所以我需要的是一个有效的一次性mod功能，没有开销和特殊限制。因此我的问题是：是否有可能在不首先计算商的情况下计算余数，以比分割更有效的方式？
一个建议是编写一个简单的函数来计算A%B=C并将A，B和C值存储到一个数组中，然后将所有结果存储到一个向量中。然后将它们打印出来以查看所有输入和输出值的关系。
有一件事可以简化一些工作，那就是了解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所说的：
“特别是，功率为2的模数可以用逐位运算代替。”
接下来的是偶数或奇数值，因为偶数和奇数情况确实呈现A mod B时B < A的不同图案。
我已经为您提供了一些信息工具，但其余的我将留给您，包括将A，B和C值转换为二进制表示的任务。
一旦你知道A和B输入的二进制模式根据他们的C输出，你了解逻辑门的真值表 - 运营商，如And - &，Or - |，Nand - (!&)，Nor - (!|)，Xor - ^ Xnor - (!^)和Not - !以及赞美(~) 。您应该能够高效地设计算法。