imported>David Eppstein: /* Algorithm */ not a reliable source

2025-06-01T20:22:04Z

Algorithm: not a reliable source

New page

{{Short description|Fast method for calculating the digits of π}}
The '''Chudnovsky algorithm''' is a fast method for calculating the digits of [[pi|{{pi}}]], based on [[Ramanujan]]'s [[List of formulae involving π#Efficient infinite series|{{pi}} formulae]]. Published by the [[Chudnovsky brothers]] in 1988,<ref>{{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}}</ref> it was used to calculate {{pi}} to a billion decimal places.<ref>{{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}}</ref>

It was used in the [[Chronology of computation of π|world record]] calculations of 2.7 trillion digits of {{pi}} in December 2009,<ref>{{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}}</ref> 10 trillion digits in October 2011,<ref>{{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}}</ref><ref>{{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}}</ref> 22.4 trillion digits in November 2016,<ref>{{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}}</ref> 31.4 trillion digits in September 2018–January 2019,<ref>{{Cite web|url=http://www.numberworld.org/blogs/2019_3_14_pi_record/|title= Google Cloud Topples the Pi Record|website=www.numberworld.org/}}</ref> 50 trillion digits on January 29, 2020,<ref>{{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/}}</ref> 62.8 trillion digits on August 14, 2021,<ref>{{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}}</ref> 100 trillion digits on March 21, 2022,<ref>{{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}}</ref> 105 trillion digits on March 14, 2024,<ref>{{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}}</ref> and 202 trillion digits on June 28, 2024.<ref>{{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}}</ref> Recently, the record was broken yet again on April 2nd 2025 with 300 trillion digits of pi.<ref>{{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}}</ref><ref>{{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}}</ref> This was done through the usage of the algorithm on [[y-cruncher]].

==Algorithm==
The algorithm is based on the negated [[Heegner number]] <math> d = -163 </math>, the [[j-invariant|''j''-function]] <math> j \left(\tfrac{1 + i\sqrt{-163}}{2}\right) = -640320^3</math>, and on the following rapidly convergent [[generalized hypergeometric series]]:<ref name="baruah">{{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}}</ref><math display="block"> \frac{1}{\pi} =
12 \sum_{k=0}^{\infty}
{\frac{(-1)^k (6k)! (545140134k + 13591409)}{(3k)! (k!)^3(640320)^{3k + 3/2}}}</math>

This identity is similar to some of [[Ramanujan]]'s formulas involving {{pi}},<ref name="baruah"/> and is an example of a [[Ramanujan–Sato series]].

The [[time complexity]] of the algorithm is <math>O\left(n (\log n)^3\right)</math>.<ref>{{cite web|accessdate=2018-02-25|title=y-cruncher - Formulas|url=http://www.numberworld.org/y-cruncher/internals/formulas.html|website=www.numberworld.org}}</ref>

== Optimizations ==
The optimization technique used for the world record computations is called [[binary splitting]].<ref>
{{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
}}</ref>

==See also==
{{Portal|Mathematics}}
*[[Bailey–Borwein–Plouffe formula]]
*[[Borwein's algorithm]]
*[[Approximations of π]]

==References==
{{reflist}}

[[Category:Pi algorithms]]

Chudnovsky algorithm - Revision history

imported>David Eppstein: /* Algorithm */ not a reliable source