使用Binet公式计算斐波那契偶数和结果偏差1的问题排查

你用Binet公式结合斐波那契数列每第三项为偶数的特性计算小于4000000的偶数项和，结果比正确值多1，核心原因就是浮点数精度不足，具体拆解如下：

问题根源 #

• float类型的精度局限：float只有6-7位有效数字，你手动赋值的sqrt5、goldenRatio都是近似值，本身就存在误差。随着n增大，Math.pow会把这个误差指数级放大，导致计算出的斐波那契数偏离真实值。比如某个偶数项的计算值刚好比真实值大0.5以上，Math.round就会把它进位成大1的数，累加后总和就多了1。
• Binet公式的误差积累：公式中Math.pow(reciprocalGoldenRaio, nth)这一项，当n增大时绝对值趋近于0，但float的精度不足以准确表示这个极小值，残留的误差会干扰最终结果的计算，进一步加剧数值偏差。

修正方案 #

1. 提升浮点数精度 #

把所有float类型换成double，double有15-17位有效数字，能大幅降低精度误差。同时不要手动输入近似值，直接用计算得到的精确值：

public static final double sqrt5 = Math.sqrt(5);
public static final double goldenRatio = (1 + sqrt5) / 2;
public static final double reciprocalGoldenRatio = (1 - sqrt5) / 2;

2. 优化循环逻辑 #

原循环for (int i = 0; i < 4_000_000; i += 3)完全没必要，斐波那契数列增长极快，远没到i=400万时数值就会超过400万。改成当计算值超过阈值时直接终止循环：

long sum = 0;
int n = 0;
while (true) {
  long number = binetsFormula(n);
  if (number >= 4_000_000L) {
    break;
  }
  sum += number;
  n += 3;
}

修正后的完整代码 #

/*
  通过Binet公式和斐波那契数列每第三项为偶数的特性计算
*/

public class Optimised002 {
  public static void main(String[] args) {
    long sum = 0;
    int n = 0;
    while (true) {
      long number = binetsFormula(n);
      if (number >= 4_000_000L) {
        break;
      }
      sum += number;
      n += 3;
    }
    System.out.println(sum);
  }

  public static final double sqrt5 = Math.sqrt(5);
  public static final double goldenRatio = (1 + sqrt5) / 2;
  public static final double reciprocalGoldenRatio = (1 - sqrt5) / 2;

  public static long binetsFormula(int nth) {
    return Math.round((Math.pow(goldenRatio, nth) - Math.pow(reciprocalGoldenRatio, nth)) / sqrt5);
  }
}

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