Chudnovsky algorithm: Difference between revisions

From HandWiki
fix
 
simplify
 
Line 1: Line 1:
{{Short description|Fast method for calculating the digits of π}}
{{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>
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 [[Biography:Chudnovsky brothers|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|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 November 23rd, 2025 with 314 trillion digits of pi.<ref>{{Cite web |title=StorageReview Sets New Pi Record: 314 Trillion Digits on a Dell PowerEdge R7725 |url=https://www.storagereview.com/review/storagereview-sets-new-pi-record-314-trillion-digits-on-a-dell-poweredge-r7725 |access-date=2026-01-02 |website=StorageReview.com |language=en-US}}</ref><ref>{{Cite web |last=OBrien |first=Kevin |date=2025-12-25 |title=Pi calculation world record shattered at 314 trillion digits with a four-month run on a single server — StorageReview retakes the crown, thanks to storage bandwidth |url=https://www.tomshardware.com/pc-components/storage/pi-calculating-record-shattered-at-314-trillion-digits-with-a-four-month-run-on-a-single-server-storagereview-retakes-the-crown-thanks-to-storage-bandwidth |access-date=2026-01-02 |website=Tom's Hardware |language=en}}</ref> This was done through the usage of the algorithm on [[Software:Y-cruncher|y-cruncher]].
It was used in the [[Chronology of computation of π|world record]] calculations of 2.7 [[Trillion|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 November 23, 2025 with 314 trillion digits of pi.<ref>{{Cite web |title=StorageReview Sets New Pi Record: 314 Trillion Digits on a Dell PowerEdge R7725 |url=https://www.storagereview.com/review/storagereview-sets-new-pi-record-314-trillion-digits-on-a-dell-poweredge-r7725 |access-date=2026-01-02 |website=StorageReview.com |language=en-US}}</ref><ref>{{Cite web |last=OBrien |first=Kevin |date=2025-12-25 |title=Pi calculation world record shattered at 314 trillion digits with a four-month run on a single server — StorageReview retakes the crown, thanks to storage bandwidth |url=https://www.tomshardware.com/pc-components/storage/pi-calculating-record-shattered-at-314-trillion-digits-with-a-four-month-run-on-a-single-server-storagereview-retakes-the-crown-thanks-to-storage-bandwidth |access-date=2026-01-02 |website=Tom's Hardware |language=en}}</ref> This was done through the usage of the [[Algorithm|algorithm]] on [[Software:Y-cruncher|y-cruncher]].


==Algorithm==
==Algorithm==
Line 18: Line 18:
  | volume = 116
  | volume = 116
  | year = 2009}}</ref><math display="block"> \frac{1}{\pi} =  
  | year = 2009}}</ref><math display="block"> \frac{1}{\pi} =  
12 \sum_{k=0}^{\infty}
\frac{\sqrt{10005}}{4270934400} \sum_{k=0}^{\infty}
{\frac{(-1)^k (6k)! (545140134k + 13591409)}{(3k)! (k!)^3(640320)^{3k + 3/2}}}</math>
{\frac{(-1)^k (6k)! (545140134k + 13591409)}{(3k)! (k!)^3(640320)^{3k}}}</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]].
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|time complexity]] of the algorithm is <math>O\left(n (\log n)^3\right)</math>, where n is the number of digits desired.<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>
The [[Time complexity|time complexity]] of the algorithm is <math>O\left(n (\log n)^3\right)</math>, where n is the number of digits desired.<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> Each term produces about 14 correct decimal digits of {{pi}}.<ref>The limiting ratio between two consecutive terms, using [[Stirling's approximation]], is <math>\frac{640320^3}{1728}</math>; and <math>\log_{10}(\frac{640320^3}{1728}) \approx 14.18</math>.</ref>


== Optimizations ==
== Optimizations ==

Latest revision as of 02:04, 16 April 2026

Short description: Fast method for calculating the digits of π

The Chudnovsky algorithm is a fast method for calculating the digits of π, based on Ramanujan's π formulae. Published by the Chudnovsky brothers in 1988,[1] it was used to calculate π to a billion decimal places.[2]

It was used in the world record calculations of 2.7 trillion digits of π in December 2009,[3] 10 trillion digits in October 2011,[4][5] 22.4 trillion digits in November 2016,[6] 31.4 trillion digits in September 2018–January 2019,[7] 50 trillion digits on January 29, 2020,[8] 62.8 trillion digits on August 14, 2021,[9] 100 trillion digits on March 21, 2022,[10] 105 trillion digits on March 14, 2024,[11] and 202 trillion digits on June 28, 2024.[12] Recently, the record was broken yet again on November 23, 2025 with 314 trillion digits of pi.[13][14] This was done through the usage of the algorithm on y-cruncher.

Algorithm

The algorithm is based on the negated Heegner number d=−163, the j-function j(1+i−1632)=−6403203, and on the following rapidly convergent generalized hypergeometric series:[15]1π=100054270934400∑k=0∞(−1)k(6k)!(545140134k+13591409)(3k)!(k!)3(640320)3k

This identity is similar to some of Ramanujan's formulas involving π,[15] and is an example of a Ramanujan–Sato series.

The time complexity of the algorithm is O(n(log⁡n)3), where n is the number of digits desired.[16] Each term produces about 14 correct decimal digits of π.[17]

Optimizations

The optimization technique used for the world record computations is called binary splitting.[18]

See also

References

  1. ↑ Chudnovsky, David; Chudnovsky, Gregory (1988), Approximation and complex multiplication according to Ramanujan, Ramanujan revisited: proceedings of the centenary conference 
  2. ↑ Warsi, Karl; Dangerfield, Jan; Farndon, John; Griffiths, Johny; Jackson, Tom; Patel, Mukul; Pope, Sue; Parker, Matt (2019). The Math Book: Big Ideas Simply Explained. New York: Dorling Kindersley Limited. pp. 65. ISBN 978-1-4654-8024-8. 
  3. ↑ Baruah, Nayandeep Deka; Berndt, Bruce C.; Chan, Heng Huat (2009-08-01). "Ramanujan's Series for 1/π: A Survey" (in en). American Mathematical Monthly 116 (7): 567–587. doi:10.4169/193009709X458555. http://openurl.ingenta.com/content/xref?genre=article&issn=0002-9890&volume=116&issue=7&spage=567. 
  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 
  5. ↑ Aron, Jacob (March 14, 2012), "Constants clash on pi day", New Scientist, https://www.newscientist.com/article/dn21589-constants-clash-on-pi-day.html 
  6. ↑ "22.4 Trillion Digits of Pi". http://www.numberworld.org/y-cruncher/records/2016_11_11_pi.txt. 
  7. ↑ "Google Cloud Topples the Pi Record". http://www.numberworld.org/blogs/2019_3_14_pi_record/. 
  8. ↑ "The Pi Record Returns to the Personal Computer". http://www.numberworld.org/y-cruncher/news/2020.html#2020_1_29. 
  9. ↑ "Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden". https://www.fhgr.ch/fachgebiete/angewandte-zukunftstechnologien/davis-zentrum/pi-challenge/#c15513. 
  10. ↑ "Calculating 100 trillion digits of pi on Google Cloud". https://cloud.google.com/blog/products/compute/calculating-100-trillion-digits-of-pi-on-google-cloud. 
  11. ↑ Yee, Alexander J. (2024-03-14). "Limping to a new Pi Record of 105 Trillion Digits". http://www.numberworld.org/y-cruncher/news/2024.html#2024_3_13. 
  12. ↑ Ranous, Jordan (2024-06-28). "StorageReview Lab Breaks Pi Calculation World Record with Over 202 Trillion Digits" (in en-US). https://www.storagereview.com/news/storagereview-lab-breaks-pi-calculation-world-record-with-over-202-trillion-digits. 
  13. ↑ "StorageReview Sets New Pi Record: 314 Trillion Digits on a Dell PowerEdge R7725" (in en-US). https://www.storagereview.com/review/storagereview-sets-new-pi-record-314-trillion-digits-on-a-dell-poweredge-r7725. 
  14. ↑ OBrien, Kevin (2025-12-25). "Pi calculation world record shattered at 314 trillion digits with a four-month run on a single server — StorageReview retakes the crown, thanks to storage bandwidth" (in en). https://www.tomshardware.com/pc-components/storage/pi-calculating-record-shattered-at-314-trillion-digits-with-a-four-month-run-on-a-single-server-storagereview-retakes-the-crown-thanks-to-storage-bandwidth. 
  15. ↑ 15.0 15.1 Baruah, Nayandeep Deka; Berndt, Bruce C.; Chan, Heng Huat (2009), "Ramanujan's series for 1/π: a survey", American Mathematical Monthly 116 (7): 567–587, doi:10.4169/193009709X458555 
  16. ↑ "y-cruncher - Formulas". http://www.numberworld.org/y-cruncher/internals/formulas.html. Retrieved 2018-02-25. 
  17. ↑ The limiting ratio between two consecutive terms, using Stirling's approximation, is 64032031728; and log10(64032031728)≈14.18.
  18. ↑ Brent, Richard P.; Zimmermann, Paul (2010). Modern Computer Arithmetic. 18. Cambridge University Press. doi:10.1017/CBO9780511921698. ISBN 978-0-511-92169-8. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Chudnovsky_algorithm&oldid=4299657"