Java 高精度計算：BigInteger 實現費波那契數列第 100 項

費波那契數列增長極快，第 50 項已超過 long 範圍（9,223,372,036,854,775,807）。Java java.math.BigInteger 提供任意精度整數運算，完美解決大數計算問題。

核心代碼：迭代法 O(n) 時間、O(1) 空間

import java.math.BigInteger;

public class FibonacciBigInteger {
    public static BigInteger fibonacci(int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be positive");
        if (n <= 2) return BigInteger.ONE;
        
        BigInteger prev = BigInteger.ONE;  // F(n-2)
        BigInteger curr = BigInteger.ONE;  // F(n-1)
        
        for (int i = 3; i <= n; i++) {
            BigInteger next = prev.add(curr); // F(n) = F(n-1) + F(n-2)
            prev = curr;
            curr = next;
        }
        return curr;
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 100; i++) {
            System.out.printf("F(%3d) = %s%n", i, fibonacci(i));
        }
    }
}

關鍵點解析

• 不可變性：BigInteger 所有運算返回新對象，prev.add(curr) 不修改原值。
• 常量複用：BigInteger.ONE、BigInteger.ZERO、BigInteger.TEN 避免重複創建。
• 輸出格式：toString() 直接輸出十進制字符串，無科學計數法截斷。

第 100 項結果

F(100) = 354224848179261915075

進階優化：矩陣快速冪 O(log n)

對極大 n（如百萬級），可用矩陣乘冪或快速倍增法：

[F(n+1) F(n)  ]   [1 1]^n
[F(n)   F(n-1)] = [1 0]   

BigInteger 亦支持 modPow、gcd、isProbablePrime 等數論運算，是密碼學、大數計算、組合數學的利器。金融計算請用 BigDecimal（定點小數），避免浮點誤差。