相关疑难解决方法(0)

我很好奇是否有一个很好的方法来做到这一点.我目前的代码是这样的:

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++中创建一个递归的,memoized函数？

我有一个定点bignumber库,想要实现快速阶乘,没有精度损失.

在纸上做了一些数学技巧后,我得到了这个公式:

(4N)!=((2N)!).((2N)!).{ (2N+1).(2N+3).(2N+5)...(4N-1) }.(2^N)/(N!)

这已经非常快了,并且通过一些编程技巧,复杂性接近~ O(log(n)).

要清楚,我目前的实现是:

//---------------------------------------------------------------------------
longnum fact(const DWORD &x,longnum &h) // h return (x>>1)! to speed up computation
    {
    if (x==0) { h=1; return  1; }
    if (x==1) { h=1; return  1; }
    if (x==2) { h=1; return  2; }
    if (x==3) { h=1; return  6; }
    if (x==4) { h=2; return 24; }
    int N4,N2,N,i; longnum c,q;
    N=(x>>2);
    N2=N<<1;
    N4=N<<2;
    h=fact(N2,q);                                          // get 2N! and N!
    c=h*h; for (i=(N2+1)|1;i<=N4;i+=2) c*=i; c/=q;         // c= …