时间戳

首页 > 解决方案 > 使用 Big Integer 进行更高值的斐波那契计算的无限循环？

java - 使用 Big Integer 进行更高值的斐波那契计算的无限循环？

问题描述

我编写了一个程序来计算斐波那契数列，它对于较低的值可以正常工作，但对于较高的值它会陷入无限循环。这是代码，

public static BigInteger fib(BigInteger n) {
    // ...
    // ...
    
    if(n.intValue() == 0){
      return BigInteger.valueOf(0);
    }
    
    if(n.intValue() == 1){
      return BigInteger.valueOf(1);
    }
    
    if(n.intValue() > 0){
        return calp(n);
      }
    return caln(n);
  }
  
  static BigInteger calp(BigInteger n){
   
    BigInteger prev1 = BigInteger.valueOf(1);
    BigInteger prev2 = BigInteger.valueOf(0);
    
    int i=2;        
    while(i <= n.intValue()){
            BigInteger curr = BigInteger.valueOf(0);

       curr= curr.add(prev1);
       curr = curr.add(prev2);
      prev2=prev1;
      prev1=curr;
      i++;
    }
    return prev1;
  }

对于值 1234567，它陷入了无限循环。有人可以向我解释为什么吗？

标签： javabiginteger

解决方案

您的程序没有陷入循环，它只是很慢。

斐波那契数列呈指数增长。第 1234567 个斐波那契数约为

7.84468471036091254428371992991734957118403295643488... × 10^258008

用这么大的数字进行计算会花费很多时间，特别是如果您使用效率低下的 Fib(n+1) = Fib(n) + Fib(n-1) 算法。

使用基于双重身份的方法会更快。这个想法是，当给定 Fib(n) 时，您可以直接计算 Fib(2n)，跳过所有中间值。细节当然要复杂一些。这是我找到的一篇好文章https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling

推荐阅读