Fibonacci using Threads

The following code attempts开发者_如何学运维 to parallelize the Fibonacci number problem. How can this be modified so that the number of threads are limited.

I understand that Fibonacci is not a natural candidate for threading. But would like to know how it can be optimized with threading.

public class Fib extends Thread
{
    private int x;
    public int answer;

    public Fib(int x) {
        this.x = x;
    }

    public void run() {
        if( x <= 2 )
            answer = 1;
        else {
            try {
                Fib f1 = new Fib(x-1);
                Fib f2 = new Fib(x-2);
                f1.start();
                f2.start();
                f1.join();
                f2.join();
                answer = f1.answer + f2.answer;
            }
            catch(InterruptedException ex) { }
        }
    }

    public static void main(String[] args)
        throws Exception
    {
        try {
            Fib f = new Fib( Integer.parseInt(args[0]) );
            f.start();
            f.join();
            System.out.println(f.answer);
        }
        catch(Exception e) {
            System.out.println("usage: java Fib NUMBER");
        }
    }
}

Branching each call to fib() into two calls is inefficient - The calculation of the Fibonacci series should be done in linear time. See answer to this question.

That said, if you still want to use threads, memoization and/or using future results is essential.

You can create some factory for Threads that will contain current number of Threads/thread's poll or smt else. The main issue of this factory will be - threads creation.

Fibonacci is a common example for creating lots of threads because its easy to understand and implement which makes it good for homework, however it should be noted that is also perhaps the best example of when using one thread is faster than trying to use multiple threads. The reason its a bad idea is that the overhead from having many threads is proportional the result which grows exponential.

In short, the optimal number of threads is one. Once you know that, your code will become much simpler.

If you want optimise your code, you should start building your values from the first value up in a loop. i.e. start with 1, 1, 2, 3, 5, 8 ... This will also reduce the number of calls you make exponentially.