1
\$\begingroup\$

I've been tasked with making a fast Fibonacci recursive method that uses BigInteger to calculate REALLY big numbers. However, to calculate numbers past 30 it takes almost a MINIMUM of 60 seconds each time. Unfortunately, I have to use some type of recursion in my method even though the iteration way is WAY faster.

public static BigInteger theBigFib(int b) {
        BigInteger[] a = new BigInteger[100000];
        if(b < 2) {
            return BigInteger.ONE;
        }

        if(a[b] != null) {
            return a[b];
        }

        a[b] = theBigFib(b - 1).add(theBigFib(b - 2));
        return a[b];
    }

I have a loop in my main that runs the the method from values 20 to 30.

public static void main(String[] args) {
        final long start = System.nanoTime();
        for (int i = 20; i <= 30; i++) {
            System.out.println(theBigFib(i));
        }
    //  System.out.println(theBigFib(35));  Takes way too long
        final long end = System.nanoTime();
        System.out.println("This program took " + ((end - start) / 1000000000) + " second(s) to run.");
    }

Here are the results from the console. This is from the 2nd time running it which the first time came out to be 443 seconds.

10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
This program took 227 second(s) to run.

I find this topic of recursion and program efficiency to be super interesting so I'm open to all suggestions. Only thing I cannot use is external libraries. :)

\$\endgroup\$
  • \$\begingroup\$ This code is broken if b>100000 \$\endgroup\$ – Oscar Smith Jan 30 '18 at 6:02
  • \$\begingroup\$ Search for "tail recursion". I am not sure if it is supported in Java nowerdays though. \$\endgroup\$ – shallowThought Jan 30 '18 at 8:15
  • \$\begingroup\$ Can you elaborate on "I have to use some type of recursion"? Specifically, why? \$\endgroup\$ – vnp Jan 30 '18 at 8:38
  • \$\begingroup\$ It's just part of the assignment specifications of my instructor. \$\endgroup\$ – Ozymandias Jan 30 '18 at 17:34
1
\$\begingroup\$

This line causes a lot of unnecessary calls:

a[b] = theBigFib(b - 1).add(theBigFib(b - 2));

For each second call you get 4 calls, 8 calls, 16 calls etc.

You can still use recursion, but if you add a second argument to your method, you can pass both current and 'intermediate' result (Fn-1 and Fn-2) and prevent the double call. Example using int (you can rewrite it to BigInteger)

public class Fib {


    public static void main(String[] args) {
        System.out.println(fib(10));

    }

    private static int fib(int n) {

        return fibInternal(0,1,n);

    }

    //Recursion here :)
    private static int fibInternal(int a, int b, int n) {

        if (n<=1) 
            return b;
        else 
            return fibInternal(b, (a+b), n-1);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the clarification this is more along the lines of what I was thinking of doing but wasn't sure how to relate it together!! \$\endgroup\$ – Ozymandias Jan 30 '18 at 17:37
1
\$\begingroup\$

Every time you call theBigFib, you allocate a new BigInteger[] a object. As a result, you're not caching any previous results.

\$\endgroup\$
  • \$\begingroup\$ Ah yes thanks. Wasn't sure where to put that array when I made the method! \$\endgroup\$ – Ozymandias Jan 30 '18 at 6:49
1
\$\begingroup\$

Building on the previous answer, to cache the result, you should have the cache be a static class variable. This small change makes your code run from 20 to 10000 in 1 second.

import java.math.BigInteger;

public class test{
    private static BigInteger[] fibCache = new BigInteger[100000];
    public static BigInteger theBigFib(int b) {
        if(b < 2) {
            return BigInteger.ONE;
        }

        if(fibCache[b] != null) {
            return fibCache[b];
        }

        fibCache[b] = theBigFib(b - 1).add(theBigFib(b - 2));
        return fibCache[b];
    }
    public static void main(String[] args) {
        final long start = System.nanoTime();
        for (int i = 20; i <= 10000; i++) {
            System.out.println(theBigFib(i));
        }
    //  System.out.println(theBigFib(35));  Takes way too long
        final long end = System.nanoTime();
        System.out.println("This program took " + ((end - start) / 1000000000) + " second(s) to run.");
    }
}
\$\endgroup\$
0
\$\begingroup\$
public static BigInteger theBigFib(int b) {
        BigInteger[] a = new BigInteger[100000];
        if(b < 2) {
            return BigInteger.ONE;
        }

As others have noted, you can improve this by moving a from being a local variable to a static class variable.

You can also get rid of the conditional with a static initializer.

    private static final BigInteger[] fibCache = new BigInteger[100000];

    static {
        fibCache[0] = BigInteger.ONE;
        fibCache[1] = BigInteger.ONE;
    }

    public static BigInteger theBigFib(int b) {
        if (fibCache[b] == null) {
            fibCache[b] = theBigFib(b - 1).add(theBigFib(b - 2));
        }

        return fibCache[b];
    }

Given the way that you call it (always with increasing numbers), this will have the effect of saving the conditional check on every call after the first. I.e. after you've cached 2 and 3, that conditional is never true again because you never recurse that far down.

This also makes it easier to switch from the version of the Fibonacci sequence that starts 1, 1 to the variant that starts 0, 1.

A side benefit is that it will return an array index out of bounds if called with a negative value. The original code would have incorrectly returned BigInteger.ONE in that case.

I would declare fibCache as final, since you will never overwrite it with a different array. That may also allow for some compiler optimizations, as it can use the pointer rather than the handle to refer to it. You only need to leave it mutable if you want to resize the array later.

Since you return the same thing in both the null and not null cases, I would prefer to check for null and recurse. The other way you have to write the return twice. This way you only write it once. Sure, it's only one line of code, but it's one line in a method that only needs five even with whitespace.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.