CODEWITHSUNDEEP
recursiondynamic-programmingfibonacci
Alexander Mills
Alexander Mills

Reputation: 100000

Fibonacci linear time recursion

Why does this work only up to n=90 or so? Trying to calculate the 94th fibonacci number gives the incorrect result. Same thing happens if I use the Integer class instead of Long.

import java.util.HashMap;

public class FDP {

    private static HashMap<Long, Long> fib = new HashMap<Long, Long>();

    private static Long calculateFib(Long n) {

        if(fib.get(n)==null){
            Long temp = calculateFib(n-1) + calculateFib(n-2);
            fib.put(n, temp);
            return temp;
        }
        else{
            return fib.get(n);
        }
    }
    }

    public static void main(String[] args) {
        fib.put(0L, 0L);
        fib.put(1L, 1L);
        System.out.println(calculateFib(90L)); //success
        System.out.println(calculateFib(94L)); //garbage??
    }
}

here is a list of the Fibonacci numbers:

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html

Upvotes: 0

Views: 232

Answers (2)

Christian Fries
Christian Fries

Reputation: 444

You reach the limitations of the type Long (64bit), use BigInteger instead

Upvotes: 1

user
user

Reputation: 745

Its an overflow. The 94th Fibonacci number is: 19740274219868223167 Long.MAX_VALUE is: 9223372036854775807

19740274219868223167 - 9223372036854775807 > 0

You can use BigInteger to handle numbers with arbitrary length.

Upvotes: 1

Related Questions