并行斐波那契序列发生器(Parallelize Fibonacci sequence generat

我正在学习关于并行化和在一个锻炼，我给出了几个，我应该在性能提升的算法。 其中之一是斐波那契序列发生器：

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

我的怀疑是，这不能被优化（由并行化），因为每一个数量取决于前两个数字对（并因此间接地对所有的先行数字）。 这怎么可能被并行化？

Answer 1:

斐波那契数序列仅通过它的前两个元素来确定; 其实，你可以以某种方式并行化，虽然难看：

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

希望现在，你可以看到：

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

因此，在计算前k号码后，您可以使用这种关系来计算下一k个项目的顺序，同时，并行化。

你也可以使用斐波那契数计算它们并行的直接公式，但毕竟是一种太酷了（也可能是过于简单了学习的目的，它可能成为）。

Answer 2:

最好的方式来处理它使用斐波那契数的2维矩阵形式

现在，您可以轻松地扩展它。 简单的矩阵乘法的概念将做到这一点。

或者您也可以与其他数学方法去，如

Answer 3:

若干 'n' 是一个Fibanocci数如果（5N ^ 2 - 4）或第（5n ^ 2 + 4）是一个完美的正方形。

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

因此，考虑大一些，你可以找到使用这种算法，接下来的两个蛋白原NUMS和你除了继续从那时起。

以这种方式，可以划分的问题，因为（0到N / 2），然后（N / 2 + 1到N）之间，并且在并行线程中运行它。

文章来源: Parallelize Fibonacci sequence generator