Tính Giai Thừa Dùng Số Nguyên Lớn - Programming - Dạy Nhau Học

Có thể bạn quan tâm

programmingalgorithm MrEZ (Nguyễn Quốc Hoàng) December 18, 2018, 8:10pm #1 Mọi người có ai biết cách tính giai thừa của một số nguyên lớn (1 tỷ) không? Mình đang gặp bài này và đang bí, tìm trên google không ra thuật toán. Mong mọi người giúp namhaiha0308 (Hà Hải Nam) May 20, 2018, 11:28am #3 Tính giai thừa số lớn (Big Factorial)Tính giai thừa số lớn (Big Factorial) (Ngày cập nhật cuối: 18/05/2009) Chủ đề bài báo: Tính giai thừa số lớn, C/C++, thuật toán. Bài toán tính giai thừa là một trong các ba… MrEZ (Nguyễn Quốc Hoàng) May 20, 2018, 9:23pm #4 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 phamvandung (Pham Van Dung) May 20, 2018, 11:04pm #5 (10^9)!=10^10^9.932763139878869 wtf

Stirling's approximationIn 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...3 Likes rogp10 (rogp10) May 21, 2018, 9:25am #6 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.4 Likes noname00 (HK boy) May 21, 2018, 1:42am #7 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?3 Likes MrEZ (Nguyễn Quốc Hoàng) May 21, 2018, 3:37am #8

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 à MrEZ (Nguyễn Quốc Hoàng) May 21, 2018, 3:59am #9

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ì? rogp10 (rogp10) April 20, 2019, 4:18am #10 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ênmà 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.3 Likes noz1995 (Trần Hoàn) May 21, 2018, 1:32pm #11

3 Likes rogp10 (rogp10) April 20, 2019, 4:19am #12 ^ lắc đầu

chỉ cài sẵn O(n^2) thôi.1 Like kisuluoibieng (Tên Gì Cũng Được) April 20, 2019, 4:50am #13 O(n) loop 1 tỷ thì đã là một chuyện khó cứ coi như đủ thời gian để chờ đợi thì kết quả của nó ghi ra file text thuần cũng nặng vài GB đề bài tập này chẳng có gì thực tế cả, khè sv là chính\nếu là kiểm tra trên giấy thì cứ loop với array mà phang thôi1 Like