Chudnovsky algorithm

Builds on pi Factorial Convergent series

Definition

The Chudnovsky algorithm computes approximations of pi from the Chudnovsky formula $\frac{1}{\pi} = 12\sum_{k=0}^{\infty} \frac{(-1)^k\,(6k)!\,(13591409 + 545140134\,k)}{(3k)!\,(k!)^3\,640320^{3k + 3/2}},$ where $n!$ is the factorial. To obtain $\pi$ to $D$ decimal digits, it adds the first $N$ terms of this series and inverts the sum. Here $N$ is slightly more than $D/14$ . The partial sum is evaluated by binary splitting. The rational numbers that form the terms are combined pairwise in a balanced tree, so the work is done with large-integer products.

Remarks

The ratio of successive terms tends to $-12^3/640320^3 \approx -6.6 \times 10^{-15}$ , since $(6k)!/((3k)!(k!)^3)$ grows like a constant times $1728^k k^{-3/2}$ by Stirling's formula; this gives about $14.18$ digits per term. Example: the $k = 0$ term gives $\pi \approx 640320^{3/2}/(12\cdot 13591409) = 3.14159265358973\ldots$ , correct to $13$ decimal places. Non-example: summing the Leibniz series $\pi/4 = 1 - \frac13 + \frac15 - \cdots$ is not this algorithm and is far slower: its error after $N$ terms is of order $1/N$ . The number $640320^3 = 262537412640768000$ is close to $e^{\pi\sqrt{163}} - 744$ , which reflects the j-invariant value $j\big(\frac{1 + \sqrt{-163}}{2}\big) = -640320^3$ .

Reading path

To understand this page from the ground up, read these 59 pages in order. The foundations come first.

Convergent series concept
Factorial concept
Limit point of a set definition
Local maximum definition
Sequence definition
Limit of a function definition
Local minimum definition
Real sequence definition
Subsequence definition
Continuity at a point definition
Derivative definition
Bounded sequence definition
Cauchy sequence definition
Geometric sequence definition
Limit of a sequence definition
Monotone sequence definition
Series definition
Continuous function definition
Fermat's theorem on stationary points statement
Limit superior definition
Cauchy sequences are bounded statement
Sum of a finite geometric series statement
Monotone convergence theorem for sequences statement
Every sequence has a monotone subsequence statement
Convergent sequence definition
Pointwise convergence definition
Squeeze theorem statement
Partial sum definition
Power series definition
Intermediate value theorem statement
Bolzano–Weierstrass theorem statement
The sequence r^n tends to zero for |r| < 1 example
Radius of convergence definition
Convergent series definition
Uniform convergence definition
Sine and cosine definition
Boundedness theorem statement
Cauchy criterion for sequences statement
Uniform convergence on a set definition
Absolute convergence definition
A series of nonnegative terms converges iff its partial sums are bounded statement
Series of functions definition
Sum of a series definition
Extreme value theorem statement
Uniformly Cauchy sequence of functions definition
Comparison test statement
Geometric series example
Rolle's theorem statement
Root test statement
Weierstrass M-test statement
Mean value theorem statement
Cauchy–Hadamard theorem statement
Power series converge uniformly on smaller discs inside the radius of convergence statement
Uniform convergence of derivatives allows term-by-term differentiation statement
Term-by-term differentiation statement
Power series are differentiable inside the radius of convergence statement
Derivative of cosine statement
pi object
Chudnovsky algorithm definition

Tag	`Z5G5JPT022`
URI	`m2://Z5G5JPT022`
Kind	definition
Writing	W0 stub
MSC	11Y60, 65D20
Defines	Chudnovsky algorithm
Uses	pi, Factorial, Convergent series

Chudnovsky algorithm

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here