Java中基于公式实现BigInteger版斐波那契数列第n项的精度问题求助

I'm trying to calculate the nth Fibonacci number using Binet's formula, but I'm getting incorrect results for larger indices (e.g., index 100). Here's my code:

public BigInteger getFibonacciNumber(int index) {
    final Instant start = Instant.now();
    if (index == 0) return BigInteger.ZERO;
    if (index == 1) return BigInteger.ONE;
    BigDecimal phi1 = new BigDecimal("5");
    phi1 = phi1.sqrt(MathContext.DECIMAL128);
    BigDecimal phi2 = phi1.subtract(BigDecimal.ONE);
    phi1 = phi1.add(BigDecimal.ONE);
    phi1 = phi1.divide(new BigDecimal("2"), 8, RoundingMode.HALF_EVEN);
    phi2 = phi2.divide(new BigDecimal("2"), 8, RoundingMode.HALF_EVEN);
    BigDecimal p1 = phi1.pow(index);
    BigDecimal p2 = phi2.pow(index);
    p1 = p1.subtract(p2);
    BigDecimal sqrt5 = BigDecimal.valueOf(Math.sqrt(5));
    p1 = p1.divide(sqrt5, 8, RoundingMode.HALF_EVEN);
    Log.infov( "Fibonacci number for index {0} computed in {1}", index, Duration.between(start, Instant.now()));
    return p1.toBigInteger();
}

When calculating the 100th Fibonacci number, the expected result is 354224848179261915075, but my code returns 354224875546939407559. I suspect the issue is with BigDecimal precision or rounding settings, but I'm not sure how to fix it. Can anyone help me figure out a solution?

Solution: Fix Precision Issues in Binet's Formula Implementation #

Great question—this is a classic precision problem with Binet's formula when using limited floating-point arithmetic. Let's break down what's causing the error and how to fix it:

What's Wrong with Your Current Code #

1. Too Little Precision in Intermediate Steps: Using a fixed scale of 8 in your divide calls chops off most significant digits early on. When you raise these truncated values to the 100th power, those small errors get amplified exponentially, leading to a wildly incorrect final result.
2. Inaccurate √5 Calculation: Calling BigDecimal.valueOf(Math.sqrt(5)) converts a double-precision value (which only has ~15-17 reliable digits) to BigDecimal. For the 100th Fibonacci number, we need far more precision to capture the exact integer when rounding.
3. Unnecessary Precision Loss: While you start with MathContext.DECIMAL128 for the first sqrt(5) calculation, you immediately reduce precision by dividing with a scale of 8. This negates the initial high-precision calculation.

Fixed Code with Explanations #

Here's a revised version that maintains sufficient precision throughout all operations:

public BigInteger getFibonacciNumber(int index) {
    final Instant start = Instant.now();
    if (index == 0) return BigInteger.ZERO;
    if (index == 1) return BigInteger.ONE;

    // Use DECIMAL128 for 34 significant digits—plenty for index up to ~1000
    MathContext highPrecision = MathContext.DECIMAL128;
    
    // Calculate √5 once with full precision, no double conversions
    BigDecimal sqrt5 = new BigDecimal("5").sqrt(highPrecision);
    
    // Compute phi and psi using the high-precision context
    BigDecimal phi = sqrt5.add(BigDecimal.ONE).divide(new BigDecimal("2"), highPrecision);
    BigDecimal psi = sqrt5.subtract(BigDecimal.ONE).divide(new BigDecimal("2"), highPrecision);
    
    // Raise to the nth power with the same precision to avoid errors
    BigDecimal phiPower = phi.pow(index, highPrecision);
    BigDecimal psiPower = psi.pow(index, highPrecision);
    
    // Subtract and divide by √5, keeping full precision
    BigDecimal numerator = phiPower.subtract(psiPower);
    BigDecimal result = numerator.divide(sqrt5, highPrecision);
    
    Log.infov("Fibonacci number for index {0} computed in {1}", index, Duration.between(start, Instant.now()));
    
    // Round to the nearest integer properly—critical for exact results
    return result.setScale(0, RoundingMode.HALF_UP).toBigInteger();
}

Key Improvements #

• Uniform High Precision: Every arithmetic operation uses MathContext.DECIMAL128, which ensures we don't lose digits at any step. This 34-digit precision is more than enough for Fibonacci numbers up to the 1000th term (which has ~209 digits).
• Accurate √5: We calculate sqrt5 directly via BigDecimal.sqrt() instead of converting from a double, which eliminates a major source of error.
• Proper Rounding: Using setScale(0, RoundingMode.HALF_UP) ensures we round the final decimal value to the correct integer, which is essential for getting the exact Fibonacci number.

Quick Note for Very Large Indices #

If you need to calculate Fibonacci numbers beyond index ~1000, Binet's formula will start to struggle even with DECIMAL128 precision. For those cases, switch to an iterative approach or matrix exponentiation using BigInteger—these methods are both faster and completely accurate for any index.

内容的提问来源于stack exchange，提问作者Simon B