ベイリー＝ボールウェイン＝プラウフの公式のソースを表示

'''ベイリー＝ボールウェイン＝プラウフの公式'''（ベイリー＝ボールウェイン＝プラウフのこうしき、{{lang-en-short|Bailey–Borwein–Plouffe formula}}）あるいはBBP公式は、[[1995年]]に[[サイモン・プラウフ]]によって発見された[[円周率]] {{π}} に関する以下の[[公式]]である。
:<math display="block">
\pi = \sum_{k = 0}^{\infty} 
\left[
  \frac{1}{16^k}
  \left(
      \frac{4}{8k + 1}
    - \frac{2}{8k + 4}
    - \frac{1}{8k + 5}
    - \frac{1}{8k + 6}
  \right)
\right]
</math>（{{equationRef|BBP公式}}）{{sfn|Bailey|Borwein|Plouffe|1997|loc=1. Introduction, Theorem 1, (1.2)}}

名称はBBP公式に関する論文 {{harv|Bailey|Borwein|Plouffe|1997}} の著者ら{{ill2|デイヴィッド・H・ベイリー|en|David H. Bailey (mathematician)}}、{{ill2|ピーター・ボールウェイン|en|Peter Borwein}}、プラウフに因む。BBP公式は論文公開以前にもプラウフが自身のサイトで紹介していた<ref>[http://plouffe.fr プラウフのサイト].</ref>。

BBP公式は、先行する桁を計算せずに {{pi}} の[[十六進法]]で {{mvar|n}} 桁目（[[二進法]]で {{math|4''n''}} 桁目）の数を直接求める{{ill2|スピゴット・アルゴリズム|en|Spigot algorithm}}を与える。これは {{pi}} の[[十進法]]で {{mvar|n}} 桁目を計算するものではない{{sfn|Gourdon|Sebah|2003}}。そのような公式はプラウフによって[[2022年]]に発見されている<ref>{{MathWorld| title=Digit-Extraction Algorithm| urlname=Digit-ExtractionAlgorithm}}</ref>。BBPとBBPに触発された[[アルゴリズム]]は、分散コンピューティングを使って {{pi}} の多くの桁を計算するPiHex<ref>{{cite web|title=PiHex Credits|url=http://wayback.cecm.sfu.ca/projects/pihex/credits.html|website=Centre for Experimental and Constructive Mathematics|publisher=Simon Fraser University|accessdate=30 March 2018|archiveurl=https://web.archive.org/web/20170610094408/http://wayback.cecm.sfu.ca/projects/pihex/credits.html|archivedate=2017-06-10|url-status=live|date=March 21, 1999}}</ref>などのプロジェクトで使用されている。BBPアルゴリズムの発見は驚くべきものであった。BBPアルゴリズムの発見以前、{{pi}} のような[[超越数]]の {{mvar|n}} 桁目を直接計算するのは、最初の {{mvar|n}} 桁を計算するのと同程度に難しいと広く信じられていた{{sfn|Bailey|Borwein|Plouffe|1997|loc=1. Introduction}}。

{{pi}} 以外の[[無理数]]についてもBBP公式と類似の式が得られている。それらの類似の式は'''BBP型公式'''（{{en|BBP-typed formulae}}）<ref name="Ref_a">{{MathWorld| title=BBP Formula| urlname=BBPFormula}}</ref>または'''BBP系公式'''と呼ばれる。BBP型公式の一般形は以下のように表される：
:<math display="block">
\alpha = \sum_{k = 0}^\infty
\left[
  \frac{1}{b^k} \frac{p(k)}{q(k)} \right]
</math>（{{equationRef|BBP型公式}}）{{sfn|Bailey|Borwein|Plouffe|1997|loc=3. The Algorithm}}{{efn2|{{harvnb|Bailey|Borwein|Plouffe|1997}} では {{mvar|b}} の指数は {{mvar|ck}} となっていて、正整数 {{mvar|c}} が付け加わっている。}}
ここで {{mvar|&alpha;}} は無理数、{{math|1=''p''(''k''), ''q''(''k'')}} は {{mvar|k}} の整数係数[[多項式]]、{{mvar|b}} は通常、[[位取り記数法]]の底であり {{math|2}} 以上の整数を表すが、より一般には[[実数]]でもよい。また {{mvar|q}} は {{mvar|k}} の範囲でゼロにならず、{{mvar|p}} の次数は {{mvar|q}} より小さい。

ある数 {{mvar|&alpha;}} に対しBBP型公式を（すなわち {{math|''p''(''k'')}}, {{math|''q''(''k'')}}, {{mvar|b}} を）与える系統だったアルゴリズムは知られておらず、ある数に対するBBP型公式は今のところ[[実験数学|実験的な]]方法によってのみ得られている。

== 特殊化 ==

一般の{{eqNoteN|BBP型公式}}の特殊な例として、多くの結果を与えたものに以下がある：
<math display="block">
P(s, b, m, A) = \sum_{k=0}^{\infty}
\left[
  \frac{1}{b^k}
  \sum_{j=1}^m \frac{a_j}{(mk+j)^s}
\right]
</math>（{{equationRef|BBP型公式の特殊化}}）

ここで {{math2|1=''s'', ''b'', ''m''}} は[[整数]]、{{math|''A'' {{=}} (''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a<sub>m</sub>'')}} は整数の[[数列]]である。
[[関数 (数学)|関数]] {{mvar|P}} はいくつかの解に対して簡潔な表記を与える。例えば、元の{{eqNoteN|BBP公式}}は、{{math|1=''s'' = 1}}, {{math|1=''b'' = 16}}, {{math|1=''m'' = 8}}, {{math2|1=''A'' = [4, 0, 0, &minus;2, &minus;1, &minus;1, 0, 0]}} として以下のように書くことができる。
<math display="block">
\pi = P\left(
  1,
  16,
  8,
  [4, 0, 0, -2, -1, -1, 0, 0]
\right)
</math>

=== 既知のBBP型公式 ===

BBP型公式のうちBBP公式より以前から知られているもので、{{eqNoteN|BBP型公式の特殊化}} {{mvar|P}} が簡潔な形になるものに、次のものがある。
: <math display="block">
\begin{align}
\ln\frac{10}{9}
&=
    \frac{1}{10} 
  + \frac{1}{200}
  + \frac{1}{3\,000}
  + \cdots \\
&= 
  \frac{1}{10}
  \sum_{k=0}^\infty 
  \left[
    \frac{1}{10^k}
    \left( \frac{1}{k+1} \right) 
  \right] \\
&= \frac{1}{10} P\left(1, 10, 1, [1] \right)
\end{align}
</math>
: <math display="block">
\begin{align}
\ln 2
&=
    \frac{1}{2}
  + \frac{1}{2 \cdot 2^2}
  + \frac{1}{3 \cdot 2^3}
  + \cdots \\
&=
  \frac{1}{2} \sum_{k=0}^\infty 
  \left[
    \frac{1}{2^k} \left( \frac{1}{k + 1} \right)
  \right] \\
&=
  \frac{1}{2} P\left( 1, 2, 1, [1] \right).
\end{align}</math>
（実際、恒等式
:<math>\ln\frac{a}{a-1} = \sum_{k=1}^\infty \frac{1}{a^k \cdot k}</math>
は {{math|1=''a'' &gt; 1}} に対して成り立つ）

プラウフは、[[逆三角関数]]の[[冪級数]]にも触発された（{{mvar|P}} 表記は {{mvar|b}} が整数でない場合にも一般化できる）。
: <math display="block">
\begin{align}
\arctan\frac{1}{b}
&=
    \frac{1}{b}
  - \frac{1}{b^3 3}
  + \frac{1}{b^5 5}
  - \cdots \\
&=
  \frac{1}{b}
  \sum_{k=0}^\infty
  \left[
    \frac{1}{b^{4k}}
    \left(
        \frac{1}{4k + 1}
      + \frac{-b^{-2}}{4k + 3}
    \right) 
  \right] \\
&=
  \frac{1}{b}
  P\left( 1, b^4, 4, \left[1, 0, -b^{-2}, 0\right] \right)
\end{align}
</math>

=== 新しい等式の探索 ===

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

== 発見と導出 ==

円周率のBBP公式の原型は、1995年にプラウフが[[PSLQアルゴリズム]]を用いて見つけたものである。また、{{eqNoteN|BBP型公式の特殊化}} {{mvar|P}} を用いて表現可能である。
: <math display="block">
\begin{align}
\pi &= \sum_{k = 0}^\infty
  \left[
    \frac{1}{16^k} \left(
        \frac{4}{8k + 1} 
      - \frac{2}{8k + 4} 
      - \frac{1}{8k + 5} 
      - \frac{1}{8k + 6} 
    \right)
  \right] \\
  &= P\left( 1, 16, 8, (4, 0, 0, -2, -1, -1, 0, 0) \right)\,.
\end{align}
</math>

上式は、以下の等価な2多項式の比に還元される。
: <math display="block">
\pi = \sum_{k = 0}^\infty
  \left[
    \frac{1}{16^k} \left(
      \frac
        {120k^2 + 151k + 47}
        {512k^4 + 1024k^3 + 712k^2 + 194k + 15} 
    \right)
  \right]
</math>
この式は、かなり単純な証明によって、{{pi}} に等しいことが示されている{{sfn|Bailey|Borwein|Borwein|Plouffe|1997}}。

== BBPアルゴリズム ==

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

一般に数 {{mvar|&alpha;}} の {{mvar|b}} 進法で小数点以下 {{mvar|n}} 桁目の値を求めるには、{{mvar|&alpha;}} に {{math|1=''b''<sup>''n''&minus;1</sup>}} を掛けて（{{math|1=''n'' &minus; 1}} 桁左にシフトして）その小数部分の最上位の桁を計算すればよい。BBPアルゴリズムでは {{mvar|n}} 桁目だけを必要とするため、小数部の計算は通常の[[浮動小数点数]]の演算で済む。{{math|1=''b''<sup>''n''&minus;1</sup>''&alpha;''}} の整数部分の計算を省略できるなら、{{mvar|&alpha;}} の小数点以下 {{math|1=''n'' &minus; 1}} 桁までの値を求めずに {{mvar|n}} 桁目を計算できる。

{{math|1=''b''<sup>''n''&minus;1</sup>''&alpha;''}} の整数部の計算の省略は[[剰余]]算することでできる。
{{mvar|&alpha;}} が{{eqNoteN|BBP型公式}}の一般形で書ける場合、分母 {{math|1=''q''(''k'')}} で分子 {{math|1=''b''<sup>(''n''&minus;1)&minus;''k''</sup>''p''(''k'')}} を割った余りだけを計算するよう変形し、最後に和の小数部を取り出す：
: <math display="block">
\left\{ b^{n-1}\alpha \right\} \bmod 1
 =
\left\{
  \sum_{k=0}^\infty
  \frac{
    b^{(n-1)-k} p(k) \bmod q(k)
  }{q(k)}
\right\}
\bmod 1
</math>
特に{{eqNoteN|BBP型公式の特殊化}}の {{math|1=''s'' = 1}} の場合では、以下のように書ける：
: <math display="block">
\left\{
  b^{n-1}P(1, m, b, A)
\right\}
\bmod 1
=
\left\{
  \sum_{j=1}^m
  a_j
  \left[
    \sum_{k=0}^{\infty}
    \frac{
      b^{(n - 1) - k} \bmod (mk + j)
    }{mk + j}
  \right]
\right\} \bmod 1
</math>
ここで {{math|1=''x'' mod ''y''}} は {{mvar|x}} を {{mvar|y}} で割った余りを表す{{efn2|この {{math|mod}} 演算の対象は整数に限らず、{{math|1=''x'' &minus; [''x'' / ''y''] ''y''}} の意味で使う。ここで {{math|1=[&sdot;]}} は引数の整数部を取り出す関数である。文献によっては引数の小数部を表す関数を {{math|1={{mset|&sdot;}}}} と定義し、{{math|mod}} の代わりに使用している（{{math|1=''x'' mod ''y'' = {{mset|''x'' / ''y''}}''y''}}）。}}。和の中の剰余算が必要となるのは分子が分母より大きくなる場合のみであり、分子が小さい場合には必要ない。そのため、上述の {{math|1=''b''<sup>''n''&minus;1</sup>''P''}} の例では、{{math|1=''k'' &le; ''n'' &minus; 1}} となる最初の項だけ剰余算を行う。

上述の手順に従い {{pi}} の16進法での小数点以下 {{mvar|n}} 桁目の計算を以下に示す。まず{{eqNoteN|BBP公式}}を以下のように変形する：
: <math display="block">
16^{n-1}\pi
= 
    4 \sum_{k=0}^\infty
    \frac{16^{(n-1)-k}}{8k + 1}
  - 2 \sum_{k=0}^\infty
    \frac{16^{(n-1)-k}}{8k + 4}
  - \sum_{k=0}^\infty
    \frac{16^{(n-1)-k}}{8k + 5}
  - \sum_{k=0}^\infty
    \frac{16^{(n-1)-k}}{8k + 6}
</math>
それぞれの和の小数部の最初の数桁を計算し、次に右辺全体の小数部を計算する。最終的な結果から小数第一位を取り出せば {{pi}} の小数第 {{mvar|n}} 位が求まる。

例えば最初の和の小数部は以下のようになる：
: <math display="block">
\left\{
  \sum_{k=0}^\infty
  \frac{16^{(n - 1) - k}}{8k + 1}
\right\} \bmod 1
=
\left\{
  \sum_{k=0}^{n - 1}
  \frac{
    16^{(n - 1) - k}
    \bmod
    (8k + 1)
  }{8k + 1}
+ \sum_{k=n}^\infty
  \frac{16^{(n - 1) - k}}{8k + 1}
\right\} \bmod 1
</math>
前述の通り、右辺の2つ目の和に関しては適当な精度で値が収束したと見なされるまで計算すればよいが、1つ目の和は {{mvar|n}} 回の[[冪剰余]]{{efn2|浮動小数点数の割り算と足し算も行うが、[[冪剰余]]の計算が支配的となる。}}が必要となる。
一方で1回の冪剰余の計算は、{{math|1=''M''(''j'')}} を {{mvar|j}} ビット整数の乗算に必要な計算量として、{{math|1=''O''(log ''n'' &sdot; ''M''(log ''n''))}} のビット計算量で行える{{efn2|対数の底の異なりは定数としてしか寄与しないため、オーダーの計算では底を書かない。}}{{efn2|{{mvar|M}} の引数が {{math|log ''n''}} となっているのは、除数 {{mvar|q}} に対する冪剰余の計算には {{math|''q''<sup>2</sup>}} を表せる長さを持つ整数型が必要となるためである。{{math|''q''<sup>2</sup>}} のビット長は {{math|1=1 + 2log<sub>2</sub> ''q''}} であり、これは漸近的に {{math|log ''q''}} に等しい。BBPアルゴリズムによる {{pi}} の計算では除数は高々 {{mvar|n}} のオーダーになるから、{{math|1=''q'' &approx; ''n''}} と考えてよく、ビット長は {{math|log ''n''}} 程度と見積もれる。{{pi}} 以外の例では {{mvar|q}} の取り得る大きさは異なり、例えば {{math|1=''q'' &approx; ''n''<sup>2</sup>}} などになり得る。ビット計算量の見積もりには顕れないが、ナイーブな方法では浮動小数点数の精度が不足し得る。}}。
従って全体の計算量は {{math|1=''O''(''n'' &sdot; log ''n'' &sdot; ''M''(log ''n''))}} となる。

乗算の計算量は乗算アルゴリズムに依存する。例えば、乗算を[[筆算]]と同様に行えば乗算の計算量は {{math|1=''M''(''j'') = ''O''(''j''<sup>2</sup>)}} となり、この場合のBBPアルゴリズムの計算量は {{math|1=''O''(''n'' &sdot; (log ''n'')<sup>3</sup>))}} となる。乗算を[[ショーンハーゲ・ストラッセン法]]で行えば乗算の計算量は {{math|1=''M''(''j'') = ''O''(''j'' &sdot; log ''j'' &sdot; log(log ''j''))}} となり、この場合のBBPアルゴリズムの計算量は
: <math display="block">
O(
  n 
  \cdot (\log n)^2 
  \cdot \log(\log n)
  \cdot \log(\log(\log n))
)
</math>
となる。
これは（ショーンハーゲ・ストラッセン法で乗算を実装した場合の）{{pi}} を {{mvar|n}} 桁計算するアルゴリズムよりはわずかに遅く、BBPアルゴリズムのビット計算量は {{math|1=log(log(log ''n''))}} 倍だけ大きい。

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

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

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

BBPは {{pi}} の任意の桁の値を直接計算することができ、その間のすべての桁を計算しなければならない数式よりも少ない計算量で計算できるが、BBPは線形的（<math>O(n (\log n)^{O(1)})</math>{{sfn|Bailey|Borwein|Plouffe|1997}}）であり、{{mvar|n}} の値が大きくなるほど計算に要する時間が長くなる。つまり、ある桁が「先に」あるほどBBPの計算に要する時間は長くなり、標準の {{pi}} 計算アルゴリズムと同じようになっていく<ref>{{cite web
 | last   = Bailey
 | first  = David H.
 | title  = The BBP Algorithm for Pi
 | date   = 8 September 2006
 | quote  = Run times for the BBP algorithm ... increase roughly linearly with the position ''d''.
 | url    = http://www.experimentalmath.info/bbp-codes/bbp-alg.pdf
 | accessdate = 17 January 2013}}</ref>。

== 一般化 ==
D. J. Broadhurst はBBPアルゴリズムを一般化し、他の多くの定数をほぼ線形時間および対数空間で計算するために使用できるようにした{{sfn|Broadhurst|1998}}。[[カタランの定数]]、{{math|π<sup>3</sup>}}、{{math|π<sup>4</sup>}}、[[アペリーの定数]] {{math|ζ(3)}}、{{math|ζ(5)}}（{{math|ζ(''x'')}} は[[リーマンゼータ函数]]）、{{math|log<sup>3</sup>2}}、{{math|log<sup>4</sup>2}}、{{math|log<sup>5</sup>2}} および {{pi}} と {{math|log2}} の冪乗による様々な積について明示的に結果を与えている。これらの結果は、主に[[多重対数関数|多重対数梯子]]を用いて得られるものである。

== 関連項目 ==
*[[円周率の近似]]
*[[実験数学]]
*{{ill2|ベラールの公式|en|Bellard's formula}}

== 出典 ==
{{脚注ヘルプ}}
{{reflist}}

== 注釈 ==
{{脚注ヘルプ}}
{{notelist2}}

== 参考文献 ==
* {{cite journal
 | last1 = Bailey
 | first1 = David H.
 | last2 = Borwein
 | first2 = Peter B.
 | last3 = Plouffe
 | first3 = Simon
 | year = 1997
 | title = On the Rapid Computation of Various Polylogarithmic Constants
 | journal = Mathematics of Computation
 | volume = 66
 | issue = 218
 | pages = 903–913
 | doi = 10.1090/S0025-5718-97-00856-9
 | mr = 1415794
 | doi-access = free
 | ref = harv
}}
* {{cite journal
 | last1 = Bailey
 | first1 = David H.
 | last2 = Borwein
 | first2 = Jonathan M.
 | last3 = Borwein
 | first3 = Peter B.
 | last4 = Plouffe
 | first4 = Simon
 | year = 1997
 | journal = Mathematical Intelligencer
 | volume = 19
 | issue = 1
 | pages = 50–57
 | doi=10.1007/BF03024340
 | mr=1439159
 | title=The quest for pi
 | ref=harv
}}
* {{cite web2
 | last   = Gourdon
 | first  = Xavier
 | last2  = Sebah
 | first2 = Pascal
 | website= numbers.computation.free.fr
 | title  = N-th Digit Computation
 | date   = 2003-02-12
 | url    = http://numbers.computation.free.fr/Constants/Algorithms/nthdigit.html
 | accessdate = 2023-01-22
 | ref    = {{sfnref|Gourdon|Sebah|2003}}
}}
* {{cite journal
 |first=D. J.
 |last=Broadhurst
 |title=Polylogarithmic ladders, hypergeometric series and the ten millionth digits of ζ(3) and ζ(5)
 |year=1998
 |arxiv=math.CA/9803067
 |ref=harv
}}

== 外部リンク ==
* {{ill2|リチャード・リプトン|en|Richard Lipton}}, "[http://rjlipton.wordpress.com/2010/07/14/making-an-algorithm-an-algorithm-bbp/ Making An Algorithm An Algorithm — BBP]", weblog post, July 14, 2010.
* リチャード・リプトン, "[http://rjlipton.wordpress.com/2009/03/15/cooks-class-contains-pi/ Cook’s Class Contains Pi]", weblog post, March 15, 2009.
* {{cite web
|url=https://www.davidhbailey.com/dhbpapers/bbp-formulas.pdf
|first1=David H.
|last1=Bailey
|title=A compendium of BBP-type formulas for mathematical constants, updated 15 Aug 2017
|accessdate=2019-03-31}}
* {{ill2|デイヴィッド・H・ベイリー|en|David H. Bailey (mathematician)}}, "[http://www.experimentalmath.info/bbp-codes/ BBP Code Directory]", web page with links to Bailey's code implementing the BBP algorithm, September 8, 2006.

{{デフォルトソート:へいりいほおるうえいんふらうふのこうしき}}
[[Category:円周率]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]