如何有效率計算N！使用定點大數庫？

問題：

決定計算 N 的有效方法！ （N 階乘）使用定點大數庫沒有精度損失。具體來說，找到以下公式：

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

解：

1. 計算T1：

   T1 = T2 * N!

   哪裡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 是任意素數 j 是任意整數， j 是任意整數，使得i^j

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 &amp;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&amp;1,j/=p);
        if (e)                        // c*=p^e
            {
            if (p==2) c<<=e;
            else for (pp=p;;)
                {
                if (int(e&amp;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中文網其他相關文章！