gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:24:28 25 4
gpt4 key购买 nike

我最近一直在尝试实现模幂运算器。我正在用 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}
}

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

最佳答案

老实说,我不确定您在那里计算的是什么。您谈论模运算,但通常模运算是在两个数字之间 ab ,其结果是除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 + ...

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

关于algorithm - 实现模运算的更好方法(算法问题),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2773628/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com