N을 효율적으로 계산하는 방법! 고정 소수점 빅넘버 라이브러리를 사용하시나요?

문제:

N을 계산하는 효율적인 방법을 결정하세요! (N 계승) 고정 소수점 큰 숫자 라이브러리를 사용하여 정밀도 손실이 없습니다. 구체적으로 다음 공식을 찾으세요.

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

솔루션:

1. Compute T1:

   T1 = T2 * N!

   어디엔! 다음 공식을 사용하여 결정됩니다.

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

   이를 통해 N! T1에서.

2. 소수 i에 대한 지수 e를 계산합니다.

   e = sum(j=1,2,3,4,5,...) of (4N/(i^j))-(2N/(i^j)) )

   여기서 i는 임의의 소수 <= 4N
   입니다. j는 i^j <=인 임의의 정수입니다. 4N

3. T2 계산:

   T2 = multiplication(i=all primes<=4N) of [i^e]

   여기서 e는 2단계에서 계산된 지수입니다.

신규 코드 조각 방정식:

// edit beg:
// Sorry, forget to copy sorted list of all primes up to max n here it is
// end of table is marked with 0
// Primes are in DWORDs so they only 4Byte per number
// so the table is very small compared with lookup table for the same max n!
// and also primes are needed for many other routines in bignum
// can compute n! for n <= max prime in table
DWORD _arithmetics_primes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,0};
// edit end.

longnum fact(const DWORD &x)
    {
    if (x<=4)
        {
        if (x==4) return 24;
        if (x==3) return  6;
        if (x==2) return  2;
        if (x==1) return  1;
        if (x==0) return  1;
        }
    int N4,N2,p,i,j,e; longnum c,pp;
    N4=(x>>2)<<2;
    N2=N4>>1;
    c=fact(N2); c*=c;                 // c=((2N)!)^2;
    for (i=0;;i++)                    // c*= T2
        {
        p=_arithmetics_primes[i];
        if (!p) break;
        if (p>N4) break;
        for (e=0,j=N4;j;e+=j&1,j/=p);
        if (e)                        // c*=p^e
            {
            if (p==2) c<<=e;
            else for (pp=p;;)
                {
                if (int(e&1)) c*=pp;
                e>>=1; if (!e) break;
                pp*=pp;
                }
            }
        }
    for (i=N4+1;i<=x;i++) { c*=i; } c.round();
    return c;
    }

시간 측정:


N!
Time (ms)



1!
0.001


2!
0.000


3!
0.000


4!
0.006


5!
0.006


6!
0.007


7!
0.005


8!
0.006


9!
0.007


10!
0.008


11!
0.012


12!
0.013


13!
0.014


14!
0.016


15!
0.014


16!
0.015


17!
0.017


18!
0.019


19!
0.016


20!
0.017


21!
0.019


22!
0.021


23!
0.023


24!
0.025


25!
0.027


26!
0.029


27!
0.032


28!
0.034


29!
0.037


30!
0.039


31!
0.034


32!
0.037


33!
0.039


34!
0.041


35!
0.039


36!
0.041


37!
0.044


38!
0.046


39!
0.041


40!
0.044


41!
0.046


42!
0.049


43!
0.048


44!
0.050


45!
0.054


46!
0.056


47!
0.056


48!
0.060


49!
0.063


50!
0.066


51!
0.065


52!
0.069


53!
0.072


54!
0.076


55!
0.077


56!
0.162


57!
0.095


58!
0.093


59!
0.089


60!
0.093


61!
0.098


62!
0.096


63!
0.090


64!
0.100


65!
0.104


66!
0.111


67!
0.100


68!
0.121


69!
0.109


70!
0.119


71!
0.104


72!
0.124


73!
0.113


74!
0.118


75!
0.118


76!
0.123


77!
0.129


78!
0.133

79



위 내용은 N을 효율적으로 계산하는 방법! 고정 소수점 빅넘버 라이브러리를 사용하시나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!