ベイリー＝ボールウェイン＝プラウフの公式

ベイリー＝ボールウェイン＝プラウフの公式（ベイリー＝ボールウェイン＝プラウフのこうしき、テンプレート:Lang-en-short）あるいはBBP公式は、1995年にサイモン・プラウフによって発見された円周率 テンプレート:Π に関する以下の公式である。

$$\pi =\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{16^k}(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6})\right]$$（テンプレート:EquationRef）テンプレート:Sfn

名称はBBP公式に関する論文 テンプレート:Harv の著者らテンプレート:Ill2、テンプレート:Ill2、プラウフに因む。BBP公式は論文公開以前にもプラウフが自身のサイトで紹介していた。

BBP公式は、先行する桁を計算せずに テンプレート:Pi の十六進法で テンプレート:Mvar 桁目（二進法で テンプレート:Math 桁目）の数を直接求めるテンプレート:Ill2を与える。これは テンプレート:Pi の十進法で テンプレート:Mvar 桁目を計算するものではないテンプレート:Sfn。そのような公式はプラウフによって2022年に発見されている。BBPとBBPに触発されたアルゴリズムは、分散コンピューティングを使って テンプレート:Pi の多くの桁を計算するPiHexなどのプロジェクトで使用されている。BBPアルゴリズムの発見は驚くべきものであった。BBPアルゴリズムの発見以前、テンプレート:Pi のような超越数の テンプレート:Mvar 桁目を直接計算するのは、最初の テンプレート:Mvar 桁を計算するのと同程度に難しいと広く信じられていたテンプレート:Sfn。

テンプレート:Pi 以外の無理数についてもBBP公式と類似の式が得られている。それらの類似の式はBBP型公式（テンプレート:En）またはBBP系公式と呼ばれる。BBP型公式の一般形は以下のように表される：

$$\alpha =\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{b^k}\frac{p(k)}{q(k)}\right]$$（テンプレート:EquationRef）テンプレート:Sfnテンプレート:Efn2

ここで テンプレート:Mvar は無理数、テンプレート:Math は テンプレート:Mvar の整数係数多項式、テンプレート:Mvar は通常、位取り記数法の底であり テンプレート:Math 以上の整数を表すが、より一般には実数でもよい。また テンプレート:Mvar は テンプレート:Mvar の範囲でゼロにならず、テンプレート:Mvar の次数は テンプレート:Mvar より小さい。

ある数 テンプレート:Mvar に対しBBP型公式を（すなわち テンプレート:Math, テンプレート:Math, テンプレート:Mvar を）与える系統だったアルゴリズムは知られておらず、ある数に対するBBP型公式は今のところ実験的な方法によってのみ得られている。

特殊化

一般のテンプレート:EqNoteNの特殊な例として、多くの結果を与えたものに以下がある： $$P(s,b,m,A)=\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{b^k}\sum _{j=1}^m\frac{a_j}{(mk+j{)}^s}\right]$$（テンプレート:EquationRef）

ここで テンプレート:Math2 は整数、テンプレート:Math は整数の数列である。 関数 テンプレート:Mvar はいくつかの解に対して簡潔な表記を与える。例えば、元のテンプレート:EqNoteNは、テンプレート:Math, テンプレート:Math, テンプレート:Math, テンプレート:Math2 として以下のように書くことができる。 $$\pi =P(1,16,8,[4,0,0,-2,-1,-1,0,0])$$

既知のBBP型公式

BBP型公式のうちBBP公式より以前から知られているもので、テンプレート:EqNoteN テンプレート:Mvar が簡潔な形になるものに、次のものがある。

$$\begin{array}{cc}\ln \frac{10}{9}& =\frac{1}{10}+\frac{1}{200}+\frac{1}{3000}+\cdots \\ & =\frac{1}{10}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{10^k}\left(\frac{1}{k+1}\right)\right]\\ & =\frac{1}{10}P(1,10,1,[1])\end{array}$$

$$\begin{array}{cc}\ln 2& =\frac{1}{2}+\frac{1}{2\cdot 2^2}+\frac{1}{3\cdot 2^3}+\cdots \\ & =\frac{1}{2}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{2^k}\left(\frac{1}{k+1}\right)\right]\\ & =\frac{1}{2}P(1,2,1,[1]).\end{array}$$

（実際、恒等式

$\ln \frac{a}{a-1}=\sum _{k=1}^{\mathrm{\infty }}\frac{1}{a^k\cdot k}$

は テンプレート:Math に対して成り立つ）

プラウフは、逆三角関数の冪級数にも触発された（テンプレート:Mvar 表記は テンプレート:Mvar が整数でない場合にも一般化できる）。

