Finding 10000 decimals of pi

Up a level : Algebra and Arithmetic
Previous page : Finding 10000 decimals of e
Next page : RSA cryptosystem

Calculating Pi

In this page pi is approximately calculated with various algorithms. All but the last one can be found on the Wikipedia page of pi: https://en.wikipedia.org/wiki/Pi. You can read more of them there.

Link to the page

Gregory–Leibniz series

This is

$\pi = \frac{4}{1} - \frac{4}{3} + \frac{4}{5} - \frac{4}{7} + ...$

The calculations are done using JavaScripts native bigInt value type, but interpreted as fixed int numbers, where 1 is replaced by a value 10 to the power of some number. In this way all the calculations can be done using integers only. When printing out the result the decimal point is added. This trick (sometimes on steroids is used in all the algorithms.)

Every 22474th step is shown. The reason this rather peculiar, and rather arbitrary value is shown is that an ordinary laptop can handle at least this many steps in one (common) frame, i.e. 1/60 seconds, and because 22474 will make all the digits in the shown number of steps varying, giving the impression that you can see all the steps

Nilakantha’s algorithm

Here every 14474th step is shown of the same reason as for the previous algorithm.

John Machin’s formula

Here we have two variants. One where every 6^th step is shown so that one can see the progress, and one where every 1193^rd step is shown. The reason behind those particular numbers is that both are factors of the numbers of steps to get 10 000 correct decimals + they are conveniently large numbers to se the progress or make it as fast as possible.

BBP digit extraction algorithm

Yet again there are two variants, one where one can see the progress, showing every 17^th step, and one where every 498^th step is shown.

Mauritz’s algorithm

Then finally an algorithm of my own. Here I use the fact that cos x has a zero at x= pi/2. I will start with a guess close to this (I will use the value of pi provided by JavaScript, i.e. a value with about 16 significant figures) then since the slope of cos(x) is close to -1 close to that zero we can follow that line to the x-axis to get a better guess.

In the figure c=cos(x) for a particular value of x, and the red line represents the cos(x)-curve. Following the line with slope −1 from the point
(x_n, cos(x_n)) = (x_n, c) will get us to a better guess. This will this be at the point x_n+1= x_n+c.

By horizontally mirror this around the zero we can see that the numbers will approach 0 exactly as fast as they would approach 0 for sin(x).

We have that

$\sin (x) \approx x - \frac{{{x^3}}}{{3!}}$

So the new term will be approximately in the order of x³. We should thus get about three times more accurate digits for each turn. Indeed, after one turn we will have 49 accurate figures, and 16 times 3 is 48.

What I did here was working with larger and larger number of digits, starting with 50 and then triple it every turn, so 50, 150, 450, 1350, 4050, and finally 12150. I will round the later to 10005 though, and then run one extra turn of the algorithm to ensure that at least 10000 digits are correct.

I had to write a cosine function for bigInt, using a Taylor series.

All in all, the algorithm is reasonable fast, but does not scale well when I tried with 100 000 digits. To make this work well one must come up with a faster way to calculate cos.

Up a level : Algebra and Arithmetic
Previous page : Finding 10000 decimals of e
Next page : RSA cryptosystem

Last modified: Apr 12, 2023 @ 20:37