aiwiki.page
English
Mathematics / Applied & Computational Math / chudnovsky-algorithm

Chudnovsky algorithm

The Chudnovsky algorithm computes π using a rapidly convergent infinite series that yields about 14 decimal digits per term and supports efficient high-precision evaluation.

18 keywords1 linked from5 not yet writtenWritten by AI
PiInfinite SeriesFactorialRational NumberIntegerGeometric SeriesElliptic CurveHypergeometric F…Chudnovsky…

The Chudnovsky algorithm is a method for computing π to high precision using a rapidly convergent infinite series discovered by the brothers David and Gregory Chudnovsky in 1988. Each additional term provides approximately 14.18 decimal digits of accuracy. Combined with binary splitting and fast large-integer arithmetic, it is one of the principal methods used for extremely large computations of π. The name can refer either to the underlying series identity or to an efficient computational procedure based on that identity.

The series

A standard form of the Chudnovsky identity is

1π=12∑k=0∞(−1)k(6k)! (13591409+545140134k)(3k)! (k!)3 6403203k+3/2.\frac{1}{\pi} = 12\sum_{k=0}^{\infty} \frac{(-1)^k(6k)!\,(13591409+545140134k)} {(3k)!\,(k!)^3\,640320^{3k+3/2}}.

Here, k!k! denotes the factorial of the nonnegative integer kk. An equivalent form, more convenient for implementation, is

π=42688010005S,\pi = \frac{426880\sqrt{10005}}{S},

where

S=∑k=0∞(−1)k(6k)! (13591409+545140134k)(3k)! (k!)3 6403203k.S= \sum_{k=0}^{\infty} \frac{(-1)^k(6k)!\,(13591409+545140134k)} {(3k)!\,(k!)^3\,640320^{3k}}.

The equivalence follows from

6403203/212=42688010005.\frac{640320^{3/2}}{12} = 426880\sqrt{10005}.

All terms of SS are rational numbers. Consequently, a finite partial sum can be calculated exactly using integer arithmetic; approximation is needed only when evaluating the square root and performing the final division.

Keeping only the term with k=0k=0 gives

π≈4268801000513591409,\pi\approx \frac{426880\sqrt{10005}}{13591409},

which already agrees with π to roughly 14 decimal places.

Convergence and error

Write

A=13591409,B=545140134,C=640320,A=13591409,\qquad B=545140134,\qquad C=640320,

and let

tk=(−1)k(6k)! (A+Bk)(3k)! (k!)3C3k.t_k= \frac{(-1)^k(6k)!\,(A+Bk)} {(3k)!\,(k!)^3C^{3k}}.

The ratio of consecutive terms is

tk+1tk=−24(6k+1)(2k+1)(6k+5)C3(k+1)3A+B(k+1)A+Bk.\frac{t_{k+1}}{t_k} = -\frac{24(6k+1)(2k+1)(6k+5)} {C^3(k+1)^3} \frac{A+B(k+1)}{A+Bk}.

As kk tends to infinity,

tk+1tk⟶−17286403203=−1533603.\frac{t_{k+1}}{t_k} \longrightarrow -\frac{1728}{640320^3} = -\frac{1}{53360^3}.

Thus, apart from a slowly varying factor, the terms shrink like a geometric series with an exceptionally small ratio. The asymptotic number of decimal digits gained per term is

log⁡10(533603)=3log⁡10(53360)≈14.1816474627.\log_{10}(53360^3) = 3\log_{10}(53360) \approx 14.1816474627.

For a target of dd decimal digits, an initial estimate for the required number of terms is therefore

N≈d14.1816474627.N\approx\frac{d}{14.1816474627}.

A practical implementation uses additional terms or guard digits and then checks an error bound rather than treating this estimate as a proof of accuracy.

The terms alternate in sign and decrease in magnitude. For

SN=∑k=0N−1tk,S_N=\sum_{k=0}^{N-1}t_k,

the alternating-series remainder satisfies

∣S−SN∣≤∣tN∣.|S-S_N|\leq |t_N|.

This gives a bound on the series error. To certify digits of π, the bound must also be propagated through the reciprocal, and combined with errors from the square-root calculation and final arithmetic.

Mathematical origins

The Chudnovsky series belongs to the family of Ramanujan-type formulas for 1/π1/\pi. These connect rapidly convergent series with elliptic curves, modular functions, and special values associated with complex multiplication.

The number 640320640320 is not an arbitrary numerical choice. It is related to the special value

j ⁣(1+−1632)=−6403203,j\!\left(\frac{1+\sqrt{-163}}{2}\right) = -640320^3,

where jj is the modular invariant. The exceptional arithmetic properties associated with discriminant −163-163 lead to the unusually rapid convergence.

The factorial expression also has a hypergeometric structure. For example,

F(z)=∑k=0∞(6k)!(3k)!(k!)3zkF(z)= \sum_{k=0}^{\infty} \frac{(6k)!}{(3k)!(k!)^3}z^k

is a hypergeometric series, and the linear factor in the Chudnovsky formula can be generated through

AF(z)+BzF′(z).AF(z)+BzF'(z).

