Chudnovsky algorithm

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] and 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] and 50 trillion digits on January 29, 2020.[7]

The algorithm is based on the negated Heegner number ${\displaystyle d=-163}$, the j-function ${\displaystyle \scriptstyle j\left({\frac {1+{\sqrt {-163}}}{2}}\right)=-640320^{3}}$, and on the following rapidly convergent generalized hypergeometric series:[2]

${\displaystyle {\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}\left(640320\right)^{3k+3/2}}}}$

A detailed proof of this formula can be found here:[8]

For a high performance iterative implementation, this can be simplified to

${\displaystyle {\frac {(640320)^{3/2}}{12\pi }}={\frac {426880{\sqrt {10005}}}{\pi }}=\sum _{k=0}^{\infty }{\frac {(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}\left(-262537412640768000\right)^{k}}}}$

There are 3 big integer terms (the multinomial term M_k, the linear term L_k, and the exponential term X_k) that make up the series and π equals the constant C divided by the sum of the series, as below:

${\displaystyle \pi =C\left(\sum _{k=0}^{\infty }{\frac {M_{k}\cdot L_{k}}{X_{k}}}\right)^{-1}}$, where:

${\displaystyle C=426880{\sqrt {10005}}}$,

${\displaystyle M_{k}={\frac {(6k)!}{(3k)!(k!)^{3}}}}$,

${\displaystyle L_{k}=545140134k+13591409}$,

${\displaystyle X_{k}=(-262537412640768000)^{k}}$.

The terms M_k, L_k, and X_k satisfy the following recurrences and can be computed as such:

${\displaystyle {\begin{alignedat}{4}L_{k+1}&=L_{k}[phone]\,\,&&{\textrm {where}}\,\,L_{0}&&=13591409\\[4pt]X_{k+1}&=X_{k}\cdot (-262537412640768000)&&{\textrm {where}}\,\,X_{0}&&=1\\[4pt]M_{k+1}&=M_{k}\cdot \left({\frac {(12k+2)(12k+6)(12k+10)}{(k+1)^{3}}}\right)\,\,&&{\textrm {where}}\,\,M_{0}&&=1\\[4pt]\end{alignedat}}}$

The computation of M_k can be further optimized by introducing an additional term K_k as follows:

${\displaystyle {\begin{alignedat}{4}K_{k+1}&=K_{k}+12\,\,&&{\textrm {where}}\,\,K_{0}&&=6\\[4pt]M_{k+1}&=M_{k}\cdot \left({\frac {K_{k}^{3}-16K_{k}}{(k+1)^{3}}}\right)\,\,&&{\textrm {where}}\,\,M_{0}&&=1\\[12pt]\end{alignedat}}}$

Note that

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

${\displaystyle 640320^{3}=262537412640768000}$

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

${\displaystyle 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 ${\displaystyle O(n\log(n)^{3})}$.[9]

See also

• Borwein's algorithm
• Numerical approximations of π
• Ramanujan–Sato series

References

1. Chudnovsky, David; Chudnovsky, Gregory (1988), Approximation and complex multiplication according to ramanujan, Ramanujan revisited: proceedings of the centenary conference
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. Milla, Lorenz (2018), A detailed proof of the Chudnovsky formula with means of basic complex analysis, arXiv:1809.00533
9. "y-cruncher - Formulas". www.numberworld.org. Retrieved 2018-02-25.