GMPライブラリとC++を使用して、円周率の桁を計算するGauss-Legendreアルゴリズムの実装をコーディングしました。
正しい出力がありますが、コードで精度を指定する必要があるため、どの時点で出力が「悪くなる」かわからないという問題があります。
64ビット精度を使用した出力は次のとおりです。3.141592653589793238* 35 *、最後の2桁が正しくありません。
私の質問は、円周率のn桁が必要な場合、精度bのビット数、およびアルゴリズムの反復回数iが必要になるかどうかです。
ありがとうございました
Gauss-Legendre アルゴリズム (AGM アルゴリズムとも呼ばれる) では、全体を通して完全な精度が必要です。
ニュートン法の反復とは異なり、AGM 反復は自己修正しません。したがって、最初から完全な精度が必要です。さらに、追加の保護桁が必要です。
私の質問は、
n円周率の桁数が必要な場合、何ビットの精度bが必要になるかということです。
n最初に、 (10 進数) の数字をb2 進数のビットに変換する必要があります。つまり、次のようになります。
log(10)
b = n ---------- + epsilon
log(2)
epsilonガード桁数はどこにありますか。必要な量は、実装と丸めの動作によって異なりますが、通常、反復回数には 100 ビットで十分です。
必要な反復回数について。これは、経験的な証拠によって見つけることができます。
これは、Gauss-Legendre アルゴリズムを使用して Pi を 1 億桁まで計算する、私が書いた小さなアプリの出力です。
================================================================
Computing pi to 100000000 digits:
Threads: 8
Starting AGM... 1.394965 seconds
Starting Iteration 0... -3 (error in decimal digits)
Starting Iteration 1... -9
Starting Iteration 2... -20
Starting Iteration 3... -42
Starting Iteration 4... -85
Starting Iteration 5... -173
Starting Iteration 6... -347
Starting Iteration 7... -696
Starting Iteration 8... -1395
Starting Iteration 9... -2792
Starting Iteration 10... -5586
Starting Iteration 11... -11175
Starting Iteration 12... -22352
Starting Iteration 13... -44706
Starting Iteration 14... -89414
Starting Iteration 15... -178829
Starting Iteration 16... -357661
Starting Iteration 17... -715324
Starting Iteration 18... -1430650
Starting Iteration 19... -2861302
Starting Iteration 20... -5722607
Starting Iteration 21... -11445216
Starting Iteration 22... -22890435
Starting Iteration 23... -45780871
Starting Iteration 24... -91561745
Starting Iteration 25... -183123492
AGM: 118.796792 seconds
Finishing... 3.033239 seconds
Radix Conversion... 2.924844 seconds
Total Wall Time: 126.151086 seconds
CPU Utilization: 495.871%
CPU Efficiency: 61.984%
Writing to "pi.txt"... Done
したがって、1 億 8,300 万桁には 25 回の反復で十分です。同様に、反復ごとに 2 倍になるため、基本的な対数計算を実行して、必要な反復回数を計算できます。