7

低メモリ環境で Piのn桁目を計算しようとしています。利用できる小数がないので、このPython の整数のみの BBP アルゴリズムは、優れた出発点でした。一度に 1 桁の Pi を計算するだけで済みます。D に設定できる最小値、つまり「作業精度の桁数」をどのように決定できますか?

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

D をどれだけ高く設定しても、十分な桁数をテストすると、式が正しくない値を返す桁が見つかるようです。

0x3fff や 0x1000 など、数字が別の数字に「近い」場合は精度を上げてみましたが、「近い」の適切な定義が見つかりません。たとえば、数字 9798 で計算すると 0x c de6 が得られます。これは 0xd000 にあまり近くありませんが、正しい数字は 0xd です。

このアルゴリズムを使用して特定の数字を計算するために必要な作業精度を把握するのを手伝ってくれる人はいますか?

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

参照用に編集
:

精度 (D) 最初の桁が間違っています
------------- ------------------
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]) )
4

2 に答える 2

3

D をどれだけ高く設定しても、十分な桁数をテストすると、式が正しくない値を返す桁が見つかるようです。

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

桁が変わらない場合のブレーク付きの無制限の反復では、特定の桁数に必要な最小精度を決定するのが難しくなります。

あなたの最善の策は、経験的に決定することです。理想的には、既知の正しいソースと比較し、一致するまで桁数の精度を上げるか、正しいソースが利用できない場合は、最大の精度から始めます (これは 14 だと思います) 、ほとんどの場合、15 桁目には丸め誤差が含まれるためです。)

編集:より正確に言うと、アルゴリズムにはループが含まれています-from 0..n、n は計算す​​る桁です。ループの反復ごとに、一定量のエラーが発生します。十分な回数ループした後、エラーは計算している最上位桁に侵入するため、結果は間違ったものになります。

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

D桁の16進数の精度がある場合、それはD * 4ビットです。反復ごとに 0.5 ビットのエラーが最下位ビットに導入されるため、2 回の反復では LSB が間違っている可能性があります。合計中に、これらのエラーが追加され、累積されます。合計されたエラーの数が最上位桁の LSB に達した場合、抽出した 1 桁は間違っています。大雑把に言えば、N > 2**(D-0.75) のときです。(いくつかの対数の底に修正します。)

経験的にデータを推定すると、おおよその適合は N=~(2**(2.05*D)) のようですが、データポイントが少ないため、これは正確な予測因子ではない可能性があります。

選択した BBP アルゴリズムは反復的であるため、シーケンス内の数字の計算に時間がかかるようになります。数字 0..n を計算するには、O(n^2)手順を実行します。

ウィキペディアの記事では、累乗と有理数だけで、反復を必要としない n 桁目を計算する式が示されています。これは、反復アルゴリズムと同じように精度が失われることはなく、必要に応じて定数時間で pi の任意の桁を計算できます (または、モジュラスによるべき乗の実装に応じて、最悪の場合は対数型)。そのため、n桁の計算にはO(n)時間がかかる可能性があります。 O(n log n)。

于 2010-05-29T13:33:55.173 に答える