5
我有一个定点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