为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

当年话下 2019-11-29 09:40:29
我很好奇是否有一个很好的方法可以做到这一点。我当前的代码是这样的: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 ++中创建一个递归的,记忆化的函数?
查看完整描述

3 回答

?
慕尼黑5688855

TA贡献1848条经验 获得超2个赞

将我的评论扩展为答案:


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


因此,除非您确实需要额外的性能,否则我建议您不要尝试实现这些性能。


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


使用乘法按不变整数进行除法

蒙哥马利减少

这些方法之所以快速,是因为它们基本上消除了模量。


单独使用这些方法应该可以使您获得适度的加速。为了真正高效,您可能需要展开循环以实现更好的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

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


有人可能会认为循环展开应该留给编译器。我会反驳说,编译器目前还不够智能,无法展开这个特定的循环。仔细看看,您会明白为什么。


请注意,尽管我的回答与语言无关,但主要是针对C或C ++的。


查看完整回答
反对 回复 2019-11-29
?
江户川乱折腾

TA贡献1851条经验 获得超5个赞

如果要计算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)))


查看完整回答
反对 回复 2019-11-29
  • 3 回答
  • 0 关注
  • 975 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信