并行化Fibonacci序列生成器

我正在学习并行化，在一个练习中，我给出了一些我应该提高性能的算法。 其中一个是Fibonacci序列生成器：

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

我怀疑这是不能优化的（通过并行化），因为每个数字都取决于前两个数字（因此间接地依赖于所有前面的数字）。 怎么可以并行化呢？

Answer 1

Fibonacci序列仅由前两个元素决定; 事实上，你可以以某种方式并行化它，虽然丑陋：

 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项，同时并行化。

你也可以使用Fibonacci数的直接公式来并行计算它们，但这有点过于冷却（对于它可能服务的学习目的来说也可能太简单了）。

Answer 2

接近它使用Fibonacci的二维矩阵forms的最佳方法

现在您可以轻松扩展它。 简单的矩阵乘法概念就可以实现。

或者你可以采用其他数学方式，例如

Answer 3

如果（5n ^ 2 – 4）或（5n ^ 2 + 4）是完美的正方形，则数字’n’是Fibanocci数。

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

因此，如果给出大量数据，您可以使用此算法找到接下来的两个Fib nums，然后继续添加。

这样，您可以将问题分区为（0到N / 2）然后（N / 2 + 1到N）并在并行线程中运行它。