User:Joshua Rayton/sandbox: Difference between revisions

Content deleted Content added

Inline

Revision as of 21:28, 18 October 2023

This is the user sandbox of Joshua Rayton. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

The Chudnovsky algorithm is a fast method for calculating the digits of $π$ , based on Ramanujan's $π$ formulae. It was published by the Chudnovsky brothers in 1988.^[1]

It was used in the world record calculations of 2.7 trillion digits of $π$ in December 2009,^[2] 10 trillion digits in October 2011,^[3]^[4] 22.4 trillion digits in November 2016,^[5] 31.4 trillion digits in September 2018–January 2019,^[6] 50 trillion digits on January 29, 2020,^[7] 62.8 trillion digits on August 14, 2021,^[8] and 100 trillion digits on March 21, 2022.^[9]

Algorithm

The algorithm is based on the negated Heegner number $d=-163$ , the j-function $j\left({\tfrac {1+i{\sqrt {163}}}{2}}\right)=-640320^{3}$ , and on the following rapidly convergent generalized hypergeometric series:^[2] ${\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2}}}$ A detailed proof of this formula can be found here: ^[10]

Note that

e^{\pi {\sqrt {163}}}\approx 640320^{3}+743.99999999999925\dots

and

640320^{3}=262537412640768000

545140134=163\cdot 127\cdot 19\cdot 11\cdot 7\cdot 3^{2}\cdot 2

13591409=13\cdot 1045493

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

The time complexity of the algorithm is $O\left(n(\log n)^{3}\right)$ .^[11]

Optimizations

The optimization technique used for the world record computations is called binary splitting. Here is a video that explains the binary splitting of the algorithm: ^[12]

Binary splitting

A factor of ${\textstyle 1/{640320^{3/2}}}$ can be taken out of the sum and simplified to ${\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k}}}$

Let $f(n)={\frac {(-1)^{n}(6n)!}{(3n)!(n!)^{3}(640320)^{3n}}}$ , and substitute that into the sum. ${\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{f(k)\cdot (545140134k+13591409)}$ ${\frac {f(n)}{f(n-1)}}$

References

^ Chudnovsky, David; Chudnovsky, Gregory (1988), Approximation and complex multiplication according to Ramanujan, Ramanujan revisited: proceedings of the centenary conference
^ ^a ^b ^c 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, JSTOR 40391165, MR 2549375
^ 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
^ Aron, Jacob (March 14, 2012), "Constants clash on pi day", New Scientist
^ "22.4 Trillion Digits of Pi". www.numberworld.org.
^ "Google Cloud Topples the Pi Record". www.numberworld.org/.
^ "The Pi Record Returns to the Personal Computer". www.numberworld.org/.
^ "Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden". www.fhgr.ch. Retrieved 2021-08-17.
^ "Calculating 100 trillion digits of pi on Google Cloud". cloud.google.com. Retrieved 2022-06-10.
^ Milla, Lorenz (2018), A detailed proof of the Chudnovsky formula with means of basic complex analysis, arXiv:1809.00533
^ "y-cruncher - Formulas". www.numberworld.org. Retrieved 2018-02-25.
^ Rayton, Joshua, How is π calculated to trillions of digits?{{citation}}: CS1 maint: url-status (link)

[1] Chudnovsky, David; Chudnovsky, Gregory (1988), Approximation and complex multiplication according to Ramanujan, Ramanujan revisited: proceedings of the centenary conference

[baruah-2] 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, JSTOR 40391165, MR 2549375

[3] 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

[4] Aron, Jacob (March 14, 2012), "Constants clash on pi day", New Scientist

[5] "22.4 Trillion Digits of Pi". www.numberworld.org.

[6] "Google Cloud Topples the Pi Record". www.numberworld.org/.

[7] "The Pi Record Returns to the Personal Computer". www.numberworld.org/.

[8] "Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden". www.fhgr.ch. Retrieved 2021-08-17.

[9] "Calculating 100 trillion digits of pi on Google Cloud". cloud.google.com. Retrieved 2022-06-10.

[10] Milla, Lorenz (2018), A detailed proof of the Chudnovsky formula with means of basic complex analysis, arXiv:1809.00533

[11] "y-cruncher - Formulas". www.numberworld.org. Retrieved 2018-02-25.

[12] Rayton, Joshua, How is π calculated to trillions of digits?{{citation}}: CS1 maint: url-status (link)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 20: / Line 20: @@
 ==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"/>
+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"/><math display="block"> \frac{1}{\pi} =
-:<math> \frac{1}{\pi} =
 \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 + 3/2}}}</math>A detailed proof of this formula can be found here: <ref>{{citation|title=A detailed proof of the Chudnovsky formula with means of basic complex analysis|last1=Milla|first1=Lorenz|arxiv=1809.00533|year=2018}}</ref>
-A detailed proof of this formula can be found here: <ref>{{citation|title=A detailed proof of the Chudnovsky formula with means of basic complex analysis|last1=Milla|first1=Lorenz|arxiv=1809.00533|year=2018}}</ref>
 Note that
@@ Line 45: / Line 41: @@
 A factor of <math display="inline">1/{640320^{3/2}}</math> can be taken out of the sum and simplified to <math display="block">\frac{1}{\pi} = \frac{1}{426880 \sqrt{10005}} \sum_{k=0}^{\infty}{\frac{(-1)^k (6k)! (545140134k + 13591409)}{(3k)! (k!)^3 (640320)^{3k}}}</math>
-Let <math>f(n) = \frac{(-1)^n (6n)!}{(3n)! (n!)^3 (640320)^{3n}}</math>, and substitute that into the sum.<math display="block">\frac{1}{\pi} = \frac{1}{426880 \sqrt{10005}} \sum_{k=0}^{\infty}{f(k) \cdot (545140134k + 13591409)}</math>
+Let <math>f(n) = \frac{(-1)^n (6n)!}{(3n)! (n!)^3 (640320)^{3n}}</math>, and substitute that into the sum.<math display="block">\frac{1}{\pi} = \frac{1}{426880 \sqrt{10005}} \sum_{k=0}^{\infty}{f(k) \cdot (545140134k + 13591409)}</math><math> \frac{f(n)}{f(n-1)}</math>
 ==See also==