What is the fastest way to $\pi$?

Question

There are many known sequences convergent to $\pi$ with different convergence accelerations. For example both of the following sequences are convergent to $\pi$ when $n$ goes to $\infty$:

(a) $a_n=2^{n+1}\times\sqrt{2-\underbrace{\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{...+\sqrt{2}}}}}}}$ which the under brace part repeats $n$ times. More clear:

$a_0=2\sqrt{2}$

$a_1=4\sqrt{2-\sqrt{2}}$

$a_2=8\sqrt{2-\sqrt{2+\sqrt{2}}}$

$a_3=16\sqrt{2-\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2}}}}}$

$...$

(b) $b_n=4\times\sum_{i=0}^{n}\frac{(-1)^i}{2i+1}$

More clear:

$b_0=4$

$b_1=4(1-\frac{1}{3})$

$b_2=4(1-\frac{1}{3}+\frac{1}{5})$

$b_3=4(1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7})$

$...$

It seems the first sequence goes to $\pi$ faster than the second one.

Question: What is the fastest known explicit sequence convergent to $\pi$? Please introduce a list of known sequences convergent to $\pi$ and their convergence accelerations.

Answer 1

The provably fastest convergence, in fractions, is given by the continued fraction:

$$[3;7,15,1,292,1,1,1,2,1,3,1,\ldots]$$

This corresponds to the sequence $$3,\frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \frac{103993}{33102},\ldots$$

Answer 2

One of the astounding formulae for $\pi$ is surely https://crypto.stanford.edu/pbc/notes/pi/ramanujan.html

Answer 3

The fastest (by steps/iterations) is Gauss - Legendre algorithm (see AGM method too) and its modifications.

$25$ iterations to get $45$ million correct digits of $\pi$...

But this algorithm is very expansive in time, because each step uses square root calculating (very-very slow operation for huge number of digits).

Release A: (by Brent $-$ Salamin, modification) :

\begin{array}{llll} a_0 = 1, & b_0 = \frac{1}{\sqrt{2}}, & u_0 = 0, & v_0 = 1;\\ a_{n+1} = \frac{a_n+b_n}{2}, & b_{n+1} = \sqrt{a_n b_n}, & u_{n+1} = \frac{u_n+v_n}{2}, & v_{n+1} = \frac{a_nv_n+b_nu_n}{2b_{n+1}} \end{array} and $$ \pi_n = 2\sqrt{2} \frac{a_n^3}{v_n} \approx \pi. $$

First steps:

\begin{array}{|l|l|l|r|}\hline n & p_n & \pi-p_n & \log_{10}(\pi-p_n) \\ \hline0) & \color{gray}{2.828427...} & 3.13165... \times 10^{-1} & -0.50422... \\ 1) & \color{gray}{2.95807...} & 1.83515... \times 10^{-1} & -0.73632... \\ 2) & \underline{3.14}\color{gray}{066686...} & 9.25783... \times 10^{-4} & -3.03349... \\ 3) & \underline{3.1415926}\color{gray}{465191...} & 7.07059...\times 10^{-9} & -8.15054... \\ 4) & \underline{3.141592653589793238}\color{gray}{28322...} & 1.79413... \times 10^{-19} & -18.74614... \\ 5) & \small{\underline{3.1415926535897932384626433832795028841971}\color{gray}{15228...}} & 5.41713... \times 10^{-41} & -40.26623... \\ 6) & ... & 2.39409...\times 10^{-84} & -83.62085... \end{array}

Each iteration multiplies number of correct digits by $\approx 2$.

Release B: (by Brent $-$ Salamin):

\begin{array}{llll} a_0 = 1, & b_0 = \frac{1}{\sqrt{2}}, & t_0 = \frac{1}{4};\\ a_{n+1} = \frac{a_n+b_n}{2}, & b_{n+1} = \sqrt{a_n b_n}, & t_{n+1} = t_n-2^n(a_n-a_{n+1})^2, & \end{array} and $$ \pi_n = \frac{(a_n+b_n)^2}{4t_n} \approx \pi. $$

First steps:

\begin{array}{|l|l|l|r|}\hline n & p_n & \pi-p_n & \log_{10}(\pi-p_n) \\ \hline0) & \color{gray}{2.91421...} & 2.27379... \times 10^{-1} & -0.64324... \\ 1) & \underline{3.14}\color{gray}{05792...} & 1.01340... \times 10^{-3} & -2.99421... \\ 2) & \underline{3.1415926}\color{gray}{46213...} & 7.37625... \times 10^{-9} & -8.13216... \\ 3) & \underline{3.141592653589793238}\color{gray}{27951...} & 1.83130...\times 10^{-19} & -18.73723... \\ 4) & \small{\underline{3.1415926535897932384626433832795028841971}\color{gray}{14678...}} & 5.47210... \times 10^{-41} & -40.26184... \\ 5) & ... & 2.40612... \times 10^{-84} & -83.61868... \end{array}

Each iteration multiplies number of correct digits by $\approx 2$.

Release C: (by Borwein brothers) : (see http://www.cecm.sfu.ca/~jborwein/Kanada_50b.html):

\begin{array}{ll} y_0 = \sqrt{2}-1, & a_0 = 6-4\sqrt{2};\\ y_{n+1} = \frac{1-\sqrt[4]{1-y_n^4}}{1+\sqrt[4]{1-y_n^4}}, & a_{n+1} = (1+y_{n+1})^4a_n - 2^{2n+3}(1+y_{n+1}+y_{n+1}^2), & \end{array} and $$ \pi_n = \frac{1}{a_n} \approx \pi. $$

First steps:

\begin{array}{|l|l|l|r|} \hline n & p_n & \pi-p_n & \log_{10}(\pi-p_n) \\ \hline 0) & \color{gray}{2.91421...} & 2.27379... \times 10^{-1} & -0.64324... \\ 1) & \underline{3.1415926}\color{gray}{46213...} & 7.37625... \times 10^{-9} & -8.13216... \\ 2) & \small{\underline{3.1415926535897932384626433832795028841971}\color{gray}{14678...}} & 5.47210... \times 10^{-41} & -40.26184... \\ 3) & ... & 2.30858... \times 10^{-171} & -170.63665... \end{array}

Each iteration multiplies number of correct digits by $\approx 4$ (in fact, it is interlined release B).

---

Collection of such algorithms: http://www.pi314.net/eng/algo.php.

---

But, in general, there are no "the fastest" sequence, because if the sequence $\{s_n\}$ converges very fast, then the sequence $\{t_n\}$, where $t_n= s_{2n}$ converges faster.