CODEWITHSUNDEEP
javamultithreadingfibonacci
Riporter
Riporter

Reputation: 390

calculate fibonacci with threads in java

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> 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));
  }
}

im gonig to calculate fibonacci sequence with java threads in order to decrease calculating time but answer is wrong Although its seem to be true. another problem is out of memory exception that occurred in starting new threads for number 35 to the top. please help me many regards...

Upvotes: 1

Views: 3014

Answers (3)

John B
John B

Reputation: 32969

You need to limit the number of threads. I would recommend that you only use two threads: one for finding index - 1, the other for finding index - 2. When each of these methods recursively find the previous index - 1 and index - 2, do this in the existing thread.

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

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

Finally, I believe the first two Fibonacci numbers (the root numbers) are 1 & 2, not 0 & 1. Notice that I changed getNumber to return index + 1 and recursively call itself rather than going back to the service.

1 + 2 = 3 + 2 = 5 ...

0 + 1 = 1 (error)

Another problem this alg has is that is does a lot of work twice because it recalculates values. For example if you are looking for the

F5 = F4 + F3

Thread 1: F4 = F3 + F2

Thread 2: F3 = F2 + F1

Notice that you calculate F3 twice. In fact you are calculating just about each number twice.

Upvotes: 1

NPE
NPE

Reputation: 500853

You say you're doing this to improve performance. There are several issues:

  • You'll never decrease the computation time by using threads in this manner.
  • If you care about performance, recursion is a bad idea for this problem.

Just have one thread, a simple loop and two variables, and you'll have something that'll be hard to beat performance-wise (without using a closed-form solution, that is).

Upvotes: 4

helpermethod
helpermethod

Reputation: 62224

See Fibonacci numbers (Java), memoized recursion. This should give you an idea on how to implement a fast solution.

Upvotes: 2

Related Questions