Recursive Fibonacci using BigInteger in Java

Question

I'm trying to solve a project euler 25 problem in java and since I need something to store numbers with 10000 digits, I'm using BigInteger classes.

So I'm working in some recursive fibonacci sequence using BigIntegers and I'm trying to convert this code:

public int fibonacci(int n)  {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

from this link: Java recursive Fibonacci sequence

to the same code, but using BigIntegers.

So, this is what I have so far:

public static BigInteger fibonacci(BigInteger index) {
    if (index.compareTo(BigInteger.ZERO) == 0)
        return BigInteger.ZERO;
    else if (index.compareTo(BigInteger.valueOf(1)) == 1)
        return BigInteger.ONE;
    else
        return fibonacci(index.subtract(BigInteger.ONE)).add(fibonacci(index.subtract(BigInteger.valueOf(2))));
}

public static int numberOfDigits(BigInteger fibonacci) {
    return Integer.valueOf(fibonacci.toString().length());
}

public static void main(String[] args) {
    long startTime = System.nanoTime();
    for (BigInteger i = new BigInteger("1"); numberOfDigits(fibonacci(i)) <= 1000; i = i.add(BigInteger.ONE))
        System.out.println(" " + i + "  -  " + fibonacci(i) + "  -  " + numberOfDigits(fibonacci(i)));
    long endTime = System.nanoTime();
    long duration = (endTime - startTime);
    System.out.println("Duration: " + duration/1000000 + " ms");
}

When I run it, I get a StackOverFlowError, like this:

Exception in thread "main" java.lang.StackOverflowError
    at java.math.BigInteger.subtract(BigInteger.java:1423)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)

And it repeats I think 1000 times. Well, I have no idea what is wrong, so please can you guys help me? Thank you!

Just convert the program into a non-recursive form. Using DP will make this program a lot faster in addition. Recursion is definitely not the way to go here, as already the `StackOverflowError` indicates. — , Dec 22 '16 at 13:35
You are not supposed to use brute force to solve project Euler problems. Why use BigIntegers ? The point of this problem is not big numbers, it is to find a method which makes the computational time acceptable. Think a bit more about an effective way of limiting the number of calculations and you won't need any fancy class :) — Dese, Dec 22 '16 at 13:37
Thank you guys. Thought recursive was faster, but I'm running it now and I see its way slower. Thanks! — Gabriel Augusto, Dec 22 '16 at 13:43

score 3 · Accepted Answer · edited Mar 06 '17 at 07:31

3

When you use compare() it returns 1 if argument is higher than actual.

So you should change this piece of code:

else if (index.compareTo(BigInteger.valueOf(1)) == 1)

for this:

else if (index.compareTo(BigInteger.valueOf(1)) == 0)

edited Mar 06 '17 at 07:31

eol

23,236
5
46
64

answered Dec 22 '16 at 13:37

Vlad Bochenin

3,007
1
20
33

Thank you very much. Now it's running. Funny thing is that I thought it was going to run faster than the substitute method of Fibonacci, but seems to be way slower. – Gabriel Augusto Dec 22 '16 at 13:44

score 1 · Answer 2 · edited Apr 13 '17 at 12:45

1

Java doesn't deal too well with deep recursion. You should convert to using a loop instead.

Also see this thread on tail recursion: https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all

edited Apr 13 '17 at 12:45

Community

1
1

answered Dec 22 '16 at 13:39

Jilles van Gurp

7,927
4
38
46

This is a good point, some languages can deal with tail recursion without eating up the stack. – weston Dec 22 '16 at 13:40

MatWdo · Answer 3 · 2016-12-22T13:46:57.497

0

I think You have standard problem with recursion... It's a problem with method fibonacci, because You have no places, when this method must return final result, so please check your condition and more about compare in BigInteger. Recommends also read about tail recursion

edited Dec 22 '16 at 13:46

answered Dec 22 '16 at 13:37

MatWdo

1,610
1
13
26

score 0 · Answer 4 · answered Dec 22 '16 at 13:44

You could try to use dynamic programming to reduce space complexity. Something like this should work:

public static BigInteger fibonacci(BigInteger n) {
    if (n.compareTo(BigInteger.valueOf(3L)) < 0) {
        return BigInteger.ONE;
    }
    //Map to store the previous results
    Map<BigInteger, BigInteger> computedValues = new HashMap<BigInteger, BigInteger>();
    //The two edge cases
    computedValues.put(BigInteger.ONE, BigInteger.ONE);
    computedValues.put(BigInteger.valueOf(2L), BigInteger.ONE);
    return fibonacci(n, computedValues);
}

private static BigInteger fibonacci(BigInteger n, Map<BigInteger, BigInteger> computedValues) {
    if (computedValues.containsKey(n))
        return computedValues.get(n);
    BigInteger n1 = n.subtract(BigInteger.ONE);
    BigInteger n2 = n.subtract(BigInteger.ONE).subtract(BigInteger.ONE);
    computedValues.put(n1, fibonacci(n1, computedValues));
    computedValues.put(n2, fibonacci(n2, computedValues));
    BigInteger newValue = computedValues.get(n1).add(computedValues.get(n2));
    computedValues.put(n, newValue);
    return newValue;
}

Recursive Fibonacci using BigInteger in Java

4 Answers4