Cara Mengira N dengan Cekap! Menggunakan Perpustakaan Nombor Besar Titik Tetap?

Masalah:

Tentukan kaedah yang cekap untuk mengira N! (N faktorial) tanpa kehilangan ketepatan menggunakan perpustakaan nombor besar titik tetap. Secara khusus, cari formula untuk:

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

Penyelesaian:

1. Hitung T1:

   T1 = T2 * N!

   di mana N! ditentukan menggunakan formula berikut:

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

   Ini membolehkan pengiraan N! daripada T1.

2. Kira eksponen e untuk perdana i:

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

   di mana i ialah sebarang perdana <= 4N
   dan j ialah sebarang integer sehingga i^j <= 4N

3. Hitung T2:

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

   di mana e ialah eksponen yang dikira dalam Langkah 2.

Snippet Kod untuk Baharu Persamaan:

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

Sukatan Masa:


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



Atas ialah kandungan terperinci Cara Mengira N dengan Cekap! Menggunakan Perpustakaan Nombor Besar Titik Tetap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!