スピゴットアルゴリズム

スピゴットアルゴリズムは、超越数( πやeなど)の値を計算するアルゴリズムです。このアルゴリズムは、左から右へ数字の桁を順番に生成し、アルゴリズムが進むにつれて精度が増します。また、スピゴット アルゴリズムは、必要な中間ストレージの量を最小限に抑えることも目的としています。この名前は、液体の流れを制御する蛇口またはバルブを意味する「スピゴット」という言葉の意味に由来しています。スピゴット アルゴリズムは、完全な数を格納および処理して、目的の超越数に連続的により正確な近似値を生成するアルゴリズムとは対照的です。

計算数学の初期の頃、メモリの極度の制約によりスピゴットアルゴリズムへの関心が高まり、eの桁を計算するそのようなアルゴリズムは1968 年に Sale の論文に登場しました。 ^[1] 1970 年に Abdali は、連続する項の比が項の位置の整数関数の商として表される級数の和を計算するためのより一般的なアルゴリズムを発表しました。このアルゴリズムは、上記の条件を満たす三角関数、対数、超越数の多くのよく知られた級数に適用できます。^{[2] 「スピゴットアルゴリズム」という名前は、Stanley Rabinowitz と}Stan Wagonによって作られたようです。π の桁を計算する彼らのアルゴリズムは、「 πのスピゴットアルゴリズム」と呼ばれることもあります。^[3]

ラビノウィッツとワゴンのスピゴットアルゴリズムは、処理される無限級数の項の数を事前に指定する必要があるという意味で、制限があります。「ストリーミングアルゴリズム」 ^[4]という用語は、この制限のないアプローチを示しています。これにより、計算が進むにつれて中間ストレージの量を変えながら、計算を無制限に実行できます。

スピゴットアプローチの変形では、先行する数字を計算せずに超越数の任意の1桁を計算するために使用できるアルゴリズムを使用します。例としては、ベイリー・ボーウェイン・プルーフの公式があります。これは、16進数の数字を生成するπの数字抽出アルゴリズムです。アルゴリズムの基礎となる無限級数の必然的な切り捨ては、計算される項の数によって結果の精度が制限される可能性があることを意味します。

この例では、2の自然対数（OEISのシーケンスA068426） の2進数を次の恒等式を使用して計算することにより、スピゴットアルゴリズムの動作を示しています。

${\displaystyle \ln(2)=\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.}$

たとえば、8 桁目から 2 進数の計算を始めるには、この恒等式に 2 ⁷を掛けます(7 = 8 − 1 なので)。

${\displaystyle 2^{7}\ln(2)=2^{7}\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.}$

次に、無限和を、2 の指数が 0 以上である「頭」と、2 の指数が負である「尾」に分けます。

${\displaystyle 2^{7}\ln(2)=\sum _{k=1}^{7}{\frac {2^{7-k}}{k}}+\sum _{k=8}^{\infty }{\frac {1}{k2^{k-7}}}\,.}$

この値の小数部分のみに関心があるので、「ヘッド」の各被加数を次のように置き換えることができます。

${\displaystyle {\frac {2^{7-k}}{k}}{\bmod {1}}={\frac {2^{7-k}{\bmod {k}}}{k}} \,.}$

これらの各項を計算し、小数部分のみを残して合計に追加すると、次のようになります。

合計を切り捨てることによって生じる誤差が最終項よりも小さくなることに注意しながら、「末尾」にいくつかの項を追加します。

「ヘッド」と「テール」の最初の数項を足し合わせると次のようになります。

${\displaystyle 2^{7}\ln(2){\bmod {1}}\approx {\frac {64}{105}}+{\frac {37}{360}}=0.10011100\ldots _{2}+0.00011010\ldots _{2}=0.1011\ldots _{2}\,,}$

したがって、ln(2) の 2 進展開における 8 番目から 11 番目の 2 進桁は 1、0、1、1 です。最初の 7 つの 2 進桁の値を計算していないことに注意してください。実際、それらに関するすべての情報は、 「ヘッド」合計でモジュラー演算を使用することによって意図的に破棄されています。

同じアプローチを使用して、任意のn番目の位置から始まる ln(2) の 2 進展開の桁を計算することができます。「ヘッド」の合計の項の数はnとともに直線的に増加しますが、効率的なモジュラー指数法が使用されている場合、各項の複雑さはnの対数とともにのみ増加します。計算と中間結果の精度、および「テール」の合計から取得される項の数はすべてnとは無関係であり、計算される 2 進桁の数によってのみ異なります。開始位置に関係なく、 単精度演算を使用して約 12 の 2 進桁を計算できます。

• アルント、ヨルグ。 Haenel、Christoph、「π unleashed」、Springer Verlag、2000。
• ワイスタイン、エリック W.「スピゴットアルゴリズム」。マスワールド。