Calculate π using Chudnovsky algorithm and Pell equation
Arthur Vause
The Chudnovsky brothers have derived a formula
for π, which they and subsequently others,
most recently
Emma Haruka Iwao, have used in record breaking calculations of the digits of π,
. The Chudnovsky formula
can be written as:
$$ \frac{1}{\pi } = \frac{1}{426880\sqrt{10005}} \sum_{k=0}^{\infty}\frac{(-1)^k(6k)!(13591409 + 545140134k)}{(3k)!(k!)^3 640320^{3k} )} $$
Nick Craig-Wood's website
has a good description of how the Chudnovsky formula is used
to calculate π and the technique of binary splitting to speed up the implemetation.
My implementation is a Javascript port based on Nick Craig-Wood's Python code, with these modifications:
-
A potentially costly component of the Chudnovsky formula is calculating \( \sqrt{10005} \)
to the required number of decimal places.
An elegant and fast way of calculating this square root is to calculate solutions
of the Pell equation \( x^2 - 10005y^2 = 1 \) using the the base solution \( x=4001, y=40 \)
and the
recurrence relation for Pell solutions to construct a rational approximation \( \frac{x}{y} ≈ \sqrt{10005} \)
This makes the time taken to calculate \( \sqrt{10005} \) negligable compared to the summation of terms.
-
Common factors can be removed from the P,Q,R values obtained from the binary splitting algorithm
as the components are calculated at each level, producing a modest improvement in the execution time.
-
The last few hex digits of π are calculated and displayed, so that they can be verified using
the Bailey–Borwein–Plouffe (BBP) formula
The Javascript algorithm works in most browsers, including Firefox, Chrome and Microsoft Edge.
For the best performance, use chromium based 64 bit versions of Chrome or Edge.
For the fastest of the algorithms, binary splitting with factoring, timings using 64 bit Chrome browser on a 2.7GHz Athlon PC were
Digits
|
Time (seconds)
|
100,000
|
3
|
200,000
|
10
|
500,000
|
68
|
1,000,000
|
493
|
Above 100,000 digits, the Firefox implementation of Big Integers overflows, but Chrome and Edge work correctly.
Acknowledgements
The layout and style is based on a similar π calculator
by Don Cross, which uses the Machin-like formula
\( \pi = 48 arctan(\frac{1}{18}) + 32 arctan(\frac{1}{57}) − 20 arctan(\frac{1}{239}) \)