c - 并行化斐波那契数列生成器

Question

我正在学习并行化，在一次练习中，我得到了一些我应该提高性能的算法。其中之一是斐波那契数列生成器：

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

接近它的最佳方法是使用斐波那契的二维矩阵形式

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

或者您可以使用其他数学方式，例如

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) 之间，并在并行线程中运行它。