Parallelize Fibonacci sequence generator

Question

I'm learning about parallelization and in one exercise I'm given a couple of algorithms that I should improve in performance. One of them is a Fibonacci sequence generator:

array[0] = 0;
array[1] = 1;
for (q = 2; q < MAX; q++) {
    array[q] = array[q−1] + array[q−2];
}

My suspicion is, that this cannot be optimized (by parallelization), since every number depends on the two preceding numbers (and therefore indirectly on all preceding numbers). How could this be parallelized?

Answer 1

The Fibonacci sequence is determined just by its first two elements; in fact, you could somehow parallelize it, although ugly:

F(n + 2) = F(n + 1) + F(n)
F(n + 3) = F(n + 1) + F(n + 2) = F(n + 1) * 2 + F(n)
F(n + 4) = F(n + 2) + F(n + 3) = F(n + 1) * 3 + F(n) * 2
F(n + 5) = F(n + 3) + F(n + 4) = F(n + 1) * 5 + F(n) * 3
F(n + 6) = F(n + 4) + F(n + 5) = F(n + 1) * 8 + F(n) * 5

Hopefully by now, you can see that:

F(n + k) = F(n + 1) * F(K) + F(n) * F(k - 1)

So after computing the first k numbers, you could use this relation to compute the next k items in the sequence, at the same time, parallelized.

You could also use the direct formula for Fibonacci numbers to compute them in parallel, but that is kind of too uncool (also might be too simple for learning purposes that it might serve).