Tính giai thừa của số nguyên lớn

Angels fall first – 16 Jul 09

Tính giai thừa số lớn (Big Factorial)

Tính giai thừa số lớn (Big Factorial) (Ngày cập nhật cuối: 18/05/2009) Chủ đề bài báo: Tính giai thừa số lớn, C/C++, thuật toán. Bài toán tính giai thừa là một trong các ba…

Cảm ơn bạn nhưng thuật toán này mình đã đọc qua và có vẻ như không tính được đến 1 tỷ giai thừa. Dù sao cũng cảm ơn

(10^9)!=10^10^9.932763139878869 wtf

Stirling's approximation

In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of n. It is named after James Stirling, though it was first stated by Abraham de Moivre. The version of the formula typically used in applications is (in big O notation, as n → ∞ {\displaystyle n\to \infty } ), or, by changing the base of the logarithm (for ins...

Swing factorial (không phải Java Swing à)

Đặt swing(n) = n! / ((n DIV 2)!)^2, vậy (2n)! = n!^2 * swing(2n) (cũng như với (2n+1)!) Ta thấy cũng khá giống C(n, n DIV 2). Thật vậy, swing(n) luôn là số nguyên.

Vậy swing(n) có gì đặc biệt? Các thuật toán nhân nâng cao sẽ chỉ hoạt động tốt khi hai thừa số có độ lớn tương đương nhau. Vì vậy, chỉ tiếp cận n! là rất khó khăn.

Đặt e_p(n) là số mũ của thừa số nguyên tố p trong pt của n. Vậy e_p(swing(n)) = sigma((n/p^i) MOD 2). Khi đó ta có thể tính swing(n) bằng cách tính riêng từng thừa số một rồi chia để trị.

Bây giờ là làm sao để dùng lại swing(n DIV 2) chứ bỏ hết thừa số 2 rất dễ khi bạn dùng biểu diễn nhị phân.

Không ai cần tính 1 tỉ giai thừa một cách chính xác cả, có phải đề là tính n! MOD M không?

Không ai cần tính 1 tỉ giai thừa một cách chính xác cả, có phải đề là tính n! MOD M không?

Mình biết, nhưng mà thầy dạy môn thực hành của mình có ra đề này để kiểm tra bạn à

Swing factorial (không phải Java Swing à)

Đặt swing(n) = n! / (n DIV 2)!, vậy (2n)! = n!^2 * swing(2n) (cũng như với (2n+1)!) Ta thấy cũng khá giống C(n, n DIV 2). Dễ nhận ra rằng swing(n) luôn là số nguyên.

Vậy swing(n) có gì đặc biệt? Các thuật toán nhân nâng cao sẽ chỉ hoạt động tốt khi hai thừa số có độ lớn tương đương nhau. Vì vậy, chỉ tiếp cận n! là rất khó khăn.

Đặt e_p(n) là số mũ của thừa số nguyên tố p trong pt của n. Vậy e_p(swing(n)) = sigma((n/p^i) MOD 2). Khi đó ta có thể tính swing(n) bằng cách tính riêng từng thừa số một rồi chia để trị.

Bây giờ là làm sao để dùng lại swing(n DIV 2) chứ bỏ hết thừa số 2 rất dễ khi bạn dùng biểu diễn nhị phân.

Bạn có thể nói kỹ hơn được không, sigma là hàm gì?

oops e_p(swing(n)) = sigma(i=1…inf) (n DIV p^i MOD 2).

Do e_p(a/b) = e_p(a) - e_p(b)
nên e_p(swing(n)) = e_p(n!) - 2e_p((n DIV 2)!)
= sigma(i=1…inf) (n DIV p^i) - 2sigma(i=1…inf) (n DIV 2 DIV p^i)
= sigma(i=1…inf) (n DIV p^i - 2 * n DIV p^i DIV 2) (*)
mà a MOD b = a - a DIV b * b (định nghĩa phép chia) nên suy ra đpcm.

(*): Với b, c nguyên >= 2:
a/b/c = a/c/b <=> (a DIV b + eps1) / c = (a DIV c + eps2) / b với 0 <= eps1, eps2 < 1
<=> a DIV b / c + eps1 / c = a DIV c / b + eps2 / b
<=> a DIV b DIV c + e1 = a DIV c DIV b + e2
Ta có e2, e1 < 1 nên rút phần nguyên suy ra a DIV b DIV c = a DIV c DIV b.

n DIV (a*b) =? n DIV a DIV b.

Và tại sao hai thừa số phải có số chữ số tương đương (chênh nhau khoảng vài lần là tối đa)? Karatsuba, Toom-Cook và FFT đều là chia để trị. Khi thừa số đủ nhỏ thì ta đặt tính bt O(n^2) sẽ nhanh hơn, nhưng với chênh lệch lớn thì gộp lại cả quá trình thì số phép nhân kiểu này là quá nhiều.
Chữ số không nhất thiết phải theo hệ thập phân, mà nhanh nhất là 2^32-phân & dễ code nhất là 10^9-phân.

using System.Numerics.BigInteger;