Why is it returning negative numbers past the 47th fibonacci number?

Question

I wrote a program to store Fibonacci numbers and will retrieve the nth Fibonacci number. It works fine until the 50th Fibonacci where it returns a negative number.

getFibonacci(47) returns 1836311903 but
getFibonacci(48) returns -1323752223. Why is this?

public class Fibonacci {
    static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    public static void main(String[] args) {
        int x;
        storeFibonacciNumbers(50);
        System.out.println(getFibonacci(48));
    }

    public static void storeFibonacciNumbers (int n){
        for (int x=1; x <= n; x++ ){
            if(x == 1){
                map.put(x, 0);
            }
            else if (x == 2) {
                map.put(x, x-1);
            }
            else
                map.put(x, map.get(x-1) + map.get(x-2));
        }
    }

    public static long getFibonacci (int x){
        return map.get(x);
    }
}

http://en.wikipedia.org/wiki/Integer_overflow – David Apr 18 '15 at 01:44 — David, Apr 18 '15 at 01:44

score 3 · Answer 1 · answered Apr 18 '15 at 01:45

This is because the maximum value of an Integer has been reached. When you try to add a value to it, it overflows, and "wraps around" to the negative.

An alternative is to use a type that supports higher maximums (e.g. Long).

At some point, you might be forced to switch to types that are more complex, but are built specifically to store very large integers (e.g. BigInteger).

score 2 · Answer 2 · answered Apr 18 '15 at 01:56

In the HashMap you are storing Fibonacci number as a Integer. The maximum value that an Int can hold is 2147483647 (2^31-1) So based on your calculations Fibonacci(47) must exceed that maximum value and overflow is happening.

Change your HashMap value type to Long. It will fix your problem.

score 1 · Answer 3 · answered Apr 18 '15 at 01:49

1

An Integer Overflow is the condition that occurs when the result of an arithmetic operation, such as multiplication or addition, exceeds the maximum size of the integer type used to store it.

answered Apr 18 '15 at 01:49

Tarek

687
5
11

score 0 · Answer 4 · answered Apr 18 '15 at 01:45

0

It's because the int type only goes so high. The max value is 2147483647, at which point it will just start over. You need to use a different datatype, such as a long if you want to represent a bigger number correctly.

answered Apr 18 '15 at 01:45

shieldstroy

1,307
1
10
24

score 0 · Answer 5 · answered Apr 18 '15 at 01:47

0

The max java integer is 2^31-1 or 2147483647. After you reach that value you will start returning negative numbers.

You can use the constant Integer.MAX_VALUE as a way to stop your program once you reach that value.

answered Apr 18 '15 at 01:47

jriccio

3
4

Why is it returning negative numbers past the 47th fibonacci number?

5 Answers5