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

ベイリー＝ボールウェイン＝プラウフの公式あるいはBBP公式は、1995年にサイモン・プラウフによって発見された円周率 に関する以下の公式である。

名称はBBP公式に関する論文 Bailey の著者らデイヴィッド・H・ベイリー、ピーター・ボールウェイン、プラウフに因む。BBP公式は論文公開以前にもプラウフが自身のサイトで紹介していた。

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

以外の無理数についてもBBP公式と類似の式が得られている。それらの類似の式はBBP型公式またはBBP系公式と呼ばれる。BBP型公式の一般形は以下のように表される：

Baileyここで α}} は無理数、1=//p//, //q//}} は k}} の整数係数多項式、b}} は通常、位取り記数法の底であり 2}} 以上の整数を表すが、より一般には実数でもよい。また q}} は k}} の範囲でゼロにならず、p}} の次数は q}} より小さい。

ある数 α}} に対しBBP型公式を与える系統だったアルゴリズムは知られておらず、ある数に対するBBP型公式は今のところ実験的な方法によってのみ得られている。

1. 特殊化
------

一般のBBP型公式}}の特殊な例として、多くの結果を与えたものに以下がある：

ここで 1=//s//, //b//, //m//}} は整数、//A// =}} }} は整数の数列である。関数 P}} はいくつかの解に対して簡潔な表記を与える。例えば、元のBBP公式}}は、1=//s// = 1}}, 1=//b// = 16}}, 1=//m// = 8}}, 1=//A// = [4, 0, 0, −2, −1, −1, 0, 0]}} として以下のように書くことができる。

1.1. 既知のBBP型公式
--------------

BBP型公式のうちBBP公式より以前から知られているもので、BBP型公式の特殊化}} P}} が簡潔な形になるものに、次のものがある。

プラウフは、逆三角関数の冪級数にも触発された。

1.2. 新しい等式の探索
-------------

BBP型公式の特殊化}} P}} を用いた方法で、 について既知の最も簡潔なものは、1=//s// = 1}} かつ 1=//m// > 1}} のものである。b}} が指数 2}} または 3}}、m}} が指数 2}} または他の因数に富む値で、かつ数列 A}} の項のいくつかが 0}} である場合、現在多くの公式が知られている。これらの公式の発見には、個々の和を計算した後、コンピュータでこのような線形結合を探索することが必要である。探索の手順は、s、b、mのパラメータ値の範囲を選び、その和を何桁にもわたって評価し、それらの中間和をよく知られた定数に、あるいはおそらくゼロに足し合わせる数列Aを、整数関係探索アルゴリズムを用いて求めるというものである。

2. 発見と導出
--------

円周率のBBP公式の原型は、1995年にプラウフがPSLQアルゴリズムを用いて見つけたものである。また、BBP型公式の特殊化}} P}} を用いて表現可能である。

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

この式は、かなり単純な証明によって、 に等しいことが示されているBailey。

3. BBPアルゴリズム
------------

以下ではBBP公式}}から円周率 の十六進法で n}} 桁目の数を与えるアルゴリズムについて説明する。

一般に数 α}} の b}} 進法で小数点以下 n}} 桁目の値を求めるには、α}} に 1=//b////n//−1}} を掛けてその小数部分の最上位の桁を計算すればよい。BBPアルゴリズムでは n}} 桁目だけを必要とするため、小数部の計算は通常の浮動小数点数の演算で済む。1=//b////n//−1//α//}} の整数部分の計算を省略できるなら、α}} の小数点以下 1=//n// − 1}} 桁までの値を求めずに n}} 桁目を計算できる。

1=//b////n//−1//α//}} の整数部の計算の省略は剰余算することでできる。α}} がBBP型公式}}の一般形で書ける場合、分母 1=//q//}} で分子 1=//b//−//k////p//}} を割った余りだけを計算するよう変形し、最後に和の小数部を取り出す：

特にBBP型公式の特殊化}}の 1=//s// = 1}} の場合では、以下のように書ける：

ここで 1=//x// mod //y//}} は x}} を y}} で割った余りを表すこの math。和の中の剰余算が必要となるのは分子が分母より大きくなる場合のみであり、分子が小さい場合には必要ない。そのため、上述の 1=//b////n//−1//P//}} の例では、1=//k// ≤ //n// − 1}} となる最初の項だけ剰余算を行う。

上述の手順に従い の16進法での小数点以下 n}} 桁目の計算を以下に示す。まずBBP公式}}を以下のように変形する：

それぞれの和の小数部の最初の数桁を計算し、次に右辺全体の小数部を計算する。最終的な結果から小数第一位を取り出せば の小数第 n}} 位が求まる。

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

前述の通り、右辺の2つ目の和に関しては適当な精度で値が収束したと見なされるまで計算すればよいが、1つ目の和は n}} 回の冪剰余浮動小数点数の割り算と足し算も行うが、冪剰余の計算が支配的となる。}}が必要となる。冪剰余の計算のビット計算量は、1=//M//}} を j}} ビット整数の乗算に必要な計算量として、1=//O//)}} で行える対数の底の異なりは定数としてしか寄与しないため、オーダーの計算では底を書かない。}}mvar。従って全体の計算量は 1=//O//)}} となる。乗算の計算量は乗算アルゴリズムに依存するが、筆算と同じ方法なら 1=//M// = //O//}} であり、この場合のBBPアルゴリズムのビット計算量は 1=//O//3))}} となる。乗算をショーンハーゲ・ストラッセン法で行えばビット計算量は 1=//M// = //O//)}} となり、この場合のBBPアルゴリズムのビット計算量は以下の通り：

これは を n}} 桁計算するアルゴリズムよりはわずかに遅く、BBPアルゴリズムのビット計算量は 1=log)}} 倍だけ大きい。

BBPアルゴリズムの結果は n}} 桁目以降の値も含んでおり、//n// − 1}} 桁目ないし //n// + 1}} 桁目の計算結果と比較することで計算結果が正しいことを検証できる。

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

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

BBPは の任意の桁の値を直接計算することができ、その間のすべての桁を計算しなければならない数式よりも少ない計算量で計算できるが、BBPは線形的であり、n}} の値が大きくなるほど計算に要する時間が長くなる。つまり、ある桁が「先に」あるほどBBPの計算に要する時間は長くなり、標準の 計算アルゴリズムと同じようになっていく。

5. 一般化
------

D. J. Broadhurst はBBPアルゴリズムを一般化し、他の多くの定数をほぼ線形時間および対数空間で計算するために使用できるようにしたBroadhurst。カタランの定数、π3}}、π4}}、アペリーの定数 ζ}}、ζ}}、log32}}、log42}}、log52}} および と log2}} の冪乗による様々な積について明示的に結果を与えている。これらの結果は、主に多重対数梯子を用いて得られるものである。

6. 関連項目
-------

円周率の近似
実験数学

7. 出典
-----

8. 注釈
-----

9. 参考文献
-------

10. 外部リンク
---------

リチャード・リプトン, "[1]", weblog post, July 14, 2010.
リチャード・リプトン, "[2]", weblog post, March 15, 2009.
デイヴィッド・H・ベイリー, "[3]", web page with links to Bailey's code implementing the BBP algorithm, September 8, 2006.