algorithm - 快速计算 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

n can be arbitrarily large

嗯，n不能任意大-如果n >= m , 然后 n! ≡ 0 (mod m) (因为 m 是因子之一，根据阶乘的定义)。

---

假设n << m并且您需要一个精确 值，据我所知，您的算法再快不过了。但是，如果 n > m/2 ，您可以使用以下身份(Wilson's theorem - 谢谢@Daniel Fischer!)

将乘法次数限制在大约 m-n

(m-1)! ≡ -1 (mod m)
1 * 2 * 3 * ... * (n-1) * n * (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m)
n! * (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m)
n! ≡ -[(n+1) * ... * (m-2) * (m-1)]-1 (mod m)

这为我们提供了一种计算 n! (mod m) 的简单方法在m-n-1乘法，加上一个 modular inverse :

def factorialMod(n, modulus):
    ans=1
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus   
    else:
        #Fancypants method for large n
        for i in range(n+1,modulus):
            ans = (ans * i) % modulus
        ans = modinv(ans, modulus)
        ans = -1*ans + modulus
    return ans % modulus

---

我们可以用另一种方式重新表述上面的等式，它可能会或可能不会执行得稍微快一些。使用以下身份:

我们可以将等式改写为

n! ≡ -[(n+1) * ... * (m-2) * (m-1)]-1 (mod m)
n! ≡ -[(n+1-m) * ... * (m-2-m) * (m-1-m)]-1 (mod m)
       (reverse order of terms)
n! ≡ -[(-1) * (-2) * ... * -(m-n-2) * -(m-n-1)]-1 (mod m)
n! ≡ -[(1) * (2) * ... * (m-n-2) * (m-n-1) * (-1)(m-n-1)]-1 (mod m)
n! ≡ [(m-n-1)!]-1 * (-1)(m-n) (mod m)

这可以用 Python 编写如下:

def factorialMod(n, modulus):
    ans=1
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus   
    else:
        #Fancypants method for large n
        for i in range(1,modulus-n):
            ans = (ans * i) % modulus
        ans = modinv(ans, modulus)

        #Since m is an odd-prime, (-1)^(m-n) = -1 if n is even, +1 if n is odd
        if n % 2 == 0:
            ans = -1*ans + modulus
    return ans % modulus

---

如果您不需要精确 值，生活会变得更轻松一些 - 您可以使用 Stirling's approximation计算 O(log n) 中的近似值时间 (使用 exponentiation by squaring )。

---

最后，我要提一下，如果时间紧迫并且您使用的是 Python，请尝试切换到 C++。根据个人经验，您应该期望速度有一个数量级或更多的增长，因为这正是 native 编译代码优于的 CPU 绑定(bind)紧密循环 >(此外，无论出于何种原因，GMP 似乎比 Python 的 Bignum 更精细)。