Chudnovsky algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

The Chudnovsky algorithm is a fast method for calculating the digits of π. 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 of π in November 2016[5], and 31.4 trillion digits in September 2018–January 2019.[6]

The algorithm is based on the negated Heegner number , the j-function , and on the following rapidly convergent generalized hypergeometric series:[2]

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

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:

Note that

and

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 .[8]

Example: Python Implementation[edit]

[original research?]

π 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={} iterations, gc().prec={}, disp={} digits) =\n{}".format(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)")

See also[edit]

References[edit]

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