Fibonacci parallel sequence generator

Question

I learn about parallelization, and in one exercise I am given several algorithms that I need to improve in performance. One of them is the 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 each number depends on the two previous numbers (and therefore indirectly on all previous numbers). How can this be parallelized?

Answer 1

The Fibonacci sequence is determined only by its first two elements; in fact, you could somehow parallelize it, albeit 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 

Hope you can now see that:

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

So, after calculating the first k numbers, you can use this ratio to calculate the next k elements in the sequence, at the same time, with parallelization.

You can also use the direct formula for Fibonacci numbers to calculate them in parallel, but this is too crude (it may also be too simple for training purposes that it can serve).

Answer 2

The best way to get close to it is to use the two-dimensional Fibonacci matrix form

Now you can easily expand it. Simple matrix multiplication concepts will do this.

or you can go in another mathematical way, for example

Answer 3

The number "n" is the Fibanoxy number if either (5n ^ 2 - 4) or (5n ^ 2 + 4) is an ideal square.

http://en.wikipedia.org/wiki/Fibonacci_number

Therefore, given the large number, you can find the following two Fib numbers using this algorithm, and continue with the addition and further.

Thus, you can split the problem both between (from 0 to N / 2) and (N / 2 + 1 to N) and run it in parallel threads.