アルゴリズムの質問: 計算された π の値が正確かどうかをどのように判断するのでしょうか?

以下を読む前に、まず考えてみてください。 πの値を計算する世界記録保持者であるMysticialからの回答を見てみましょう。

質問（ Ishan Sharmaより）：

πの値を順番に出力するプログラムを作成するために、さまざまな方法を試しました。テイラー級数法を試してみましたが、収束が非常に遅かったです（後で自分の結果をインターネットの値と比較したときに、このことに気付きました）。とにかく、より良いアルゴリズムを見つけようとしています。

そこで、このプログラムを書いているときに、いつも問題に遭遇しました。どんなアルゴリズムを使っても、計算した数値が正しいかどうか、どうすればわかるのか、という疑問がありました。

最も投票数が多かった回答（ Mysticialより）：

私はπの値（10兆桁）を計算する世界記録保持者なので、私のささやかな意見を述べさせてください。

新しい世界記録を樹立しようとしているのでない限り、通常の解決策は、計算結果を既知の値と照らし合わせて検証することです。つまり、とても簡単です。

実際、デジタル スニペットをリストした Web ページがあります。計算された値を検証するために使用されます。 http://www.numberworld.org/digits/Pi/

しかし、世界記録の領域に入ると、比較できる既知の値は存在しません。

通常、計算された値を検証する標準的な方法は、別のアルゴリズムを使用して再度計算することです。したがって、計算ミスが 1 つでもあれば、数字は同じにはなりません。

これには、多くの場合、2 倍以上の時間がかかります (2 番目のアルゴリズムは一般に遅いため)。しかし、これは計算を検証する唯一の方法であり、これまで計算されたことのない未知の領域や新しい世界記録を扱うときは常に、計算を検証する唯一の方法です。

スーパーコンピュータが世界記録を保持していた当時、2 つの異なる一般的なAGM アルゴリズムがありました。

• ガウス・ルジャンドルアルゴリズム
• ボルウェインアルゴリズム

どちらも O(N log(N)^2) アルゴリズムであり、かなり単純です。しかし、最近のアルゴリズムは少し異なります。過去 3 つの世界記録では、最速の公式 ( Chudnovsky 公式) を使用して 2 回ではなく 1 回の操作のみを実行しました。

このアルゴリズムはより困難ですが、AGM アルゴリズムよりもはるかに高速です。

次に、デジタル抽出用のBBP 式を使用してこの 2 進数を検証します。

この式を使用すると、それ以前のすべての数値を計算しなくても、任意の 2 進数を計算できます。したがって、最後のいくつかのバイナリ計算値を検証するために使用されます。したがって、完全な計算よりもはるかに高速です。

その利点は次のとおりです。

1. 複雑な計算は 1 つだけ必要です。

欠点は次のとおりです。

1. Bailey–Borwein–Plouffe (BBP) 式の実装が必要です。
2. 検証するには、もう 1 つの手順、つまり 2 進数から 10 進数への基数の変換が必要です。

最後の数桁を検証することですべての数字が正しいことが証明される理由を説明するために、いくつかの詳細を示しました。しかし、計算エラーはすべて最後の数字に渡されるので、これは明らかです。

さて、最後のステップ（変換の検証）は実はとても重要です。元世界記録保持者は、私が最初にプロセスの詳細を伝えなかったため、これを行わないよう強く勧めたことがあります。

そこで、私のブログからこの抜粋を投稿します。

N = 必要な小数点以下の桁数

p = 64ビット素数

10進演算を使用して A を計算し、2進演算を使用して B を計算します。

A = B の場合、「極めて高い確率」のため変換は正しいです。

さらに詳しく知りたい方は、私のブログ記事「円周率 - 5兆桁」をご覧ください。

オリジナルリンク: Stack Overflow翻訳: Bole Online - colleen__chen

翻訳リンク: http://blog.jobbole.com/67766/