Fibonacci using Threads

Question

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

I'm not sure you can write a multithreaded Fibonacci generator, since each element in the sequence is a function of the last. — cdhowie, Dec 05 '10 at 09:37
@Mariah, no, e.g. you could implement a recursive flood fill with threads, as the algorithm does not directly depends on the result of a previous computation. — Ivo Wetzel, Dec 05 '10 at 09:41
Oh, ok. Can you please suggest some other recursive algorithms that can be made more efficient with threading? — Mariah, Dec 05 '10 at 09:44
Mariah: See the closed-form formula given here: http://en.wikipedia.org/wiki/Fibonacci_number ; there is indeed an expression for an arbritary element of the sequence (the closed form formula being that). — Noon Silk, Dec 05 '10 at 10:13
(Of course, knowing that kind of shifts your problem from finding Fibonacci's sequence to one of dealing with higher powers and finding the golden ratio to some arbitrary precision; but I guess I leave that research to you :) — Noon Silk, Dec 05 '10 at 10:27

score 2 · Answer 1 · edited May 23 '17 at 12:18

2

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.

edited May 23 '17 at 12:18

Community

1
1

answered Dec 05 '10 at 10:05

Little Bobby Tables

5,261
2
39
49

Since each results depends on the previous one, there isn't independent operations you can perform in parallel. – Peter Lawrey Dec 05 '10 at 10:55

score 0 · Answer 2 · answered Dec 05 '10 at 09:40

0

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.

answered Dec 05 '10 at 09:40

Stan Kurilin

15,614
21
81
132

Peter Lawrey · Answer 3 · 2010-12-05T10:54:22.300

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.

Fibonacci using Threads

3 Answers3