$$\begin{array}{cc}\arctan \frac{1}{b}& =\frac{1}{b}-\frac{1}{b^{3}3}+\frac{1}{b^{5}5}-\cdots \\ & =\frac{1}{b}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{b^{4k}}(\frac{1}{4k+1}+\frac{-b^{-2}}{4k+3})\right]\\ & =\frac{1}{b}P(1,b^4,4,[1,0,-b^{-2},0])\end{array}$$

新しい等式の探索

テンプレート:EqNoteN テンプレート:Mvar を用いた方法で、テンプレート:Pi について既知の最も簡潔なものは、テンプレート:Math かつ テンプレート:Math のものである。テンプレート:Mvar が指数 テンプレート:Math または テンプレート:Math、テンプレート:Mvar が指数 テンプレート:Math または他の因数に富む値で、かつ数列 テンプレート:Mvar の項のいくつかが テンプレート:Math である場合、現在多くの公式が知られている。これらの公式の発見には、個々の和を計算した後、コンピュータでこのような線形結合を探索することが必要である。探索の手順は、s、b、mのパラメータ値の範囲を選び、その和を何桁にもわたって評価し、それらの中間和をよく知られた定数に、あるいはおそらくゼロに足し合わせる数列Aを、整数関係探索アルゴリズム（典型的にはHelaman FergusonのPSLQアルゴリズム）を用いて求めるというものである。

発見と導出

円周率のBBP公式の原型は、1995年にプラウフがPSLQアルゴリズムを用いて見つけたものである。また、テンプレート:EqNoteN テンプレート:Mvar を用いて表現可能である。

$$\begin{array}{cc}\pi & =\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{16^k}(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6})\right]\\ & =P(1,16,8,(4,0,0,-2,-1,-1,0,0)).\end{array}$$

上式は、以下の等価な2多項式の比に還元される。

$$\pi =\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{16^k}\left(\frac{120k^2+151k+47}{512k^4+1024k^3+712k^2+194k+15}\right)\right]$$

この式は、かなり単純な証明によって、テンプレート:Pi に等しいことが示されているテンプレート:Sfn。

BBPアルゴリズム

以下ではテンプレート:EqNoteNから円周率 テンプレート:Pi の十六進法で テンプレート:Mvar 桁目の数を与えるアルゴリズム（BBPアルゴリズム）について説明する。

一般に数 テンプレート:Mvar の テンプレート:Mvar 進法で小数点以下 テンプレート:Mvar 桁目の値を求めるには、テンプレート:Mvar に テンプレート:Math を掛けて（テンプレート:Math 桁左にシフトして）その小数部分の最上位の桁を計算すればよい。BBPアルゴリズムでは テンプレート:Mvar 桁目だけを必要とするため、小数部の計算は通常の浮動小数点数の演算で済む。テンプレート:Math の整数部分の計算を省略できるなら、テンプレート:Mvar の小数点以下 テンプレート:Math 桁までの値を求めずに テンプレート:Mvar 桁目を計算できる。

テンプレート:Math の整数部の計算の省略は剰余算することでできる。 テンプレート:Mvar がテンプレート:EqNoteNの一般形で書ける場合、分母 テンプレート:Math で分子 テンプレート:Math を割った余りだけを計算するよう変形し、最後に和の小数部を取り出す：

$$\left\{b^{n-1}\alpha \right\}mod1=\left\{\sum _{k=0}^{\mathrm{\infty }}\frac{b^{(n-1)-k}p(k)modq(k)}{q(k)}\right\}mod1$$

特にテンプレート:EqNoteNの テンプレート:Math の場合では、以下のように書ける：

$$\{b^{n-1}P(1,m,b,A)\}mod1=\left\{\sum _{j=1}^m{a}_j\left[\sum _{k=0}^{\mathrm{\infty }}\frac{b^{(n-1)-k}mod(mk+j)}{mk+j}\right]\right\}mod1$$

ここで テンプレート:Math は テンプレート:Mvar を テンプレート:Mvar で割った余りを表すテンプレート:Efn2。和の中の剰余算が必要となるのは分子が分母より大きくなる場合のみであり、分子が小さい場合には必要ない。そのため、上述の テンプレート:Math の例では、テンプレート:Math となる最初の項だけ剰余算を行う。

上述の手順に従い テンプレート:Pi の16進法での小数点以下 テンプレート:Mvar 桁目の計算を以下に示す。まずテンプレート:EqNoteNを以下のように変形する：

