BBPアルゴリズムに正確に動作する必要がありますか？

Question

私は計算しようとしています n低メモリ環境でのPIの数字。私は私に利用できる小数を持っていないので、これは Pythonの整数のみのBBPアルゴリズム 素晴らしい出発点でした。一度に1桁のPIを計算するだけです。 Dを設定できる最低の「作業精度の数字数」をどのように決定できますか？

D = 4は多くの正しい数字を与えてくれますが、数桁は1つずつオフになります。たとえば、4の精度で数字393を計算すると0xafdaが得られ、そこから桁0xaを抽出します。ただし、正しい数字は0xBです。

Dをどんなに高く設定しても、十分な数の数字をテストすると、式が誤った値を返すものが見つかるようです。

数字が別のもの（0x3fffまたは0x1000）に「近い」場合に精度を上げることを試みましたが、「閉じる」という適切な定義を見つけることができません。たとえば、桁9798で計算すると0xが与えられますcDE6は0xD000にそれほど近くありませんが、正しい数字は0xDです。

このアルゴリズムを使用して特定の数字を計算するのにどれだけの作業精度が必要かを理解するのを手伝ってもらえますか？

ありがとうございました、

編集
参考のために：

precision (D)   first wrong digit
-------------   ------------------
3               27
4               161
5               733
6               4329
7               21139
8+              ???

一度に1桁を計算していることに注意してください。

for i in range(1,n):
    D = 3 # or whatever precision I'm testing
    digit = pi(i) # extracts most significant digit from integer-only BBP result
    if( digit != HARDCODED_PI[i] ):
        print("non matching digit #%d, got %x instead of %x" % (i,digit,HARDCODED_PI[i]) )

Answer 1

Dをどんなに高く設定しても、十分な数の数字をテストすると、式が誤った値を返すものが見つかるようです。

十分な数の数字をテストしている場合、常にエラーが発生します。アルゴリズムは任意の精度を使用しないため、最終的には丸めエラーが表示されます。

数字が変更されない場合の破損との無制限の反復は、特定の数字数に必要な最小精度を決定するのが難しいでしょう。

あなたの最善の策は、理想的には既知の正しいソースと比較し、一致するまで桁数を正確に増やすか、正しいソースが利用できない場合は、最大精度から始めて、それを経験的に決定することです。 、15桁にはほとんどの場合、丸めエラーが含まれます。）

編集：より正確に言うと、アルゴリズムにはループが含まれています。0..nから、nは計算する桁です。ループの各反復により、一定量のエラーが導入されます。十分な回数をループした後、エラーは計算している最も重要な数字に侵入するため、結果は間違っています。

ウィキペディアの記事では、14桁の精度を使用しており、これは10 ** 8桁を正しく計算するのに十分です。示されているように、精度の数字が少なくなると、より少ない精度が少なくなり、繰り返しが少なくなるとエラーが発生するため、エラーが発生します。最終的な結果は、桁を正しく計算できるnの値が、精度の数字が少ないと低くなることです。

精度のdヘクス桁がある場合、それはd*4ビットです。反復ごとに、0.5ビットの誤差が最も有意なビットで導入されるため、2回の反復でLSBが間違っている可能性があります。合計中に、これらのエラーが追加されるため、蓄積されます。要約されているエラーの数が最も重要な数字でLSBに到達した場合、抽出した単一の数字は間違っています。大まかに言えば、それはn> 2 **（d-0.75）です。 （いくつかの対数ベースに正しい。）

データを経験的に推定すると、概算はn =〜（2 **（2.05*d））であるように見えますが、データポイントはほとんどありません。これは正確な予測因子ではないかもしれません。

選択したBBPアルゴリズムは反復的であるため、シーケンス内の数字を計算するのに徐々に時間がかかります。数字0..n、取るには取得します O(n^2) ステップ。

Wikipediaの記事では、反復を必要としないN'th桁を計算するための式を提供します。これは、反復アルゴリズムと同じ精度の損失を被ることはなく、一定の時間で必要に応じて（または最悪の対数タイプで、弾性率との指数の実装に応じて）計算することができます。 n 数字がかかります O(n) 時間o（n log n）の時間。