Computing π to two billion digits

A C++ implementation of the Chudnovsky Algorithm - an algorithm used to efficiently compute pi. Using Binary Splitting architecture, GMP, and OpenMP, it has been able to compute nearly 5 million digit in just less than a second. So far, it've computed up to 2,000,000,000 digits (2 billion).

Benchmarks

All runs recorded on a 13th Gen i5-13500H laptop (16 threads), with WSL2.

Digits	Binary splitting	Peak memory
1,000,000	0.23708466 s	29.7 MiB
10,000,000	1.98447877 s	266.7 MiB
100,000,000	27.75211740 s	2.29 GiB
200,000,000	—	—

How it works

$$\frac{1}{\pi} \;=\; 12 \sum_{k=0}^{\infty} \frac{(-1)^k \, (6k)! \, (13591409 + 545140134\,k)} {(3k)! \, (k!)^3 \, 640320^{\,3k + 3/2}}$$

What makes it fast

Binary splitting. The series becomes a divide-and-conquer tree of exact integer products — a single division happens, at the very end.
GMP. Multiplications of million-digit integers run on FFT-based arithmetic instead of schoolbook multiplication.
OpenMP. Independent subtrees of the splitting tree are computed in parallel across all cores.

How to build

Needs a C++ compiler with OpenMP and the GMP library.

git clone https://github.com/IMBOBTHECODER/pi
cd pi
g++ -O3 -fopenmp main.cpp -o main -lgmp
./main

Limitations & future

Memory is the wall: computing digits is cheap, holding them is not — the two-billion-digit run leaned on 64 GiB of swap.

References

S. Ramanujan — Modular Equations and Approximations to π, Quarterly Journal of Mathematics (1914)
D. V. Chudnovsky & G. V. Chudnovsky — The Computation of Classical Constants, PNAS 86 (1989)
J. M. Borwein & P. B. Borwein — Pi and the AGM (1987)
B. Haible & T. Papanikolaou — Fast Multiprecision Evaluation of Series of Rational Numbers (1997)
The GNU MP manual