快速的方法来计算N！模m其中m为质数？ [英] Fast way to calculate n! mod m where m is prime?
问题描述
我很好奇，如果有一个很好的办法做到这一点。我现在的code是这样的：
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
但似乎很慢！
But it seems quite slow!
我也无法计算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.
我也碰到<一href="http://en.wikipedia.org/wiki/Stirling%27s_approximation">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?
或者说，还有可能创建一个递归，memoized在C ++函数？
Or, how might I create a recursive, memoized function in C++?
推荐答案
扩大我的评论来回答：
是的，有更有效的方法来做到这一点。 的但是他们都非常凌乱。的
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.
- Division by Invariant Integers using Multiplication
- Montgomery Reduction
这些方法是快速的，因为他们从根本上杜绝模量。
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！模m其中m为质数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
