Tôi có thư viện điểm cố định và muốn triển khai giai thừa nhanh chóng mà không bị mất chính xác.Chính xác nhanh bigint giai thừa
Sau một số thủ thuật toán trên giấy Tôi có công thức này:
(4N)!=((2N)!).((2N)!).{ (2N+1).(2N+3).(2N+5)...(4N-1) }.(2^N)/(N!)
này đã khá nhanh, và với một số thủ thuật lập trình phức tạp gần kề ~ O(log(n)).
Để được rõ ràng, thực hiện hiện tại của tôi là thế này:
//---------------------------------------------------------------------------
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);
}
//---------------------------------------------------------------------------
Bây giờ câu hỏi của tôi:
Có cách nào nhanh để có được
N!từ thuật ngữ này:T1 = { (2N+1).(2N+3).(2N+5)...(4N-1) }?Đã được trả lời.
Vì vậy, để được rõ ràng, tôi cần phải giải nén chưa biết thuật ngữ này:
T2 = (4N)!/(((2N)!).((2N)!))
vậy:
(4N)! = (((2N)!).((2N)!)).T2
Điều này sẽ giúp rất nhiều bởi vì sau đó nó sẽ không cần thiết để tính .../(N!) cho giai thừa.
Thuật ngữ T1 luôn là số nguyên-phân huỷ trong tự như thế này:
T1 = T2 * N!
Cuối cùng, nó đánh tôi :) Tôi đã làm một chương trình nhỏ cho số nguyên tố phân hủy của giai thừa và sau đó đột nhiên tất cả trở nên rõ ràng hơn nhiều:
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
sau khi phân tích các số mũ thủ thời hạn T2 (phần còn lại sau khi thừa nửa^2) tôi lấy được công thức cho họ:
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)))
- nơi nhân là qua tất cả
primes <= 4N - nơi sumation là cho đến khi
i^j <= 4N
Vấn đề là các bộ phận 4N/(i^j) và 2N/(i^j) phải được thực hiện trong toán số nguyên để họ không thể được đơn giản hóa dễ dàng.
Vì vậy, tôi có một câu hỏi khác:
Làm thế nào tôi có thể tính toán này:
exponent(i) = sum(j=1,2,3,4,5,...) of (N/(i^j))một cách hiệu quả?ilà bất kỳ giá trị nào tại đói<=N. Nó phải dễ dàng.
Bây giờ tôi tính toán số mũ e cho Thủ i bên trong hạn T2(N) như thế này (nhưng điều này là quá phức tạp cho hương vị của tôi):
for (e=0,a=N/i,b=(N>>1)/i;(a)||(b);e+=a-b-b,a/=i,b/=i);
... Tôi sẽ cố gắng thực hiện T2 vào fact(x) và so sánh tốc độ ...
Mã này có vẻ thực sự phức tạp. Có gì sai với vòng lặp O (n)? –
@CarlNorum thats chính xác những gì tôi đã suy nghĩ. * "Sau khi một số thủ đoạn meth tôi nhận được công thức [...] và với một số thủ thuật lập trình phức tạp gần O (nlogn)" * 'cho (dài dài int i = 1; i <= n; ++ i) {n * = i; } 'Whats sai với điển hình cho vòng lặp O (n) thực hiện? – Manu343726
xin lỗi sai lầm của tôi nó phải là O (log (n)) sử dụng phân khu này của N để tính toán 40! nó sử dụng 20! và 10! , để tính 20! nó sử dụng 10! và 5! ... và vân vân. để tính 100! bạn chỉ cần 5 lần thu thập thay vì 99 trong trường hợp O (n) – Spektre