Nooblhu Nooblhu - 6 months ago 29
Java Question

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

I'm testing this code to insert the Fibonacci sequence in a long[] array:

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);
}
}


However, after position 92, it starts throwing wrong or negative numbers. I'm using this Fibonacci Calculator to verify the numbers and until 92 it's correct.
I've seen some questions here about this problem and most answers say its about Integer overflow, and that you should use long, which I am using.

Is 93th number over the limit of long type? What should I use instead to reach 100 or bigger numbers and still manage it with an array?

Answer

You are overflowing the range of long. You can use BigInteger (and extract array[1] from the loop); something1 like

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]);
}

1Also, please follow Java naming conventions. Method names start with a lower case letter, Fibonacci looks like a class name.

Comments