Spigot algorithm とは

スピゴットアルゴリズムは、πまたはeのような数学的定数の値を計算するためのアルゴリズムであり、左から右にいくつかの基底(通常2または2の累乗)で出力数字を生成します。この名前は、液体の流れを制御するタップまたはバルブの「スピゴット(spigot)」という言葉の意味から来ています。
スピゴットアルゴリズムへの興味は、計算上の数学の初期にメモリの極限的な制約によって拍車がかけられ、eの数字を計算するアルゴリズムは1968年のセールで紙に登場した。「スピゴットアルゴリズム」という名前は、 Stanley RabinowitzとStan Wagonは、πの桁を計算するアルゴリズムを「πのスピゴットアルゴリズム」と呼ぶことがあります。
RabinowitzとWagonのスピゴットアルゴリズムは、必要な桁数をあらかじめ指定しなければならないという意味で制限されています。 Jeremy Gibbons(2004)は、「ストリーミングアルゴリズム」という用語は、事前の制約なしに無期限に実行できるものを意味しています。さらなる改良は、先行する数字を最初に計算することなく、単一の任意の数字を計算することができるアルゴリズムである。例は、16進数を生成するπの桁抽出アルゴリズムBailey-Borwein-Plouffeの式である。