并行斐波那契序列生成器 [英] Parallelize Fibonacci sequence generator

问题描述

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

I'm learning about parallelization and in one exercise I'm given a couple of algorithms that I should improve in performance. One of them is a 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 every number depends on the two preceding numbers (and therefore indirectly on all preceding numbers). How could this be parallelized?

推荐答案

斐波那契数列仅由其前两个元素确定；实际上，尽管很难看，但您可以通过某种方式并行化它:

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

希望现在您可以看到:

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

因此，在计算出前k个数字之后，您可以使用此关系来计算序列中的后k个对象，同时对其进行并行化.

So after computing the first k numbers, you could use this relation to compute the next k items in the sequence, at the same time, parallelized.

您还可以使用斐波那契数的直接公式来并行计算它们，但这太不酷了(出于学习目的，它可能太简单了，可能会起作用).

You could also use the direct formula for Fibonacci numbers to compute them in parallel, but that is kind of too uncool (also might be too simple for learning purposes that it might serve).

这篇关于并行斐波那契序列生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！