博士

やあ、ロボ子。今日はGPUプログラミングでフィボナッチ数列を高速に計算する方法について話すのじゃ。

ロボ子

博士、こんにちは。GPUでフィボナッチ数列ですか、面白そうですね！

博士

そうじゃろ！NVIDIAのThrustライブラリを使うと、モダンC++の概念でGPUプログラミングが簡単にできるのじゃ。

ロボ子

Thrustライブラリですね。scan演算というものを使うと並列化できるそうですが、scan演算とは何ですか？

博士

scan演算は、配列`x=[x1,...,xN]`を`y=[y1,...,yN]`に変換するのじゃ。inclusive scanだと`yi = x0 ⊕ ... ⊕ xi`、exclusive scanだと`yi = x0 ⊕ ... ⊕ xi-1`となるぞ。⊕は結合的な二項演算子じゃ。

ロボ子

なるほど、累積和のようなものですね。Thrustを使うと、exclusive scanが簡単にできるんですね。

博士

その通り！デフォルトではプラス演算子が適用されるのじゃ。行列のscan演算も可能で、行列の乗算は結合的なので、行列を使ったscanもできるぞ。

ロボ子

行列でscan演算ですか。それがフィボナッチ数列とどう関係するんですか？

博士

フィボナッチ数列には、こんな恒等式があるのじゃ。  この式を使うと、行列`Q`とのscanを実行して、結果の行列からフィボナッチ数が得られるのじゃ。

ロボ子

へー、面白い！行列のscanでフィボナッチ数列を計算できるんですね。

博士

そうじゃ。しかも、GPUの能力を使うと、F99999999をわずか17ミリ秒で計算できるのじゃ！

ロボ子

それはすごい！でも、整数のオーバーフローはどうするんですか？

博士

良い質問じゃな、ロボ子。整数のオーバーフローを避けるために、行列の乗算において特定の数で剰余を取るのじゃ。例えば、F(99999999) mod 9837 = 7558となるぞ（NVIDIA GeForce RTX 3060 Mobileを使用）。

ロボ子

なるほど、剰余を取ることでオーバーフローを防ぐんですね。scan演算とThrustを使うことで、こんなに大きなフィボナッチ数も高速に計算できるなんて驚きです。

博士

そうじゃろ！Scan演算は本当に強力で、Thrustを使うと複雑な演算も簡単に実装できるのじゃ。ちなみに、このフィボナッチ数をScanで計算するアイデアは、Guy Blellochという人の演習から得られたものなのじゃ。

ロボ子

すごいですね。私もThrustを使って色々試してみたくなりました。

博士

よし、ロボ子。今度、二人でGPUを使って、もっと面白い計算をしてみようかの。例えば、素数をscan演算で見つけるとか…って、それは無理か！