私は CUDA を学び始めており、円周率の長い数字を計算することは、素晴らしい入門プロジェクトになると思います。
簡単に並列化できる単純なモンテカルロ法を既に実装しています。各スレッドに単位正方形上でランダムに点を生成させ、単位円内にいくつあるかを計算し、リダクション操作を使用して結果を集計するだけです。
しかし、それは確かに定数を計算するための最速のアルゴリズムではありません。以前、シングル スレッドの CPU でこの演習を行ったとき、Machin のような数式を使用して計算を行い、収束を大幅に高速化しました。興味のある人のために、これには逆正接の和として pi を表現し、式を評価するためにテイラー級数を使用することが含まれます。
そのような式の例:
残念ながら、この手法を何千もの GPU スレッドに並列化するのは簡単ではないことがわかりました。問題は、データの長いベクトルに対して浮動小数点演算を行うのではなく、大部分の演算が単純に高精度の計算を行うことです。
GPUで任意の長い円周率を計算する最も効率的な方法は何ですか?
Bailey–Borwein–Plouffe の式を使用する必要があります。
なんで？まず、分解できるアルゴリズムが必要です。それで、最初に頭に浮かんだのは、円周率を無限の和として表現することでした。次に、各プロセッサは 1 つの項を計算するだけで、最終的にそれらすべてを合計します。
次に、各プロセッサは、非常に高精度の値ではなく、低精度の値を操作することが望ましいです。たとえば、10 億の 10進数が必要で、ここで使用されている表現のいくつかを使用する場合、チュドノフスキー アルゴリズムのように、各プロセッサは 10 億の長さの数値を操作する必要があります。これは、GPU に適した方法ではありません。
つまり、全体として、BBP 式を使用すると、pi の桁を個別に計算することができ (アルゴリズムは非常に優れています)、「低精度」プロセッサを使用できます! 「π の BBP 数字抽出アルゴリズム」を読む
π を計算するための BBP アルゴリズムの利点 このアルゴリズムは、数千桁または数百万桁のカスタム データ型を必要とせずにπ を計算します。このメソッドは、最初の n − 1 桁を計算せずに n 桁目を計算し、小さくて効率的なデータ型を使用できます。このアルゴリズムは、n 桁目 (または n 桁目付近の数桁) を計算する最速の方法ですが、1 から n までのすべての桁を計算することが目標である場合、大きなデータ型を使用する π 計算アルゴリズムは依然として高速です。