So berechnen Sie N effizient! Verwenden Sie eine Festkomma-Bignumber-Bibliothek?

Problem:

Bestimmen Sie eine effiziente Methode zur Berechnung von N! (N-Fakultät) ohne Präzisionsverlust unter Verwendung einer Festkomma-BigNumber-Bibliothek. Suchen Sie insbesondere nach der Formel für:

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

Lösung:

1. Berechnen Sie T1:

   T1 = T2 * N!

   wobei N! wird mit der folgenden Formel ermittelt:

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

   Dies ermöglicht die Berechnung von N! aus T1.

2. Berechnen Sie den Exponenten e für die Primzahl i:

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

   wobei i eine beliebige Primzahl <= 4N ist
   und j ist eine beliebige ganze Zahl, so dass i^j <= 4N

3. T2 berechnen:

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

   wobei e der in Schritt 2 berechnete Exponent ist.

Code-Snippet für Neu Gleichung:

// 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;
    }

Zeitmessungen:


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



Das obige ist der detaillierte Inhalt vonSo berechnen Sie N effizient! Verwenden Sie eine Festkomma-Bignumber-Bibliothek?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!