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.

 Decimal digits: Chudnovsky and Pell Chudnovsky Binary Splitting and Pell Chudnovsky Binary Splitting with factoring and Pell 50 100 1000 5000 10000 20000 50000 100000 200000 (chrome or edge) 500000 (chrome or edge) 1000000 (chrome or edge)

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})$$