algorithm - 实现模运算的更好方法(算法问题)

Question

我最近一直在尝试实现模幂运算器。我正在用 VHDL 编写代码，但我正在寻找更具算法性质的建议。模幂运算器的主要组件是一个模乘法器，我也必须自己实现它。我对乘法算法没有任何问题 - 它只是加法和移位，我已经很好地弄清楚了我所有变量的含义，这样我就可以在相当合理的时间内进行乘法。

我遇到的问题是在乘法器中实现模运算。我知道执行重复减法会起作用，但也会很慢。我发现我可以移动模数以有效地减去模数的大倍数，但我认为可能还有更好的方法来做到这一点。我使用的算法是这样的(奇怪的伪代码如下):

result,modulus : integer (n bits) (previously defined)
shiftcount : integer (initialized to zero)
while( (modulus<result) and  (modulus(n-1) != 1) ){
     modulus = modulus << 1
     shiftcount++
}
for(i=shiftcount;i>=0;i--){
     if(modulus<result){result = result-modulus}
     if(i!=0){modulus = modulus >> 1}
}

那么...这是一个好的算法，或者至少是一个好的起点？维基百科并没有真正讨论实现模运算的算法，每当我尝试在其他地方搜索时，我都会发现非常有趣但极其复杂(而且通常不相关)的研究论文和出版物。如果有一种我没有看到的明显的实现方法，我将非常感谢您提供一些反馈。

Answer 1

老实说，我不确定您在那里计算的是什么。您谈论模运算，但通常模运算是在两个数字之间 a和 b ，其结果是除a的余数通过 b . a在哪里和 b在你的伪代码中......？

无论如何，也许这会有所帮助:a mod b = a - floor(a / b) * b .

我不知道这是否更快，这取决于您是否可以比很多减法更快地进行除法和乘法。

另一种加速减法的方法是使用二进制搜索。如果你想要a mod b , 你需要减去 b来自 a直到 a小于 b .所以基本上你需要找到 k这样:

a - k*b < b, k is min

找到这个 k 的一种方法是线性搜索:

k = 0;
while ( a - k*b >= b )
    ++k;

return a - k*b;

但您也可以对其进行二进制搜索(只运行了一些测试，但它对所有测试都有效):

k = 0;
left = 0, right = a
while ( left < right )
{
    m = (left + right) / 2;
    if ( a - m*b >= b )
       left = m + 1;
    else
       right = m;
}

return a - left*b;

我猜二分查找解决方案在处理大数字时是最快的。

如果要计算a mod b并且只有 a是一个大数字(您可以将 b 存储在原始数据类型上)，您可以更快地做到这一点:

for each digit p of a do
    mod = (mod * 10 + p) % b
return mod

这是可行的，因为我们可以写 a作为a_n*10^n + a_(n-1)*10^(n-1) + ... + a_1*10^0 = (((a_n * 10 + a_(n-1)) * 10 + a_(n-2)) * 10 + ...

我认为二分查找正是您要找的东西。