时间戳

首页 > 解决方案 > 尽管使用 Long 原始类型和 Big Integer，但大斐波那契数列的整数溢出

java - 尽管使用 Long 原始类型和 Big Integer，但大斐波那契数列的整数溢出

问题描述

我正在编写一个程序来打印第 n 个斐波那契数。

方法FIBBO(int n)使用 long 和 BigInteger 类型的组合来存储斐波那契运算的结果。当认为prev+next>Long.MAX_VALUE使用big_flag时，假设该方法切换到使用 BigInteger 。但是，该程序仅在我在第二个循环中使用 Integer.MAX_VALUE 时才有效。

当我使用 Long.MAX_VALUE 时，big_flag 的第二个循环现在永远不会触发，无论 n 的值有多大，我只会得到垃圾值。我不明白为什么当我使用 Long.MAX_VALUE 时我的溢出逻辑从未被激活。

import java.util.*;
import java.math.*;

public class fibbo_iteration{
    public static void main(String argss[])
    {
        BigInteger result;                      
        Scanner input=new Scanner(System.in);
        int n=0;                                
        System.out.println("Enter number of terms for fibbonacci sequence");
        n=input.nextInt();
        if(n<0){
            System.out.println("Fibbonaci sequence cannot be generated for the entered negative value");
            System.exit(1);
        }
        
        result=fibbo_iteration.FIBBO(n);        //call
        System.out.println(result.toString());  
    }
    static BigInteger FIBBO(int n)
    {
        // variables
        long sum=0L,prev=0L,next=1L;
        BigInteger big_prev=new BigInteger("0"),big_next=new BigInteger("0"),big_sum=new BigInteger("0");
        boolean big_flag=false;
    
            for(int i=0;i<n;i++){
                if(big_flag){
                    // System.out.println(big_sum.toString()); to use when printing a series upto n 
                    big_prev=big_next;
                    big_next=big_sum;
                    big_sum=big_prev.add(big_next);
                }
                else if(prev+next>Long.MAX_VALUE){   // ***The program works abolutely correct if i replace LONG.MAX_VALUE with Integer.MAX_Value***
                    big_prev=new BigInteger(String.valueOf(prev));
                    big_next=new BigInteger(String.valueOf(next));
                    big_sum=big_prev.add(big_next);
                    big_flag=true;  // this is supposed to signal the switch to BigInteger
                    System.out.println("Value exceeds Long");
                }   
                else{
                    if(i==1){   // this if block accomodates the eccentricity of starting the fibbonaci sequence  
                        sum=1L;
                        continue;
                    }   
                sum=prev+next;
                prev=next;
                next=sum;
                System.out.println(sum);
                }
            }
        return big_flag==true?big_sum:new BigInteger(String.valueOf(sum));
    }
}

标签： javalong-integerbigintegerinteger-overflowbigint

解决方案

Long 的最大值实际上是该类型的最大值。任何高于此的计算都会给你......你显然没想到的好结果。这种支票prev+next>Long.MAX_VALUE是无稽之谈。它永远不会是真实的。

应该使您的程序正常工作的一些更改是：prev > Long.MAX_VALUE - next

如果您想更详细地了解，可以使用我编写的比较和调试，在 if 块中放置一个断点。尝试查看 的值prev+next。看看它是如何变成负数的。这是因为你已经达到了超出long可以存储的值。

推荐阅读