斐波纳契系列f(93)处的数值具有负值,怎么样？

Question

我正在尝试将fibonacci系列打印到'N'个数字.所有的工作按照期望直到f(92)但是当我试图得到f(93)的值时,值结果为负:" - 6246583658587674878".这怎么可能？下面的逻辑中有什么错误？

public long fibo(int x){
    long[] arr = new long[x+1];
    arr[0]=0;
    arr[1]=1;
    for (int i=2; i<=x; i++){
        arr[i]=arr[i-2]+arr[i-1];
    }
    return arr[x];
}

f(91) = 4660046610375530309
f(92) = 7540113804746346429    
f(93) = -6246583658587674878

这是因为数据类型吗？我应该用什么数据类型将fibonacci系列打印到N个数字？N可以是[0..10,000,000]范围内的任何整数.

Answer 1

您遇到了整数溢出:

 4660046610375530309 <-- term 91
+7540113804746346429 <-- term 92
====================
12200160415121876738 <-- term 93: the sum of the previous two terms
 9223372036854775808 <-- maximum value a long can store

为了避免这种情况,请使用BigInteger,它可以处理任意数量的数字.
这是您转换为使用的实现BigDecimal:

public String fibo(int x){
    BigInteger[] arr = new BigInteger[x+1];
    arr[0]=BigInteger.ZERO;
    arr[1]=BigInteger.ONE;
    for (int i=2; i<=x; i++){
        arr[i]=arr[i-2].add(arr[i-1]);
    }
    return arr[x].toString();u
}

请注意,返回类型必须是String(或BigInteger),因为即使是适度的值93也会x产生对于任何java基元来说都太大的结果.