快速计算 n!mod m 其中 m 是素数? [英] Fast way to calculate n! mod m where m is prime?

问题描述

我很好奇是否有好的方法可以做到这一点.我目前的代码是这样的:

I was curious if there was a good way to do this. My current code is something like:

def factorialMod(n, modulus):
    ans=1
    for i in range(1,n+1):
        ans = ans * i % modulus    
    return ans % modulus

不过好像很慢！

我也无法计算 n！然后应用素数模数，因为有时 n 大到 n！明确计算是不可行的.

I also can't calculate n! and then apply the prime modulus because sometimes n is so large that n! is just not feasible to calculate explicitly.

我还遇到了http://en.wikipedia.org/wiki/Stirling%27s_approximation 并想知道这是否可以以某种方式在这里使用?

I also came across http://en.wikipedia.org/wiki/Stirling%27s_approximation and wonder if this can be used at all here in some way?

或者，我如何在 C++ 中创建一个递归的、记忆化的函数?

Or, how might I create a recursive, memoized function in C++?

推荐答案

将我的评论扩展到一个答案:

Expanding my comment to an answer:

是的，有更有效的方法可以做到这一点.但它们非常混乱.

Yes, there are more efficient ways to do this. But they are extremely messy.

所以除非你真的需要额外的性能，否则我不建议尝试实现这些.

关键是要注意模数(本质上是除法)将成为瓶颈操作.幸运的是，有一些非常快速的算法可以让您对同一数字执行多次取模.

The key is to note that the modulus (which is essentially a division) is going to be the bottleneck operation. Fortunately, there are some very fast algorithms that allow you to perform modulus over the same number many times.

• 使用乘法的不变整数除法
• 蒙哥马利减少

这些方法速度很快，因为它们基本上消除了模数.

These methods are fast because they essentially eliminate the modulus.

仅这些方法就可以给您带来适度的加速.为了真正高效，您可能需要展开循环以实现更好的 IPC:

Those methods alone should give you a moderate speedup. To be truly efficient, you may need to unroll the loop to allow for better IPC:

像这样:

ans0 = 1
ans1 = 1
for i in range(1,(n+1) / 2):
    ans0 = ans0 * (2*i + 0) % modulus    
    ans1 = ans1 * (2*i + 1) % modulus    

return ans0 * ans1 % modulus

但考虑到奇怪的迭代次数并将其与我上面链接的方法之一结合起来.

but taking into account for an odd # of iterations and combining it with one of the methods I linked to above.

有些人可能会争辩说循环展开应该留给编译器.我会反驳说，编译器目前还不够聪明，无法展开这个特定的循环.仔细看看，你就会明白为什么.

Some may argue that loop-unrolling should be left to the compiler. I will counter-argue that compilers are currently not smart enough to unroll this particular loop. Have a closer look and you will see why.

请注意，尽管我的回答与语言无关，但它主要适用于 C 或 C++.

Note that although my answer is language-agnostic, it is meant primarily for C or C++.

这篇关于快速计算 n!mod m 其中 m 是素数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！