c - Parallelize Fibonacci sequence generator -

i'm learning parallelization , in 1 exercise i'm given couple of algorithms should improve in performance. 1 of them fibonacci sequence generator:

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

my suspicion is, cannot optimized (by parallelization), since every number depends on 2 preceding numbers (and therefore indirectly on preceding numbers). how parallelized?

the fibonacci sequence determined first 2 elements; in fact, 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 now, can see that:

f(n + k) = f(n + 1) * f(k) + f(n) * f(k - 1) 

so after computing first k numbers, use relation compute next k items in sequence, @ same time, parallelized.

you use direct formula fibonacci numbers compute them in parallel, kind of uncool (also might simple learning purposes might serve).