パラレル化フィボナッチシーケンスジェネレータ

Question

私は並列化について学んでいます.1つのエクササイズでは、性能を向上させるためのアルゴリズムがいくつか用意されています。そのうちの一つは、フィボナッチ数列ジェネレータです：

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

私の疑惑は、すべての数が2つの前の番号に依存（したがって、間接的に先行するすべての番号に）ので、これは、（並列化によって）最適化することができないこと、です。どのようにこれを並列化できますか？

Answer 1

フィボナッチ配列は、その最初の2つの要素によって決まります。だから、最初のk個の数字を計算した後、あなたが計算するために、この関係を使用することができ

F(n + k) = F(n + 1) * F(K) + F(n) * F(k - 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 

、あなたがいることを見ることができます：醜いものの実際には、あなたが何らかの形で、それを並列化することができシーケンス内の次のk個のアイテムを同時に並列化します。

また、フィボナッチ数の直接計算式を使用して並列に計算することもできますが、あまりにもクールではありません（学習目的には単純すぎるかもしれません）。

Answer 2

（5n^2 - 4）または（5n^2 + 4）のいずれかが完全な正方形である場合、数字 'n'はFibanocci数です。

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

ので、多数与え、あなたは、このアルゴリズムを使用して次の二つのFIB NUMSを見つけることができ、その後、以降、あなたのほかに進みます。

このように、問題を（0〜N/2）と（N/2 + 1〜N）の間で分割し、並列スレッドで実行することができます。

Answer 3

今、あなたは簡単にそれを拡張することができフィボナッチ

の2次元マトリクス状を使用するようにアプローチするための最良の方法。単純な行列の乗算の概念はそれを行います。

かは、そのような