快速计算n！mod m m是素数？

Question

我很好奇是否有一个很好的方法可以做到这一点。我当前的代码是这样的：

def factorialMod(n, modulus):

    ans=1

    for i in range(1,n+1):

        ans = ans * i % modulus    

    return ans % modulus

但是似乎很慢！

我也无法计算n！然后应用素数模数，因为有时n太大以至于n！显式计算只是不可行。

我还遇到了http://en.wikipedia.org/wiki/Stirling%27s_approximation，想知道是否可以在某种程度上使用它？

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

Answer 1

将我的评论扩展为答案：是的，有更有效的方法可以做到这一点。但是它们非常混乱。因此，除非您确实需要额外的性能，否则我建议您不要尝试实现这些性能。关键是要注意，模数（本质上是一个除法）将成为瓶颈操作。幸运的是，有一些非常快速的算法可以让您多次执行相同次数的模数。使用乘法按不变整数进行除法蒙哥马利减少这些方法之所以快速，是因为它们基本上消除了模量。单独使用这些方法应该可以使您获得适度的加速。为了真正高效，您可能需要展开循环以实现更好的IPC：像这样：ans0 = 1ans1 = 1for i in range(1,(n+1) / 2):    ans0 = ans0 * (2*i + 0) % modulus        ans1 = ans1 * (2*i + 1) % modulus    return ans0 * ans1 % modulus但考虑到奇数次的迭代，并将其与我上面链接的方法之一结合起来。有人可能会认为循环展开应该留给编译器。我会反驳说，编译器目前还不够智能，无法展开这个特定的循环。仔细看看，您会明白为什么。请注意，尽管我的回答与语言无关，但主要是针对C或C ++的。

Answer 2

如果要计算M = a*(a+1) * ... * (b-1) * b (mod p)，可以使用以下方法，如果我们假设可以进行加，减和乘快速运算（mod p），则运行时复杂度为O( sqrt(b-a) * polylog(b-a) )。为简单起见，假设(b-a+1) = k^2，是一个正方形。现在，我们可以将产品分成k个部分，即M = [a*..*(a+k-1)] *...* [(b-k+1)*..*b]。本产品中的每个因素都具有p(x)=x*..*(x+k-1)适当的形式x。通过使用多项式的快速乘法算法（例如Schönhage–Strassen算法），以分而治之的方式可以找到多项式的系数p(x) in O( k * polylog(k) )。现在，显然有一种算法可以将替换k为相同的k次多项式中的点O( k * polylog(k) )，这意味着我们可以p(a), p(a+k), ..., p(b-k+1)快速计算。C. Pomerance和R. Crandall在“ Prime number”一书中描述了将许多点代入一个多项式的算法。最终，当您拥有这些k值时，可以将它们相乘O(k)并获得所需的值。请注意，我们所有的操作都在执行(mod p)。确切的运行时间为O(sqrt(b-a) * log(b-a)^2 * log(log(b-a)))。