The Chudnovsky algorithm is a fast method for calculating the digits of π. It was published by the Chudnovsky brothers in 1989, and was used in the world record calculations of 2.7 trillion digits of π in December 2009, 5 trillion digits in August 2010, 10 trillion digits in October 2011, 12.1 trillion digits in December 2013 and 22.4 trillion digits of π in November 2016.
For a high performance iterative implementation, this can be simplified to
There are 3 big integer terms (the multinomial term Mk, the linear term Lk, and the exponential term Xk) that make up the series and π equals the constant C divided by the sum of the series, as below:
- , where:
The terms Mk, Lk, and Xk satisfy the following recurrences and can be computed as such:
The computation of Mk can be further optimized by introducing an additional term Kk as follows:
Example: Python Implementation
π can be computed to any precision using the above algorithm in any environment which supports arbitrary-precision arithmetic. As an example, here is a Python implementation:
from decimal import Decimal as Dec, getcontext as gc def PI(maxK=70, prec=1008, disp=1007): # parameter defaults chosen to gain 1000+ digits within a few seconds gc().prec = prec K, M, L, X, S = 6, 1, 13591409, 1, 13591409 for k in range(1, maxK+1): M = (K**3 - 16*K) * M // k**3 L += 545140134 X *= -262537412640768000 S += Dec(M * L) / X K += 12 pi = 426880 * Dec(10005).sqrt() / S pi = Dec(str(pi)[:disp]) # drop few digits of precision for accuracy print("PI(maxK=%d iterations, gc().prec=%d, disp=%d digits) =\n%s" % (maxK, prec, disp, pi)) return pi Pi = PI() print("\nFor greater precision and more digits (takes a few extra seconds) - Try") print("Pi = PI(317,4501,4500)") print("Pi = PI(353,5022,5020)")
- Chudnovsky, David V.; Chudnovsky, Gregory V. (1989), "The Computation of Classical Constants", Proceedings of the National Academy of Sciences of the United States of America, 86 (21): 8178–8182, doi:10.1073/pnas.86.21.8178, ISSN 0027-8424, JSTOR 34831, PMC 298242, PMID 16594075
- 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
- Geeks slice pi to 5 trillion decimal places, Australian Broadcasting Corporation, August 6, 2010
- 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
- Aron, Jacob (March 14, 2012), "Constants clash on pi day", New Scientist
- Yee, Alexander J.; Kondo, Shigeru (28 December 2013). "12.1 Trillion Digits of Pi". www.numberworld.org.
- "22.4 Trillion Digits of Pi". www.numberworld.org.
- "y-cruncher - Formulas". www.numberworld.org. Retrieved 2018-02-25.
|This number article is a stub. You can help Wikipedia by expanding it.|