$$16^{n-1}\pi =4\sum _{k=0}^{\mathrm{\infty }}\frac{16^{(n-1)-k}}{8k+1}-2\sum _{k=0}^{\mathrm{\infty }}\frac{16^{(n-1)-k}}{8k+4}-\sum _{k=0}^{\mathrm{\infty }}\frac{16^{(n-1)-k}}{8k+5}-\sum _{k=0}^{\mathrm{\infty }}\frac{16^{(n-1)-k}}{8k+6}$$

それぞれの和の小数部の最初の数桁を計算し、次に右辺全体の小数部を計算する。最終的な結果から小数第一位を取り出せば テンプレート:Pi の小数第 テンプレート:Mvar 位が求まる。

例えば最初の和の小数部は以下のようになる：

$$\left\{\sum _{k=0}^{\mathrm{\infty }}\frac{16^{(n-1)-k}}{8k+1}\right\}mod1=\{\sum _{k=0}^{n-1}\frac{16^{(n-1)-k}mod(8k+1)}{8k+1}+\sum _{k=n}^{\mathrm{\infty }}\frac{16^{(n-1)-k}}{8k+1}\}mod1$$

前述の通り、右辺の2つ目の和に関しては適当な精度で値が収束したと見なされるまで計算すればよいが、1つ目の和は テンプレート:Mvar 回の冪剰余テンプレート:Efn2が必要となる。 一方で1回の冪剰余の計算は、テンプレート:Math を テンプレート:Mvar ビット整数の乗算に必要な計算量として、テンプレート:Math のビット計算量で行えるテンプレート:Efn2テンプレート:Efn2。 従って全体の計算量は テンプレート:Math となる。

乗算の計算量は乗算アルゴリズムに依存する。例えば、乗算を筆算と同様に行えば乗算の計算量は テンプレート:Math となり、この場合のBBPアルゴリズムの計算量は テンプレート:Math となる。乗算をショーンハーゲ・ストラッセン法で行えば乗算の計算量は テンプレート:Math となり、この場合のBBPアルゴリズムの計算量は

$$O(n\cdot (\log n{)}^2\cdot \log (\log n)\cdot \log (\log (\log n)))$$

となる。 これは（ショーンハーゲ・ストラッセン法で乗算を実装した場合の）テンプレート:Pi を テンプレート:Mvar 桁計算するアルゴリズムよりはわずかに遅く、BBPアルゴリズムのビット計算量は テンプレート:Math 倍だけ大きい。

BBPアルゴリズムの結果は テンプレート:Mvar 桁目以降の値も含んでおり、テンプレート:Math 桁目ないし テンプレート:Math 桁目の計算結果と比較することで計算結果が正しいことを検証できる。

BBPと他の円周率計算方法との比較

このアルゴリズムは、数千、数百万の桁を持つカスタムデータ型を必要とせずに テンプレート:Pi を計算する。この方法は、最初の n − 1 桁を計算せずにn桁目を計算し、小さくて効率的なデータ型を使用することができる。

BBPは テンプレート:Pi の任意の桁の値を直接計算することができ、その間のすべての桁を計算しなければならない数式よりも少ない計算量で計算できるが、BBPは線形的（$O(n(\log n{)}^{O(1)})$テンプレート:Sfn）であり、テンプレート:Mvar の値が大きくなるほど計算に要する時間が長くなる。つまり、ある桁が「先に」あるほどBBPの計算に要する時間は長くなり、標準の テンプレート:Pi 計算アルゴリズムと同じようになっていく。

一般化

D. J. Broadhurst はBBPアルゴリズムを一般化し、他の多くの定数をほぼ線形時間および対数空間で計算するために使用できるようにしたテンプレート:Sfn。カタランの定数、テンプレート:Math、テンプレート:Math、アペリーの定数 テンプレート:Math、テンプレート:Math（テンプレート:Math はリーマンゼータ函数）、テンプレート:Math、テンプレート:Math、テンプレート:Math および テンプレート:Pi と テンプレート:Math の冪乗による様々な積について明示的に結果を与えている。これらの結果は、主に多重対数梯子を用いて得られるものである。

関連項目

• 円周率の近似
• 実験数学
• テンプレート:Ill2

参考文献

• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite web2
• テンプレート:Cite journal

外部リンク

• テンプレート:Ill2, "Making An Algorithm An Algorithm — BBP", weblog post, July 14, 2010.
• リチャード・リプトン, "Cook’s Class Contains Pi", weblog post, March 15, 2009.
• テンプレート:Cite web
• テンプレート:Ill2, "BBP Code Directory", web page with links to Bailey's code implementing the BBP algorithm, September 8, 2006.