我有一個定點bignumber庫,並希望實現快速因子沒有精度損失。快速確切bigint階乘
後在紙上一些數學技巧,我得到這個公式:
(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= ((2N!)^2)*T1/N!
for (i=N4+1;i<=x;i++) c*=i; c.round(); c<<=N ; // convert 4N! -> x!, cut off precision losses
for (i=(N2+1)|1,N2=x>>1;i<=N2;i++) h*=i; h.round(); // convert 2N! -> (x/2)!, cut off precision losses
return c;
}
//---------------------------------------------------------------------------
longnum fact(const DWORD &x)
{
longnum tmp;
return fact(x,tmp);
}
//---------------------------------------------------------------------------
現在我的問題:
是否有快速的方法來獲得這個長期
N!
:T1 = { (2N+1).(2N+3).(2N+5)...(4N-1) }
?已經回答。
所以要清楚,我需要提取這個未知項:
T2 = (4N)!/(((2N)!).((2N)!))
這樣:
(4N)! = (((2N)!).((2N)!)).T2
這將有很大的幫助,因爲那就不是需要計算.../(N!)
階乘。
的T1
術語總是整數分解成這樣:
T1 = T2 * N!
最後,打我:)我做了一些方案,階乘的素數分解,然後突然一切都變得更加清晰:
4! = 2!.2!.(2^1).(3^1) = 24
8! = 4!.4!.(2^1).(5^1).(7^1) = 40320
12! = 6!.6!.(2^2).(3^1).(7^1).(11^1) = 479001600
16! = 8!.8!.(2^1).(3^2).(5^1).(11^1).(13^1) = 20922789888000
20! = 10!.10!.(2^2).(11^1).(13^1).(17^1).(19^1) = 2432902008176640000
24! = 12!.12!.(2^2).(7^1).(13^1).(17^1).(19^1).(23^1) = 620448401733239439360000
28! = 14!.14!.(2^3).(3^3).(5^2).(17^1).(19^1).(23^1) = 304888344611713860501504000000
32! = 16!.16!.(2^1).(3^2).(5^1).(17^1).(19^1).(23^1).(29^1).(31^1) = 263130836933693530167218012160000000
36! = 18!.18!.(2^2).(3^1).(5^2).(7^1).(11^1).(19^1).(23^1).(29^1).(31^1) = 371993326789901217467999448150835200000000
40! = 20!.20!.(2^2).(3^2).(5^1).(7^1).(11^1).(13^1).(23^1).(29^1).(31^1).(37^1) = 815915283247897734345611269596115894272000000000
分析T2
項的主要指數後(其餘一半階乘後^ 2)我推導公式爲他們:
T2(4N) = multiplication(i=2,3,5,7,11,13,17,...) of (i^sum(j=1,2,3,4,5,...) of (4N/(i^j))-(2N/(i^j)))
- 其中乘法是通過所有
primes <= 4N
- 其中Sumation公司是直到
i^j <= 4N
的問題是,該部門4N/(i^j)
和2N/(i^j)
必須整數運算來完成,使他們不能簡化很容易。
所以我還有一個問題:
我如何計算這個:
exponent(i) = sum(j=1,2,3,4,5,...) of (N/(i^j))
有效?i
是任何素數i<=N
。它應該很容易。
現在我計算指數e
的黃金i
的T2(N)
術語像這裏面的(但這是太複雜,我的口味):
for (e=0,a=N/i,b=(N>>1)/i;(a)||(b);e+=a-b-b,a/=i,b/=i);
...我會努力實現T2
到fact(x)
並比較速度...
這段代碼看起來很複雜。 O(n)循環有什麼問題? –
@CarlNorum這正是我在想什麼。 *「經過一些方法後,我得到了公式[...]並且有一些編程技巧,複雜度接近O(nlogn)」*'for(long long int i = 1; i <= n; ++ i){n * = i; }'典型的循環O(n)實現有什麼問題? – Manu343726
對不起,我的錯誤應該是O(log(n))這個用N的細分來計算40!它使用20!和10! ,來計算20!它使用10!和5! ... 等等。來計算100!你只需要5次遞歸而不是99次O(n)的情況下 – Spektre