782

円周率の桁を順番に与えるプログラムを実装するために、さまざまな方法を試していました。テイラー級数法を試しましたが、収束が非常に遅いことがわかりました（しばらくしてから結果をオンライン値と比較したところ）。とにかく、私はより良いアルゴリズムを試しています。

それで、プログラムを書いている間、私はすべてのアルゴリズムと同様に問題に行き詰まりました：n私が計算した数字が正確であることをどうやって知ることができますか？

4

6 に答える 6

1645

私は円周率のほとんどの桁の現在の世界記録保持者なので、2セントを追加します：

実際に新しい世界記録を設定しているのでない限り、一般的な方法は、計算された数字を既知の値と照合することです。とても簡単です。

実際、私はそれらに対して計算を検証する目的で数字のスニペットをリストするWebページを持っています：http ：//www.numberworld.org/digits/Pi/

しかし、世界記録の領域に入るとき、比較するものは何もありません。

歴史的に、計算された数字が正しいことを確認するための標準的なアプローチは、2番目のアルゴリズムを使用して数字を再計算することです。したがって、どちらかの計算がうまくいかない場合、最後の数字は一致しません。

これは通常、必要な時間の2倍以上になります（2番目のアルゴリズムは通常遅いため）。しかし、これまで計算されたことのない数字と新しい世界記録の未知の領域に迷い込んだら、計算された数字を検証する唯一の方法です。

スーパーコンピューターが記録を打ち立てていた時代には、2つの異なるAGMアルゴリズムが一般的に使用されていました。

これらは両方ともO(N log(N)^2)、実装がかなり簡単なアルゴリズムです。

しかし、最近は少し違います。最後の3つの世界記録では、2つの計算を実行する代わりに、既知の最速の式（ Chudnovsky Formula）を使用して1つの計算のみを実行しました。

ここに画像の説明を入力してください

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

次に、数字抽出用のBBP式を使用して2進数を検証します。

ここに画像の説明を入力してください

この式を使用すると、前のすべての桁を計算せずに、任意の2進数を計算できます。したがって、計算された最後の2進数を検証するために使用されます。したがって、完全な計算よりもはるかに高速です。

これの利点は次のとおりです。

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

欠点は次のとおりです。

  1. Bailey–Borwein–Plouffe（BBP）式の実装が必要です。
  2. 2進数から10進数への基数変換を確認するには、追加の手順が必要です。

最後の数桁を確認することで、すべての桁が正しいことを意味する理由について、詳細を説明しました。ただし、計算エラーは最後の桁に伝播するため、これは簡単にわかります。

ここで、この最後のステップ（変換の検証）は実際にはかなり重要です。以前の世界記録保持者の1人が実際にこれについて私たちに呼びかけました。最初は、それがどのように機能するかについて十分な説明をしていなかったからです。

だから私は私のブログからこのスニペットを引き出しました：

N = # of decimal digits desired
p = 64-bit prime number

ここに画像の説明を入力してください

基数10の算術を使用してAを計算し、2進算術を使用してBを計算します。

ここに画像の説明を入力してください

の場合A = B、「非常に高い確率」で、変換は正しいです。

詳細については、私のブログ投稿Pi-5TrillionDigitsを参照してください。

于 2013-01-11T17:28:04.953 に答える
48

間違いなく、あなたの目的（私は単なるプログラミング演習であると思います）のために、最良のことは、ウェブ上の円周率の数字のリストのいずれかに対して結果をチェックすることです。

そして、これらの値が正しいことをどのようにして知ることができますか？さて、アルゴリズムの実装が正しいことを証明するためのコンピュータサイエンスの方法があると言えます。

もっと実際的には、異なる人々が異なるアルゴリズムを使用し、彼ら全員が小数点以下1000桁（数百万、何でも）に同意する場合、それはあなたに彼らがそれを正しくしたという暖かいあいまいな感じを与えるはずです。

歴史的に、ウィリアムシャンクスは、1873年に円周率を小数点以下707桁まで公開しました。かわいそうな男、彼は小数点以下528桁から始めて間違いを犯しました。

非常に興味深いことに、1995年に、前のすべての桁を計算することなく、円周率のn番目の桁（基数16）を直接計算するプロパティを持つアルゴリズムが公開されました。

最後に、最初のアルゴリズムがそうではなかったことを願っています。pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...これはプログラミングが最も簡単かもしれませんが、それを行うのに最も遅い方法の1つでもあります。より高速なアプローチについては、ウィキペディアのpi記事を確認してください。

于 2013-01-11T17:44:23.057 に答える
21

複数のアプローチを使用して、それらが同じ答えに収束するかどうかを確認できます。または、ネットからいくつかを取得します。チュドノフスキーアルゴリズムは通常、円周率を計算する非常に高速な方法として使用されます。http://www.craig-wood.com/nick/articles/pi-chudnovsky/

于 2013-01-11T17:21:57.883 に答える
15

テイラー級数は、円周率を近似する1つの方法です。前述のように、ゆっくりと収束します。

テイラー級数の部分和は、円周率の真の値から離れた次の項の乗数内にあることを示すことができます。

piを近似する他の方法には、最大誤差を計算する同様の方法があります。

数学的に証明できるので、これを知っています。

于 2013-01-11T17:24:55.493 に答える
5

sinとcosの（かなり）すばやく収束するべき級数を使用してsin(pi/2)（またはそのことについては）計算を試すことができます。（さらに良い：収束を速くcos(pi/2)するために、さまざまな倍増式を使用して、より近くで計算します。）x=0

ところで、シリーズを使用するよりも優れているのtan(x)は、たとえばブラックボックスとして計算cos(x)することで（たとえば、上記のようにテイラー級数を使用できます）、ニュートンを介して求根アルゴリズムを実行することです。確かに優れたアルゴリズムはありますが、大量の数字を検証したくない場合は、これで十分です（実装するのはそれほど難しいことではなく、なぜそれが機能するのかを理解するために少しの微積分が必要です）。

于 2013-01-13T19:09:22.653 に答える
0

質問に答えるために、アークタンの桁ごとの評価のためのアルゴリズムがあります、pi =4アークタン1:)

于 2021-03-20T12:41:13.767 に答える