斐波那契数列 long[] 数组在索引 92 后抛出负数

Question

我正在测试此代码以将斐波那契数列插入 long[] 数组：

public class Test {
    public static void Fibonacci(int n){
        long[] array = new long[n];
        array[0]=1;
        for (int i = 1; i < n; i++) {
            if (i==1) {
                array[i]=i;
            }
            else {
                array[i] = array[i-2] + array[i-1];
            }
        }
        System.out.println(array[n-3]+"    "+array[n-2]); // verify sum
        System.out.println(array[n-1]);
    }
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        System.out.print("Insert Fibonacci sequence index: ");
        int n = scan.nextInt();

        Fibonacci(n);
    }
}

然而，在位置 92 之后，它开始抛出错误或负数。我正在使用这个 Fibonacci Calculator 来验证数字，直到 92 它是正确的。我在这里看到了一些关于这个问题的问题，大多数答案都说它是关于整数溢出的，你应该使用我正在使用的 long。

第93个数是否超过了长型的限制？我应该使用什么来达到 100 或更大的数字并仍然使用数组来管理它？

Answer 1

您运行陷入数字溢出。使用任意精度算术来解决这个问题：将 long[] 替换为 BigInteger[]，并将公式更改为方法调用，例如

array[0] = 1;
...
array[i] = array[i-2] + array[i-1];

变成

array[0] = BigInteger.ONE;
...
array[i] = array[i-2].add(array[i-1]);

Answer 2

从this table开始，第92个斐波那契数是7540113804746346429，第93个是12200160415121876738。

一个Javalong的range是–9223372036854775808到9223372036854775807

将斐波那契数列中的第 93 个数字与 long 可以采用的最大值进行比较，揭示发生了什么：

9223372036854775807   -- max long value
7540113804746346429   -- 92nd number in Fibonacci sequence (works)
12200160415121876738  -- 93rd number in Fibonacci sequence (doesn't work)

您可以考虑使用 BigInteger 来存储您的序列号。

Answer 3

您超出了 long 的范围。您可以使用 BigInteger（并从循环中提取 array[1]）；某事¹ 喜欢

public static void fibonacci(int n) {
    BigInteger[] array = new BigInteger[n];
    array[0] = array[1] = BigInteger.ONE;

    for (int i = 2; i < n; i++) {
        array[i] = array[i - 2].add(array[i - 1]);
    }
    System.out.println(array[n - 3] + "    " + array[n - 2]); // verify sum
    System.out.println(array[n - 1]);
}

^{1_{此外，请遵循Java命名规则。方法名称以小写字母开头，Fibonacci 看起来像 class 名称。}}

Answer 4

第 93 个数字大于 2^63 - 1（java 中最大可能的 long 值）是正确的。这意味着在第 92 次迭代之后变量将溢出。如果你想使用更大的数字，你应该查看 BigInteger

斐波那契数列 long[] 数组在索引 92 后抛出负数

Fibonacci sequence long[] array throws negative numbers after index 92

java

arrays

fibonacci