---
tag: Z5G5JPT022
kind: definition
name: Chudnovsky algorithm
msc: [11Y60, 65D20]
defines: JKCKXDT5B5
uses: [0C1VYVNV2N, 0XWG0JGDFW, 0AF7X08PCR]
sources:
  - url: https://en.wikipedia.org/wiki/Chudnovsky_algorithm
---

## Definition

The *Chudnovsky algorithm* computes approximations of [[pi|0C1VYVNV2N]] 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|0XWG0JGDFW]].
To obtain $\pi$ to $D$ decimal digits, it adds the first $N$ terms of this [[series|0AF7X08PCR]] 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|FEC2XH822R]] value $j\big(\frac{1 + \sqrt{-163}}{2}\big) = -640320^3$.