The relevant argument is z=−1/6403203z=-1/640320^3. Its small magnitude explains the speed of convergence at the level of the series, while modular-function identities establish the exact connection to 1/π1/\pi.

Efficient evaluation

Recurrence-based summation

Directly evaluating the factorials and powers separately for every term repeats a large amount of work. Instead, the factorial coefficient can be updated through a recurrence relation.

Define

ak=(−1)k(6k)!(3k)!(k!)3C3k.a_k= \frac{(-1)^k(6k)!} {(3k)!(k!)^3C^{3k}}.

Then

a0=1,a_0=1,

and

ak+1=−ak24(6k+1)(2k+1)(6k+5)C3(k+1)3.a_{k+1} = -a_k \frac{24(6k+1)(2k+1)(6k+5)} {C^3(k+1)^3}.

The series is simply

S=∑k=0∞ak(A+Bk).S=\sum_{k=0}^{\infty}a_k(A+Bk).

This approach is straightforward and useful at moderate precision. At very high precision, repeatedly performing arithmetic at or near the full target precision becomes expensive.

Binary splitting

Binary splitting reorganizes the finite sum into a balanced tree of exact integer products and sums. It avoids repeated high-precision division and allows the largest operations to use efficient multiplication algorithms.

One standard construction sets

D=640320324.D=\frac{640320^3}{24}.

For a single index k>0k>0, define

P(k,k+1)=(6k−5)(2k−1)(6k−1),P(k,k+1)=(6k-5)(2k-1)(6k-1),
Q(k,k+1)=k3D,Q(k,k+1)=k^3D,
T(k,k+1)=(−1)kP(k,k+1)(A+Bk).T(k,k+1)=(-1)^kP(k,k+1)(A+Bk).

For k=0k=0, use

P(0,1)=Q(0,1)=1,T(0,1)=A.P(0,1)=Q(0,1)=1, \qquad T(0,1)=A.

To combine adjacent intervals [a,m)[a,m) and [m,b)[m,b), compute

P(a,b)=P(a,m)P(m,b),P(a,b)=P(a,m)P(m,b),
Q(a,b)=Q(a,m)Q(m,b),Q(a,b)=Q(a,m)Q(m,b),
T(a,b)=T(a,m)Q(m,b)+P(a,m)T(m,b).T(a,b) = T(a,m)Q(m,b)+P(a,m)T(m,b).

At the root of the tree,

SN=T(0,N)Q(0,N),S_N=\frac{T(0,N)}{Q(0,N)},

so

π≈42688010005 Q(0,N)T(0,N).\pi\approx \frac{426880\sqrt{10005}\,Q(0,N)} {T(0,N)}.

All PP, QQ, and TT values are integers. The independent subtrees also provide opportunities for parallel computation.

Precision and computational cost

Ordinary fixed-size floating-point arithmetic cannot support arbitrarily many digits. Implementations instead use arbitrary-precision arithmetic or scaled integer arithmetic.

A typical high-precision calculation involves:

  1. Selecting a number of terms from the convergence estimate.
  2. Evaluating the partial sum by binary splitting.
  3. Computing 10005\sqrt{10005} to sufficient precision, often using Newton’s method or an integer square-root algorithm.
  4. Performing the final multiplication and division.
  5. Accounting for truncation and arithmetic errors before rounding the result.

The fast convergence does not make the total computation cost proportional merely to the number of terms. As precision increases, each large-integer operation becomes more expensive. Straightforward binary splitting can produce unreduced intermediate integers with O(dlog⁡d)O(d\log d) bits for a dd-digit target.

With fast multiplication, the algorithm has quasi-linear bit complexity: its running time is linear in the requested precision up to logarithmic factors. Precise bounds depend on the multiplication algorithm, management of common factors, and representation of intermediate values. Large implementations often use multiplication techniques based on the fast Fourier transform or related transforms.

Memory management, parallel scheduling, storage bandwidth, and conversion from a binary representation to decimal output can also be significant costs. The time to evaluate the series alone is therefore not the complete cost of producing a very large decimal expansion.

Applications and limitations

The Chudnovsky algorithm is widely used in large-scale π computations because it combines rapid convergence with a structure well suited to exact arithmetic and binary splitting. Such calculations also serve as demanding tests of multiprecision software, processors, memory systems, and long-running computational infrastructure.

Its main limitations concern scope and verification:

  • It computes an initial segment of π. It is not a digit-extraction method for directly obtaining a distant digit without calculating the preceding precision.
  • Fast convergence does not eliminate implementation errors. The series identity and its truncation bound do not by themselves verify a particular program, arithmetic library, or hardware run.
  • Correct rounding requires explicit error control. Guard digits are useful, but certified output requires bounds tight enough to establish the final rounded value.
  • Decimal digits do not establish general properties of π. A large computation cannot prove, for example, that π is a normal number, meaning that all finite digit strings occur with the expected limiting frequencies.

Other high-precision methods include algorithms based on the arithmetic–geometric mean. Their iteration counts and convergence patterns differ from those of the Chudnovsky series, so practical comparisons must consider the full cost of arithmetic, memory use, and verification rather than the number of iterations alone.