Chudnovsky algorithm
{{Short description|Fast method for calculating the digits of π}}
The Chudnovsky algorithm is a fast method for calculating the digits of {{pi}}, based on Ramanujan's {{pi}} formulae. Published by the Chudnovsky brothers in 1988,{{citation |last1=Chudnovsky |first1=David |title=Approximation and complex multiplication according to Ramanujan |year=1988 |series=Ramanujan revisited: proceedings of the centenary conference |last2=Chudnovsky |first2=Gregory}} it was used to calculate {{pi}} to a billion decimal places.{{Cite book |last=Warsi |first=Karl |title=The Math Book: Big Ideas Simply Explained |last2=Dangerfield |first2=Jan |last3=Farndon |first3=John |last4=Griffiths |first4=Johny |last5=Jackson |first5=Tom |last6=Patel |first6=Mukul |last7=Pope |first7=Sue |last8=Parker |first8=Matt |publisher=Dorling Kindersley Limited |year=2019 |isbn=978-1-4654-8024-8 |location=New York |pages=65}}
It was used in the world record calculations of 2.7 trillion digits of {{pi}} in December 2009,{{Cite journal |last=Baruah |first=Nayandeep Deka |last2=Berndt |first2=Bruce C. |last3=Chan |first3=Heng Huat |date=2009-08-01 |title=Ramanujan's Series for 1/π: A Survey |url=http://openurl.ingenta.com/content/xref?genre=article&issn=0002-9890&volume=116&issue=7&spage=567 |journal=American Mathematical Monthly |language=en |volume=116 |issue=7 |pages=567–587 |doi=10.4169/193009709X458555}} 10 trillion digits in October 2011,{{citation|title=10 Trillion Digits of Pi: A Case Study of summing Hypergeometric Series to high precision on Multicore Systems|last1=Yee|first1=Alexander|last2=Kondo|first2=Shigeru|series=Technical Report|year=2011|publisher=Computer Science Department, University of Illinois|hdl=2142/28348}}{{citation|title=Constants clash on pi day|first=Jacob|last=Aron|journal=New Scientist|date=March 14, 2012|url=https://www.newscientist.com/article/dn21589-constants-clash-on-pi-day.html}} 22.4 trillion digits in November 2016,{{Cite web |url=http://www.numberworld.org/y-cruncher/records/2016_11_11_pi.txt |title=22.4 Trillion Digits of Pi |website=www.numberworld.org}} 31.4 trillion digits in September 2018–January 2019,{{Cite web|url=http://www.numberworld.org/blogs/2019_3_14_pi_record/|title= Google Cloud Topples the Pi Record|website=www.numberworld.org/}} 50 trillion digits on January 29, 2020,{{Cite web|url=http://www.numberworld.org/y-cruncher/news/2020.html#2020_1_29|title=The Pi Record Returns to the Personal Computer|website=www.numberworld.org/}} 62.8 trillion digits on August 14, 2021,{{Cite web|title=Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden|url=https://www.fhgr.ch/fachgebiete/angewandte-zukunftstechnologien/davis-zentrum/pi-challenge/#c15513|access-date=2021-08-17|website=www.fhgr.ch}} 100 trillion digits on March 21, 2022,{{Cite web|title=Calculating 100 trillion digits of pi on Google Cloud|url=https://cloud.google.com/blog/products/compute/calculating-100-trillion-digits-of-pi-on-google-cloud|access-date=2022-06-10|website=cloud.google.com}} 105 trillion digits on March 14, 2024,{{Cite web |first=Alexander J. |last=Yee |date=2024-03-14 |title=Limping to a new Pi Record of 105 Trillion Digits |url=http://www.numberworld.org/y-cruncher/news/2024.html#2024_3_13 |website=NumberWorld.org |access-date=2024-03-16}} and 202 trillion digits on June 28, 2024.{{Cite web |last=Ranous |first=Jordan |date=2024-06-28 |title=StorageReview Lab Breaks Pi Calculation World Record with Over 202 Trillion Digits |url=https://www.storagereview.com/news/storagereview-lab-breaks-pi-calculation-world-record-with-over-202-trillion-digits |access-date=2024-07-20 |website=StorageReview.com |language=en-US}} Recently, the record was broken yet again on April 2nd 2025 with 300 trillion digits of pi.{{Cite web |title=News (2024) |url=https://www.numberworld.org/y-cruncher/news/2025.html#2025_5_16 |access-date=2025-05-16 |website=www.numberworld.org}}{{Cite AV media |url=https://www.youtube.com/watch?v=BD-AJwqzWsU |title=This World Record took YEARS (and a Million dollars..) |date=2025-05-16 |last=Linus Tech Tips |access-date=2025-05-16 |via=YouTube}} This was done through the usage of the algorithm on y-cruncher.
Algorithm
The algorithm is based on the negated Heegner number , the j-function , and on the following rapidly convergent generalized hypergeometric series:{{citation
| last1 = Baruah | first1 = Nayandeep Deka
| last2 = Berndt | first2 = Bruce C.
| last3 = Chan | first3 = Heng Huat
| doi = 10.4169/193009709X458555
| issue = 7
| journal = American Mathematical Monthly
| jstor = 40391165
| mr = 2549375
| pages = 567–587
| title = Ramanujan's series for 1/{{pi}}: a survey
| volume = 116
| year = 2009}}
12 \sum_{k=0}^{\infty}
{\frac{(-1)^k (6k)! (545140134k + 13591409)}{(3k)! (k!)^3(640320)^{3k + 3/2}}}
This identity is similar to some of Ramanujan's formulas involving {{pi}}, and is an example of a Ramanujan–Sato series.
The time complexity of the algorithm is .{{cite web|accessdate=2018-02-25|title=y-cruncher - Formulas|url=http://www.numberworld.org/y-cruncher/internals/formulas.html|website=www.numberworld.org}}
Optimizations
The optimization technique used for the world record computations is called binary splitting.
{{cite book
|last1=Brent
|first1=Richard P.
|author-link=Richard P. Brent
|last2=Zimmermann
|first2=Paul
|author2-link=Paul Zimmermann (mathematician)
|year=2010
|title=Modern Computer Arithmetic
|volume=18
|publisher=Cambridge University Press
|isbn=978-0-511-92169-8
|doi=10.1017/CBO9780511921698
}}
See also
{{Portal|Mathematics}}
References
{{reflist}}