我正在学习并行化,在一项练习中,我得到了一些我应该提高性能的算法。其中之一是斐波那契数列生成器:
array[0] = 0;
array[1] = 1;
for (q = 2; q < MAX; q++) {
array[q] = array[q−1] + array[q−2];
}
我怀疑,这无法优化(通过并行化),因为每个数字都取决于前面的两个数字(因此间接取决于所有前面的数字)。这如何并行化?
斐波那契数列仅由其前两个元素决定;事实上,你可以以某种方式并行化它,尽管很难看:
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 个项目,同时并行计算。
您还可以使用斐波那契数的直接公式来并行计算它们,但这有点太不酷了(对于它可能达到的学习目的来说也可能太简单了)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)