チュドノフスキーアルゴリズム

πの桁を高速に計算する方法

チュドノフスキー法は、ラマヌジャンの $π$ 公式に基づいて $π$ の桁を高速に計算する手法である。 1988年にチュドノフスキー兄弟によって発表された^{[1]この法則は、} $πを$ 小数点10億桁まで計算するために使用された。^[2]

この技術は、2009年12月に $π$ の2.7兆桁、^[3] 2011年10月に10兆桁、^[4]^[5] 2016年11月に22.4兆桁、^[6] 2018年9月～2019年1月に31.4兆桁、^[7] 2020年1月29日に50兆桁、^[8] 2021年8月14日に62.8兆桁、^[9] 2022年3月21日に100兆桁、^[10] 2024年3月14日に105兆桁、^[11] 2024年6月28日に202兆桁^[12 ]の世界記録の計算に使用されました。最近では、2025年4月2日に記録が再び破られ、円周率は300兆桁です。^[13]^{[14]これは}y-cruncherのアルゴリズムを使用して行われました。

アルゴリズム

このアルゴリズムは、負のヘーグナー数、j 関数、および次の急速に収束する一般化超幾何級数に基づいている：^[15] $d=-163$ $j\left({\tfrac {1+i{\sqrt {-163}}}{2}}\right)=-640320^{3}$ ${\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2}}}$

$この恒等式は、 πを含む$ ラマヌジャンのいくつかの式に似ており、^[15]ラマヌジャン-佐藤級数の例である。

このアルゴリズムの時間計算量はであり、ここでnは必要な桁数である。^[16] $O\left(n(\log n)^{3}\right)$

最適化

世界記録の計算に使用された最適化手法はバイナリ分割と呼ばれます。^[17]

参照

参考文献

^ チュドノフスキー、デイビッド；チュドノフスキー、グレゴリー（1988）「ラマヌジャンによる近似と複素乗算」、ラマヌジャン再考：100周年記念会議議事録
^ ワーシ, カール; デンジャーフィールド, ヤン; ファーンドン, ジョン; グリフィス, ジョニー; ジャクソン, トム; パテル, ムクル; ポープ, スー; パーカー, マット (2019). 『数学の本：ビッグアイデアをシンプルに解説』ニューヨーク:ドーリング・キンダースリー・リミテッド. p. 65. ISBN 978-1-4654-8024-8。
^ バルア、ナヤンディープ・デカ;ブルース・C・ベルント;チャン、ヘン・フアト (2009-08-01)。「ラマヌジャンの 1/π のシリーズ: 調査」。アメリカ数学月刊誌。116 (7): 567–587。土井:10.4169/193009709X458555。
^ Yee, Alexander; Kondo, Shigeru (2011), 10 Trillion Digits of Pi: A Case Study of summing Hypergeometric Series to high precision on Multicore Systems , Technical Report, Computer Science Department, University of Illinois, hdl :2142/28348
^ アロン、ジェイコブ（2012年3月14日）「πの日に定数が衝突」、ニューサイエンティスト
^ 「円周率の22.4兆桁」www.numberworld.org .
^ 「Google CloudがPiの記録を更新」www.numberworld.org/。
^ 「円周率の記録がパーソナルコンピュータに戻る」www.numberworld.org/。
^ “Pi-Challenge - Weltrekordver such der FH Graubünden - FH Graubünden”. www.fhgr.ch 。2021年8月17日閲覧。
^ 「Google Cloud で円周率 100 兆桁を計算」. cloud.google.com . 2022 年 6 月 10 日閲覧。
^ Yee, Alexander J. (2024年3月14日). 「円周率の新記録、105兆桁に到達」. NumberWorld.org . 2024年3月16日閲覧。
^ Ranous, Jordan (2024年6月28日). 「StorageReview Labが円周率計算の世界記録を202兆桁以上で更新」. StorageReview.com . 2024年7月20日閲覧。
^ “ニュース (2024)”. www.numberworld.org . 2025年5月16日閲覧。
^ Linus Tech Tips (2025年5月16日). この世界記録の達成には何年も（そして100万ドルも）かかりました。2025年5月16日閲覧– YouTubeより。
^ ab Baruah、Nayandeep Deka;ブルース・C・ベルント; Chan、Heng Huat (2009)、「Ramanujan's series for 1/ $π$ : a Survey」、American Mathematical Monthly、116 (7): 567–587、doi :10.4169/193009709X458555、JSTOR 40391165、MR 2549375
^ 「y-cruncher - Formulas」. www.numberworld.org . 2018年2月25日閲覧。
^ ブレント、リチャード・P. ;ジマーマン、ポール(2010).現代コンピュータ算術. 第18巻.ケンブリッジ大学出版局. doi :10.1017/CBO9780511921698. ISBN 978-0-511-92169-8。

