Java ExecutorService to solve Recursive Fibonacci Series

I need to find out the number based on some index in the Fibonacci Series recursively using threads and I tried the following code, but the program never ends. Please let me know if I am missing something.

Code:

  import java.math.BigInteger;
  import java.util.concurrent.*;

  public class MultiThreadedFib {

    private ExecutorService executorService;

    public MultiThreadedFib(final int numberOfThreads) {
      executorService = Executors.newFixedThreadPool(numberOfThreads);
    }

    public BigInteger getFibNumberAtIndex(final int index) 
      throws InterruptedException, ExecutionException {

      Future<BigInteger> indexMinusOne = executorService.submit(
        new Callable<BigInteger>() {
          public BigInteger call() 
          throws InterruptedException, ExecutionException {
            return getNumber(index - 1);
          }
      });

      Future<BigInteger&g开发者_开发知识库t; indexMinusTwo = executorService.submit(
        new Callable<BigInteger>() {
          public BigInteger call() 
          throws InterruptedException, ExecutionException {
            return getNumber(index - 2);
          }
      });

      return indexMinusOne.get().add(indexMinusTwo.get());
    }

    public BigInteger getNumber(final int index) 
    throws InterruptedException, ExecutionException {
      if (index == 0 || index == 1)
        return BigInteger.valueOf(index);

      return getFibNumberAtIndex(index - 1).add(getFibNumberAtIndex(index - 2));
    }
  }

Fixed it (Thanks to fiver)

Instead of calling getNumber(int) from the call method, I am calling to a dynamic programming algorithm that computes the number at that index.

The code for that is:

public class DynamicFib implements IFib {

private Map<Integer, BigInteger> memoize = new HashMap<Integer, BigInteger>();

public DynamicFib() {
  memoize.put(0, BigInteger.ZERO);
  memoize.put(1, BigInteger.ONE);
}

public BigInteger getFibNumberAtIndex(final int index) {

  if (!memoize.containsKey(index))
    memoize.put(index, getFibNumberAtIndex(index - 1).add(getFibNumberAtIndex(index - 2)));

  return memoize.get(index);
  }
}

This recursion will overflow the stack very fast. This is because you are computing lower fibonacci numbers over and over again - exponentially many number of times.

One effective way to avoid that is to use memoized recursion (a dynamic programming approach)

Basically use a static array to hold the already computed fibonacci numbers and whenever you need one, take it from the array, if it's already computed. If not, then compute it and store it in the array. This way each number will be computed only once.

(You can use other data structure instead of array, of course, i.e. hashtable)

What you are doing is replacing simple recursion with recursion via threads / tasks.

Until you get to the fib(0) and fib(1) cases, each task submits two more tasks, and then waits for them to complete. While it is waiting, it is still using a thread. Since the thread pool is bounded, you soon get to the point where calls to submit block ... and the whole computation locks up.

In addition to that, you've got a bug in indexMinusTwo which would result in the computation giving the wrong answer.

But still the recursive multithreaded procedure takes much longer than the memoized recursive non-multithreaded one.. any tip to improve performance?

Even assuming that you "fixed" the above problem (e.g. by using an unbounded thread pool) there is no way that you will be able to do a multi-threaded version of fibonacci that performs better than a single-threaded version that uses memoization. The computation is simply not suited to parallelization.

Threads work best when you have independant tasks to perform. The fibonacci series by definition does not have any degrees of parallelism. Each f(n) depends on the previous two values. As such it is not possible to calculate f(n) faster using multiple threads than using one (unless you have an inefficient algo)

The only thing you could make parallel potentially the + operation for large numbers, however this is likely to be a) complex b) difficult to make faster than the single threaded solution.

The fastest/simplest way to calculate fibonacci numbers is to use a loop in one thread. You don't need to use recusrion or memorize values.