Number at f(93) in fibonacci series has negative value, how?

Question

I am trying to printout fibonacci series upto 'N' numbers. All works as per expectation till f(92) but when I am trying to get the value of f(93), values turns out in negative: "-6246583658587674878". How this could be possible? What is the mistake in the logic below?

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

Is this because of data type? What else data type I should use for printing fibonacci series upto N numbers? N could be any integer within range [0..10,000,000].

Answer 1

You've encountered an 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

To avoid this, use BigInteger, which can deal with an arbitrary number of digits.
Here's your implementation converted to use 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
}

Note that the return type must be String (or BigInteger) because even the modest value of 93 for x produces a result that is too great for any java primitive to represent.

Answer 2

This happened because the long type overflowed. In other words: the number calculated is too big to be represented as a long, and because of the two's complement representation used for integer types, after an overflow occurs the value becomes negative. To have a better idea of what's happening, look at this code:

System.out.println(Long.MAX_VALUE);
=> 9223372036854775807  // maximum long value
System.out.println(Long.MAX_VALUE + 1);
=> -9223372036854775808 // oops, the value overflowed!

The value of fibo(93) is 12200160415121876738, which clearly is greater than the maximum value that fits in a long.

This is the way integers work in a computer program, after all they're limited and can not be infinite. A possible solution would be to use BigInteger to implement the method (instead of long), it's a class for representing arbitrary-precision integers in Java.

Answer 3

As correctly said in above answers, you've experienced overflow, however with below java 8 code snippet you can print series.

Stream.iterate(new BigInteger[] {BigInteger.ZERO, BigInteger.ONE}, t -> new BigInteger[] {t[1], t[0].add(t[1])})
        .limit(100)
        .map(t -> t[0])
        .forEach(System.out::println);