java - 斐波那契数列中 f(93) 处的数字为负值，怎么办？

Question

我正在尝试打印最多“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

这是因为数据类型吗？我还应该使用什么数据类型来打印最多 N 个数字的斐波那契数列？ N 可以是 [0..10,000,000] 范围内的任意整数。

Answer 1

您遇到了一个 integer overflow :

 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)，因为即使 x 的适度值 93 也会产生一个太大的结果，任何 Java 原语都无法表示。