实现一个模运算（算法问题）更好的方法 [英] Better ways to implement a modulo operation (algorithm question)

问题描述

我一直在试图近日来实现模块化求幂。我写了code在VHDL，但是我正在寻找一个更自然算法的建议。模块化求幂的主要成分是一种模块化的乘数，我也必须执行自己。我还没有与乘法算法 - 它只是增加和移动情况，我做搞清楚什么我所有的变量都意味着这样我可以在一个时间pretty的合理数量乘以一个好工作的任何问题。

I've been trying to implement a modular exponentiator recently. I'm writing the code in VHDL, but I'm looking for advice of a more algorithmic nature. The main component of the modular exponentiator is a modular multiplier which I also have to implement myself. I haven't had any problems with the multiplication algorithm- it's just adding and shifting and I've done a good job of figuring out what all of my variables mean so that I can multiply in a pretty reasonable amount of time.

这是我遇到的问题是与实施的乘数模运算。我知道，重复进行增减的工作，但它也将是缓慢的。我发现，我可能会改变模量，有效地减去模大倍数，但我觉得可能仍然是更好的方式来做到这一点。我使用该算法是这样的（奇怪的伪code所示）：

The problem that I'm having is with implementing the modulus operation in the multiplier. I know that performing repeated subtractions will work, but it will also be slow. I found out that I could shift the modulus to effectively subtract large multiples of the modulus but I think there might still be better ways to do this. The algorithm that I'm using works something like this (weird pseudocode follows):

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}
}

所以...这是一个很好的算法，或者至少是一个良好的开端？维基百科并没有真正讨论的算法来实现模运算，每当我试图寻找别的地方，我觉得非常有趣，但令人难以置信的复杂的（而且通常不相关的）研究报告和出版物。如果有实现这一点，我没有看到，我真的AP preciate一些反馈，一个明显的方式。

So...is this a good algorithm, or at least a good place to start? Wikipedia doesn't really discuss algorithms for implementing the modulo operation, and whenever I try to search elsewhere I find really interesting but incredibly complicated (and often unrelated) research papers and publications. If there's an obvious way to implement this that I'm not seeing, I'd really appreciate some feedback.

推荐答案

我不知道你在计算什么就有什么是诚实的。请您谈一下模运算，但通常一个模操作是两个数字之间 A 和 B ，其结果是除以剩余 A 按 B 。在哪里 A 和 B 在你的伪code ...？

I'm not sure what you're calculating there to be honest. You talk about modulo operation, but usually a modulo operation is between two numbers a and b, and its result is the remainder of dividing a by b. Where is the a and b in your pseudocode...?

不管怎样，也许这会帮助： A MOD B = A - 地面（A / B）* B

Anyway, maybe this'll help: a mod b = a - floor(a / b) * b.

我不知道这是更快与否，这取决于你是否可以做除法和乘法比很多减法快。

I don't know if this is faster or not, it depends on whether or not you can do division and multiplication faster than a lot of subtractions.

的另一种方式，以加快减法的方法是使用二进制搜索。如果你想modb ，你需要减去 B 从 A 直到 A 比 B 小。所以基本上你需要找到 K 这样：

Another way to speed up the subtraction approach is to use binary search. If you want a mod b, you need to subtract b from a until a is smaller than b. So basically you need to find k such that:

A - K * B＆LT; B，K是最小

要找到这个 K 的一种方式是线性搜索：

One way to find this k is a linear search:

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

return a - k*b;

不过，你也可以二进制搜索它（只跑了几个测试，但它的工作在所有的）：

But you can also binary search it (only ran a few tests but it worked on all of them):

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;

我猜二进制搜索解决方案，在用大数字打交道是最快的。

I'm guessing the binary search solution will be the fastest when dealing with big numbers.

如果你想计算modb 只有 A 是一个大的数字（可以存储 B 上的原始数据类型），你可以做到这一点甚至更快：

If you want to calculate a mod b and only a is a big number (you can store b on a primitive data type), you can do it even faster:

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 + ...

This works because we can write a as 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 + ...

我觉得二进制搜索是你要寻找的，虽然。

I think the binary search is what you're looking for though.

这篇关于实现一个模运算（算法问题）更好的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！