猿问
下载APP

快速计算n!mod m m是素数?

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


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 ++中创建一个递归的,记忆化的函数?


当年话下
浏览 436回答 3
3回答

123456qqq

将我的评论扩展为答案:是的,有更有效的方法可以做到这一点。但是它们非常混乱。因此,除非您确实需要额外的性能,否则我建议您不要尝试实现这些性能。关键是要注意,模数(本质上是一个除法)将成为瓶颈操作。幸运的是,有一些非常快速的算法可以让您多次执行相同次数的模数。使用乘法按不变整数进行除法蒙哥马利减少这些方法之所以快速,是因为它们基本上消除了模量。单独使用这些方法应该可以使您获得适度的加速。为了真正高效,您可能需要展开循环以实现更好的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 ++的。

绝地无双

n可以任意大好吧,n不能任意大-如果n >= m,那么n! ≡ 0 (mod m) (由于m阶乘的定义是因素之一)。假设n << m您需要一个确切的值,据我所知,您的算法将无法更快地获得。但是,如果n > m/2使用,则可以使用以下标识(威尔逊定理 -谢谢@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乘法,加上模逆:def factorialMod(n,模数):&nbsp; &nbsp; ans = 1&nbsp; &nbsp; 如果n <=模数// 2:&nbsp; &nbsp; &nbsp; &nbsp; #正常计算阶乘(range()的正确参数是唯一的)&nbsp; &nbsp; &nbsp; &nbsp; 对于范围(1,n + 1)中的i:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans =(ans * i)%模量&nbsp; &nbsp;&nbsp; &nbsp; 其他:&nbsp; &nbsp; &nbsp; &nbsp; #大号n的花式方法&nbsp; &nbsp; &nbsp; &nbsp; 对于范围(n + 1,模数)中的i:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans =(ans * i)%模量&nbsp; &nbsp; &nbsp; &nbsp; ans = modinv(ans,模数)&nbsp; &nbsp; &nbsp; &nbsp; ans = -1 * ans +模数&nbsp; &nbsp; 返回ans模数我们可以用另一种方式改写上面的等式,这可能会或可能不会更快一点。使用以下身份:(图片)我们可以将等式改写为n!≡-[(n + 1)* ... *(m-2)*(m-1)] -1(mod m)n!≡-[(n + 1-m)* ... *(m-2-m)*(m-1-m)] -1(mod m)&nbsp; &nbsp; &nbsp; &nbsp;(术语相反)n!≡-[(-1)*(-2)* ... *-(mn-2)*-(mn-1)] -1(mod m)n!≡-[(1)*(2)* ... *(mn-2)*(mn-1)*(-1)(mn-1) ] -1(mod m)n!≡[(mn-1)!] -1 *(-1)(mn)(mod m)可以用Python编写,如下所示:def factorialMod(n,模数):&nbsp; &nbsp; ans = 1&nbsp; &nbsp; 如果n <=模数// 2:&nbsp; &nbsp; &nbsp; &nbsp; #正常计算阶乘(range()的正确参数是唯一的)&nbsp; &nbsp; &nbsp; &nbsp; 对于范围(1,n + 1)中的i:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans =(ans * i)%模量&nbsp; &nbsp;&nbsp; &nbsp; 其他:&nbsp; &nbsp; &nbsp; &nbsp; #大号n的花式方法&nbsp; &nbsp; &nbsp; &nbsp; 对于范围(1,模-n)中的i:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans =(ans * i)%模量&nbsp; &nbsp; &nbsp; &nbsp; ans = modinv(ans,模数)&nbsp; &nbsp; &nbsp; &nbsp; #由于m为奇数素数,如果n为偶数,则(-1)^(mn)= -1,如果n为奇数,则+1&nbsp; &nbsp; &nbsp; &nbsp; 如果n%2 == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans = -1 * ans +模数&nbsp; &nbsp; 返回ans模数如果您不需要确切的值,那么生活会变得容易一些-您可以使用斯特林近似法来计算O(log n)时间上的近似值(使用平方求幂)。最后,我应该提到,如果这是时间紧迫的,并且您正在使用Python,请尝试切换到C ++。从个人的经验,你应该期望关于速度的订单数量级增加或更多,只是因为这正是那种CPU绑定紧环原生地编译代码的过人之处在(也,无论出于何种原因,GMP似乎比Python的Bignum更加精细)。

慕雪9262066

如果要计算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)))。
打开App,查看更多内容
随时随地看视频慕课网APP
我要回答