計算 Ln(N!) 的高效算法：避免階乘溢出的對數求和法與 Stirling 公式近似

問題背景：為什麼直接計算 N! 再取對數不可行？

原代碼嘗試通過遞歸計算階乘 factorial(N) 再調用 Math.log()，存在嚴重缺陷：

1. 整數溢出：int 最大值 2,147,483,647，13! = 6,227,020,800 已超出範圍；long 也僅能到 20!
2. 遞歸邏輯錯誤：原代碼 factorial(N-2) * factorial(N-1) 邏輯錯誤，應為 N * factorial(N-1)
3. 性能低下：重複計算導致指數級時間複雜度
4. 精度問題：大數轉 double 再取對數會丟失精度

正確方法一：對數求和法（精確計算）

利用對數性質：ln(N!) = ln(1) + ln(2) + ... + ln(N)

public class LogFactorialCalculator {
    
    /**
     * 計算 ln(N!) - 精確對數求和法
     * @param n 非負整數
     * @return ln(n!) 的值
     */
    public static double logFactorialSum(int n) {
        if (n < 0) throw new IllegalArgumentException("n 必須非負");
        if (n <= 1) return 0.0;  // ln(0!) = ln(1!) = 0
        
        double sum = 0.0;
        for (int i = 2; i <= n; i++) {
            sum += Math.log(i);
        }
        return sum;
    }
    
    /**
     * 計算 ln(N!) - 使用 BigDecimal 高精度（教學演示）
     */
    public static BigDecimal logFactorialBigDecimal(int n, int scale) {
        if (n < 0) throw new IllegalArgumentException("n 必須非負");
        if (n <= 1) return BigDecimal.ZERO;
        
        BigDecimal sum = BigDecimal.ZERO;
        MathContext mc = new MathContext(scale, RoundingMode.HALF_UP);
        for (int i = 2; i <= n; i++) {
            // 注意：BigDecimal 無內置 ln，需自行實現或使用近似
            // 此處僅演示思路，實際建議用 double 足夠
            sum = sum.add(new BigDecimal(Math.log(i)), mc);
        }
        return sum;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("請輸入 N (非負整數): ");
        int n = scanner.nextInt();
        
        try {
            double result = logFactorialSum(n);
            System.out.printf("ln(%d!) = %.10f%n", n, result);
            
            // 驗證：小數值可用 BigInteger 計算階乘再取對數對比
            if (n <= 20) {
                BigInteger fact = BigInteger.ONE;
                for (int i = 2; i <= n; i++) fact = fact.multiply(BigInteger.valueOf(i));
                double verify = Math.log(new BigDecimal(fact).doubleValue());
                System.out.printf("驗證值: %.10f, 差值: %.2e%n", verify, Math.abs(result - verify));
            }
        } catch (IllegalArgumentException e) {
            System.err.println("錯誤: " + e.getMessage());
        }
    }
}

正確方法二：Stirling 公式近似（大 N 高性能）

當 N 很大（如 > 10000）時，求和循環較慢，可使用 Stirling 公式：

ln(N!) ≈ N·ln(N) - N + 0.5·ln(2πN) + 1/(12N) - 1/(360N³) + ...

public static double logFactorialStirling(int n) {
    if (n < 0) throw new IllegalArgumentException("n 必須非負");
    if (n <= 1) return 0.0;
    
    double n_d = n;
    // 基礎 Stirling 公式 + 修正項
    return n_d * Math.log(n_d) - n_d 
         + 0.5 * Math.log(2 * Math.PI * n_d)
         + 1.0 / (12 * n_d)
         - 1.0 / (360 * n_d * n_d * n_d)
         + 1.0 / (1260 * Math.pow(n_d, 5))
         - 1.0 / (1680 * Math.pow(n_d, 7));
}

性能與精度對比測試

結論：N ≤ 10000 推薦求和法（精確、足夠快）；N > 10000 推薦 Stirling 公式（極快、誤差可忽略）。

應用場景拓展

• 組合數計算：ln(C(n,k)) = ln(n!) - ln(k!) - ln((n-k)!) 避免大數溢出
• 概率計算：泊松分布、多項式分布中的階乘項
• 信息論：熵計算 H = -Σ p ln p 常涉及階乘
• 統計檢定：卡方檢定、費雪精確檢定

完整可運行示例（包含輸入驗證與多種算法切換）

public class LnFactorialApp {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("=== ln(N!) 計算器 ===");
        
        while (true) {
            System.out.print("\n請輸入 N (非負整數，輸入 q 退出): ");
            if (!in.hasNextInt()) break;
            
            int n = in.nextInt();
            if (n < 0) {
                System.out.println("錯誤: N 不能為負數");
                continue;
            }
            
            long start, end;
            double result;
            
            // 自動選擇算法
            if (n <= 10000) {
                start = System.nanoTime();
                result = logFactorialSum(n);
                end = System.nanoTime();
                System.out.printf("【精確求和法】ln(%d!) = %.12f (耗時: %.3f ms)%n", 
                                 n, result, (end - start) / 1e6);
            } else {
                start = System.nanoTime();
                result = logFactorialStirling(n);
                end = System.nanoTime();
                System.out.printf("【Stirling近似】ln(%d!) ≈ %.12f (耗時: %.3f ms)%n", 
                                 n, result, (end - start) / 1e6);
                
                // 大數驗證：對比前 10000 項求和 + 其餘近似
                double hybrid = logFactorialSum(10000) + logFactorialStirling(n) - logFactorialStirling(10000);
                System.out.printf("【混合驗證】    ln(%d!) ≈ %.12f (差值: %.2e)%n", 
                                 n, hybrid, Math.abs(result - hybrid));
            }
        }
        System.out.println("程序結束");
    }
    
    // 此處放入 logFactorialSum 和 logFactorialStirling 方法...
}

總結

計算 ln(N!) 的核心原則是避免直接計算 N!。對數求和法提供機器精度的精確結果，適用於中小規模 N；Stirling 公式提供 O(1) 時間複雜度的高精度近似，適用於大規模 N。實際工程中可根據 N 的範圍動態選擇或混合使用，兼顧性能與精度。