円周率に対するBBP桁抽出アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 06:54 UTC 版)
「ベイリー＝ボールウェイン＝プラウフの公式」の記事における「円周率に対するBBP桁抽出アルゴリズム」の解説
円周率 π の十六進数でのn桁目を返す数式を定義したい。この式を使ってスピゴット・アルゴリズムを実装するためには、いくつかの操作が必要である。 はじめに、公式を次のように変形する必要がある。 π = 4 ∑ k = 0 ∞ 1 ( 16 k ) ( 8 k + 1 ) − 2 ∑ k = 0 ∞ 1 ( 16 k ) ( 8 k + 4 ) − ∑ k = 0 ∞ 1 ( 16 k ) ( 8 k + 5 ) − ∑ k = 0 ∞ 1 ( 16 k ) ( 8 k + 6 ) {\displaystyle \pi =4\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+1)}}-2\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+4)}}-\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+5)}}-\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+6)}}} さて、ある特定の値nについて、最初の和をとると、n番目の項をはさんで和が無限大に分かれる。 ∑ k = 0 ∞ 1 ( 16 k ) ( 8 k + 1 ) = ∑ k = 0 n 1 ( 16 k ) ( 8 k + 1 ) + ∑ k = n + 1 ∞ 1 ( 16 k ) ( 8 k + 1 ) {\displaystyle \sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+1)}}=\sum _{k=0}^{n}{\frac {1}{\left(16^{k}\right)(8k+1)}}+\sum _{k=n+1}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+1)}}} ここで 16 n {\displaystyle 16^{n}} を掛けると、十六進数の小数点（小数部と整数部の分かれ目）はn位になる。 ∑ k = 0 ∞ 16 n − k 8 k + 1 = ∑ k = 0 n 16 n − k 8 k + 1 + ∑ k = n + 1 ∞ 16 n − k 8 k + 1 {\displaystyle \sum _{k=0}^{\infty }{\frac {16^{n-k}}{8k+1}}=\sum _{k=0}^{n}{\frac {16^{n-k}}{8k+1}}+\sum _{k=n+1}^{\infty }{\frac {16^{n-k}}{8k+1}}} 逆に、2番目の和は、k > n のとき、分子が分母より大きくなることはないので、整数を生成することはできない。したがって、最初の和の整数を除去するトリックが必要である。そのトリックとは mod 8k + 1 である。そうすると、最初の分数部分の和は ∑ k = 0 n 16 n − k mod ( 8 k + 1 ) 8 k + 1 + ∑ k = n + 1 ∞ 16 n − k 8 k + 1 {\displaystyle \sum _{k=0}^{n}{\frac {16^{n-k}{\bmod {(}}8k+1)}{8k+1}}+\sum _{k=n+1}^{\infty }{\frac {16^{n-k}}{8k+1}}} となる。 合同演算子が常に分数の和だけを残すことを保証していることに注目。16n−k mod (8k + 1) を高速かつ効率的に計算するために、冪剰余アルゴリズムが使用される。実行積が1より大きくなると、各和の実行積と同じように合同演算がとられる。 さて、計算を完了するには、これを4つの和に順番に適用する必要がある。これが終わると、4つの和は π に戻される。 4 Σ 1 − 2 Σ 2 − Σ 3 − Σ 4 {\displaystyle 4\Sigma _{1}-2\Sigma _{2}-\Sigma _{3}-\Sigma _{4}} 正確なのは分数部だけなので、目的の桁を取り出すには、最終和の整数部を取り除き、16倍してこの位置の十六進数桁を「かすめ取る」必要がある（理論上は、使用した計算の精度までの次の数桁も正確である）。 この処理は、長い乗算を行うのと似ているが、いくつかの中間列の和を実行するだけでよい。カウントされないキャリーも存在するが、コンピュータは通常、多くのビット（32または64）に対して演算を行い、丸めるため、我々は最上位の桁にしか興味がない。ある計算が、99999999999という数字に小さな数字（例えば1）を足すのに失敗するようなもので、その誤差が最上位桁に伝播していく可能性がある。
※この「円周率に対するBBP桁抽出アルゴリズム」の解説は、「ベイリー＝ボールウェイン＝プラウフの公式」の解説の一部です。
「円周率に対するBBP桁抽出アルゴリズム」を含む「ベイリー＝ボールウェイン＝プラウフの公式」の記事については、「ベイリー＝ボールウェイン＝プラウフの公式」の概要を参照ください。
- 円周率に対するBBP桁抽出アルゴリズムのページへのリンク