[1] チュドノフスキー、デイビッド；チュドノフスキー、グレゴリー（1988）「ラマヌジャンによる近似と複素乗算」、ラマヌジャン再考：100周年記念会議議事録

[2] ワーシ, カール; デンジャーフィールド, ヤン; ファーンドン, ジョン; グリフィス, ジョニー; ジャクソン, トム; パテル, ムクル; ポープ, スー; パーカー, マット (2019). 『数学の本：ビッグアイデアをシンプルに解説』ニューヨーク:ドーリング・キンダースリー・リミテッド. p. 65. ISBN 978-1-4654-8024-8。

[3] バルア、ナヤンディープ・デカ;ブルース・C・ベルント;チャン、ヘン・フアト (2009-08-01)。「ラマヌジャンの 1/π のシリーズ: 調査」。アメリカ数学月刊誌。116 (7): 567–587。土井:10.4169/193009709X458555。

[4] Yee, Alexander; Kondo, Shigeru (2011), 10 Trillion Digits of Pi: A Case Study of summing Hypergeometric Series to high precision on Multicore Systems , Technical Report, Computer Science Department, University of Illinois, hdl :2142/28348

[5] アロン、ジェイコブ（2012年3月14日）「πの日に定数が衝突」、ニューサイエンティスト

[6] 「円周率の22.4兆桁」www.numberworld.org .

[7] 「Google CloudがPiの記録を更新」www.numberworld.org/。

[8] 「円周率の記録がパーソナルコンピュータに戻る」www.numberworld.org/。

[9] “Pi-Challenge - Weltrekordver such der FH Graubünden - FH Graubünden”. www.fhgr.ch 。2021年8月17日閲覧。

[10] 「Google Cloud で円周率 100 兆桁を計算」. cloud.google.com . 2022 年 6 月 10 日閲覧。

[11] Yee, Alexander J. (2024年3月14日). 「円周率の新記録、105兆桁に到達」. NumberWorld.org . 2024年3月16日閲覧。

[12] Ranous, Jordan (2024年6月28日). 「StorageReview Labが円周率計算の世界記録を202兆桁以上で更新」. StorageReview.com . 2024年7月20日閲覧。

[13] “ニュース (2024)”. www.numberworld.org . 2025年5月16日閲覧。

[14] Linus Tech Tips (2025年5月16日). この世界記録の達成には何年も（そして100万ドルも）かかりました。2025年5月16日閲覧– YouTubeより。

[baruah-15] Baruah、Nayandeep Deka;ブルース・C・ベルント; Chan、Heng Huat (2009)、「Ramanujan's series for 1/ $π$ : a Survey」、American Mathematical Monthly、116 (7): 567–587、doi :10.4169/193009709X458555、JSTOR 40391165、MR 2549375

[16] 「y-cruncher - Formulas」. www.numberworld.org . 2018年2月25日閲覧。

[17] ブレント、リチャード・P. ;ジマーマン、ポール(2010).現代コンピュータ算術. 第18巻.ケンブリッジ大学出版局. doi :10.1017/CBO9780511921698. ISBN 978-0-511-92169-8。