Jump to content

Chudnovsky algorithm

From Wikipedia, the free encyclopedia

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] and 105 trillion digits on March 14, 2024.[11]

Algorithm[edit]

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

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


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

The time complexity of the algorithm is .[14]

Optimizations[edit]

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

Binary splitting[edit]

A factor of can be taken out of the sum and simplified to


Let , and substitute that into the sum.


can be simplified to , so

from the original definition of , so

This definition of isn't defined for , so compute the first term of the sum and use the new definition of

Let and , so

Let and

can never be computed, so instead compute and as approaches , the approximation will get better.

From the original definition of ,

Recursively computing the functions[edit]

Consider a value such that

Base case for recursion[edit]

Consider

Python code[edit]

import decimal


def binary_split(a, b):
    if b == a + 1:
        Pab = -(6*a - 5)*(2*a - 1)*(6*a - 1)
        Qab = 10939058860032000 * a**3
        Rab = Pab * (545140134*a + 13591409)
    else:
        m = (a + b) // 2
        Pam, Qam, Ram = binary_split(a, m)
        Pmb, Qmb, Rmb = binary_split(m, b)
        
        Pab = Pam * Pmb
        Qab = Qam * Qmb
        Rab = Qmb * Ram + Pam * Rmb
    return Pab, Qab, Rab


def chudnovsky(n):
    """Chudnovsky algorithm."""
    P1n, Q1n, R1n = binary_split(1, n)
    return (426880 * decimal.Decimal(10005).sqrt() * Q1n) / (13591409*Q1n + R1n)


print(f"1 = {chudnovsky(2)}")  # 3.141592653589793238462643384

decimal.getcontext().prec = 100 # number of digits of decimal precision
for n in range(2,10):
    print(f"{n} = {chudnovsky(n)}")  # 3.14159265358979323846264338...

Notes[edit]

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. ^ 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. p. 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". American Mathematical Monthly. 116 (7): 567–587. doi:10.4169/193009709X458555.
  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, hdl:2142/28348
  5. ^ Aron, Jacob (March 14, 2012), "Constants clash on pi day", New Scientist
  6. ^ "22.4 Trillion Digits of Pi". www.numberworld.org.
  7. ^ "Google Cloud Topples the Pi Record". www.numberworld.org/.
  8. ^ "The Pi Record Returns to the Personal Computer". www.numberworld.org/.
  9. ^ "Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden". www.fhgr.ch. Retrieved 2021-08-17.
  10. ^ "Calculating 100 trillion digits of pi on Google Cloud". cloud.google.com. Retrieved 2022-06-10.
  11. ^ Yee, Alexander J. (2024-03-14). "Limping to a new Pi Record of 105 Trillion Digits". NumberWorld.org. Retrieved 2024-03-16.
  12. ^ Jump up to: a b 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
  13. ^ Milla, Lorenz (2018), A detailed proof of the Chudnovsky formula with means of basic complex analysis, arXiv:1809.00533
  14. ^ "y-cruncher - Formulas". www.numberworld.org. Retrieved 2018-02-25.
  15. ^ Rayton, Joshua (Sep 2023), How is π calculated to trillions of digits?, YouTube