Java BigInteger 實現高精度斐波那契數列：突破 long 型別限制計算第 100 項

為什麼需要高精度？

斐波那契數列增長極快：

• F(47) = 2,971,215,073 > Integer.MAX_VALUE (21億)
• F(93) = 12,200,160,415,121,876,738 > Long.MAX_VALUE (9.22×10¹⁸)
• F(100) = 354,224,848,179,261,915,075 (21位數字)

long 只能算到第 92 項，BigInteger 理論無上限（受限於內存）。

完整實現代碼

import java.math.BigInteger;

public class FibonacciBigInteger {
    public static void main(String[] args) {
        for (int i = 1; i <= 100; i++) {
            System.out.println("第 " + i + " 項: " + fibonacci(i));
        }
    }

    /**
     * 迭代法計算斐波那契數列 (O(n) 時間, O(1) 空間)
     * @param n 項數 (從 1 開始)
     * @return BigInteger 結果
     */
    public static BigInteger fibonacci(long n) {
        if (n <= 2) {
            return BigInteger.ONE; // F(1)=1, F(2)=1
        }
        
        BigInteger prev = BigInteger.ONE;  // F(n-2)
        BigInteger curr = BigInteger.ONE;  // F(n-1)
        BigInteger next = BigInteger.ZERO;
        
        for (long i = 3; i <= n; i++) {
            next = prev.add(curr); // F(n) = F(n-2) + F(n-1)
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

關鍵技術點解析

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

public static BigInteger fibonacciFastDoubling(long n) {
    if (n <= 1) return BigInteger.valueOf(n);
    
    // 快速雙倍法公式：
    // F(2k) = F(k) * [2*F(k+1) - F(k)]
    // F(2k+1) = F(k+1)² + F(k)²
    return fibonacciPair(n).first;
}

private static Pair fibonacciPair(long n) {
    if (n == 0) return new Pair<>(BigInteger.ZERO, BigInteger.ONE);
    
    Pair p = fibonacciPair(n >> 1); // n/2
    BigInteger a = p.first;  // F(k)
    BigInteger b = p.second; // F(k+1)
    
    BigInteger c = a.multiply(b.shiftLeft(1).subtract(a)); // F(2k)
    BigInteger d = a.multiply(a).add(b.multiply(b));       // F(2k+1)
    
    if ((n & 1) == 0) {
        return new Pair<>(c, d);
    } else {
        return new Pair<>(d, c.add(d));
    }
}

性能對比：n=1,000,000 時，迭代法需百萬次循環，快速雙倍法僅需 ~20 次遞歸（log₂n）。

應用場景擴展

• 密碼學：大素數生成、RSA 密鑰計算
• 組合數學：卡特蘭數、大數階乘、組合數 C(n,k)
• 金融計算：高精度利率複利、貨幣換算無誤差
• 科學計算：天文數字、物理常數高精度運算

避坑指南

1. 不要用 new BigInteger("1") 創建常量：使用 BigInteger.ONE、BigInteger.ZERO、BigInteger.TEN
2. 字符串構造器指定基數：new BigInteger("FF", 16) 解析十六進制
3. 除法精度：divide(divisor, scale, RoundingMode.HALF_UP) 必須指定精度與舍入模式
4. 性能敏感場景：考慮 MutableBigInteger (內部類) 或專用庫如 Apache Commons Math

BigInteger 讓 Java 輕鬆突破基本類型限制，處理任意大小整數運算，是高精度計算領域的基石工具。