Calculating pi manually

Question

Hypothetically you are put in math jail and the jailer says he will let you out only if you can give him 707 digits of pi. You can have a ream of paper and a couple pens, no computer, books, previous pi memorization or outside help.

What is the best formula to use? Where best will result in the least margin of error (most important) and is decently quick (second importance).

707 probably seems arbitrary, but I got it from here: http://en.wikipedia.org/wiki/William_Shanks

Also I don't really understand how he could use that formula because I thought you need a table to get arctan values or it would probably take a long time to make values of arctan to use in the formula, but that isn't too important.

I asked this question today because it celebrates the most accurate pi day for the next 100 years :)

Answer 1

Gauss–Legendre algorithm is really good, it only uses four elementary operation and square root; it also converges very fast.

Answer 2

As metioned in Wikipedia's biography, Shanks used Machin's formula $$ \pi = 16\arctan(\frac15) - 4\arctan(\frac1{239}) $$

The standard way to use that (and the various Machin-like formulas found later) is to compute the arctangents using the power series

$$ \arctan x = x - \frac{x^3}3 + \frac{x^5}5 - \frac{x^7}7 + \frac{x^9}9 - \cdots $$

Getting $\arctan(\frac15)$ to 707 digits requires about 500 terms calculated to that precision. Each requires two long divisions -- one to divide the previous numerator by 25, another to divide it by the denominator.

The series for $\arctan(\frac1{239})$ converges faster and only needs some 150 terms.

(You can know how many terms you need because the series is alternating (and absolutely decreasing) -- so once you reach a term that is smaller than your desired precision, you can stop).

---

The point of Machin-like formulas is that the series for $\arctan x$ converges faster the smaller $x$ is. We could just compute $\pi$ as $4\arctan(1)$, but the series converges hysterically slowly when $x$ is as large as $1$ (and not at all if it is even larger). The trick embodied by Machin's formula is to express a straight angle as a sum/difference of the corner angles of (a small number of different sizes of) long and thin right triangles with simple integer ratios between the cathetes.

The arctangent gets easier to compute the longer and thinner each triangle is, and especially if the neighboring side is an integer multiple of the opposite one, which corresponds to angles of the form $\arctan\frac{1}{\text{something}}$. Then going from one numerator in the series to the next costs only a division, rather than a division and a multiplication.

Machin observed that four copies of the $5$-$1$-$\sqrt{26}$ triangle makes the same angle as an $1$-$1$-$\sqrt2$ triangle (whose angle is $\pi/4$) plus one $239$-$1$-$\sqrt{239^2+1}$ triangle. These facts can be computed exactly using the techniques displayed here.

Later workers have found better variants of Machin's idea, nut if you're in prison without reference works, it's probably easiest to rediscover Machin's formula by remembering that some number of copies of $\arctan\frac1k$ for some fairly small $k$ adds up to something very close to 45°.

Answer 3

A pretty simple method i would use if i had no access to books would be to just calculate the alternating sum of reciprocals of consecutive odd numbers and multiply by four, since $$\sum_{k=0}^\infty\frac{(-1)^k}{2k+1}=\frac \pi 4$$ It would take a very very very long time though, but it is a fairly simple method.

---

Another method would be to make some kind of small, circular pool, measure the diameter, then pour water from a measure cup into the pool, keeping in mind the amount of water you have pured. Once the pool is filled to a certain height, measure the height and, since the volume of water is given by $h*d*\pi$, then with a big (diameter-wise) enough pool we could be able to work out the digits accurately enough. This approach is less time consuming but needs a lot more resources.

Answer 4

The following formula by Ramanujan gives 8 correct decimal digits for each $k$.

$$ \pi = \left( \frac{2\sqrt{2}}{9801} \sum^\infty_{k=0} \frac{(4k)!(1103+26390k)}{(k!)^4 396^{4k}} \right)^{-1}.$$

If you calculate the partial sum from $k=0$ to $88$, then you will get $712$ correct digits of $\pi$.

Answer 5

Hand him 707 digits, starting with 111111 then moving on to 222222 and 3333 and so forth. Call your jailor over and tell him you have 707 digits of pi. Out of the kindness of your heart, offer to help him put them in the right order after he lets you out.

Answer 6

If pi is a normal number, you can give him any sequence of 707 numbers and they are guaranteed to be digits of pi...

Answer 7

Using Bellard's formula, you can find $707$ digits of $\pi$ with relatively simple operations taking $233$ terms of the series (i.e. $n_{\mathrm{max}}=233$):

$$\pi = \frac1{2^6} \sum_{n=0}^\infty \frac{(-1)^n}{2^{10n}} \, \left(-\frac{2^5}{4n+1} \right. {} - \frac1{4n+3} + \frac{2^8}{10n+1} - \frac{2^6}{10n+3} \left. {} - \frac{2^2}{10n+5} - \frac{2^2}{10n+7} + \frac1{10n+9} \right).$$

Another option is to use Bailey–Borwein–Plouffe digit extraction algorithm for base-$16$ representation of $\pi$, since no one said the digits must be decimal.

Answer 8

Nilakantha's Series haven't been mentioned yet.

$$ \pi = 3 + \frac4{2\times3\times4} - \frac4{4\times5\times6} + \frac4{6\times7\times8} - \frac4{8\times9\times10} + \dots $$

Without dots: $$ \pi = 3 + \sum_{k=1}^\infty (-1)^{k+1}\frac1{k \times (2k+1) \times (k+1)} $$

This formula is better than Leibniz's formula, but inefficient compared to Machin's formula.

It gives the first five digits of pi in (only) 14 terms of the series. Yet with it, computing each next digit of pi requires to compute twice as many terms as for the previous digit. So it can't be used to compute the 707 firsts digits of pi.

Answer 9

You can use this method that counts digit for digit in any base:

http://bellard.org/pi/pi_n2/pi_n2.html

And if you can smuggle in a computer there are programs using this method:

https://stackoverflow.com/questions/5905822/function-to-find-the-nth-digit-of-pi

Answer 10

We may use Leibniz series combined with the Euler-Maclaurin formula.

$$\frac\pi4=\sum_{k=0}^\infty\frac{(-1)^k}{2k+1}\\\small=1-\sum_{k=1}^{n-1}\left(\frac1{4k-1}-\frac1{4k+1}\right)-\int_n^\infty\left(\frac1{4x-1}-\frac1{4x+1}\right)~\mathrm dx-\frac12\left(\frac1{4x-1}-\frac1{4x+1}\right)-\sum_{k=1}^p\frac{B_{2k}}{2k}\left(\frac1{(n-1/4)^{2k}}-\frac1{(n+1/4)^{2k}}\right)+R_{n,p}\\|R_{n,p}|<\frac{3\cdot(2p)!}{(6n^2)^{2p}}$$To get 707 digits of $\pi$, you'll need $|R_{n,p}|<10^{-708}$. For example, taking $p=833,n=20$ gives the desired error.

$$\pi\pm10^{-708}=1-\sum_{k=1}^{19}\left(\frac1{4k-1}-\frac1{4k+1}\right)-\ln\left(1+\frac2{79}\right)-\sum_{k=1}^{833}\frac{B_{2k}}{2k}\left(\frac{4^{2k}}{79^{2k}}-\frac{4^{2k}}{81^{2k}}\right)$$

Where $B_k$ are the Bernoulli numbers and you can evaluate

$$\ln\left(1+\frac2{79}\right)\pm10^{-708}=-\sum_{k=1}^{442}\frac1k\left(-\frac2{79}\right)^k$$

and $\pm$ denotes maximum possible error.

Answer 11

There are a few super-convergent series and sequences that may be used to approximate $\pi$. I add this as a CW since I already have my own answer, and I merely stumbled upon this one, though I have absolutely zero clue how they work.

The mentioned series and sequences are known as Borwein's algorithm.

The first such example:

\begin{aligned}A&=212175710912{\sqrt {61}}+1657145277365\\B&=13773980892672{\sqrt {61}}+107578229802750\\C&={\big (}5280(236674+30303{\sqrt {61}}){\big )}^{3}\end{aligned}

$$\frac1\pi =12\sum_{n=0}^{\infty }\frac{(-1)^{n}(6n)!\,(A+nB)}{(n!)^{3}(3n)!\,C^{n+1/2}}$$

This series only requires about 30 terms to get 707 digits of $\pi$.

The second such example:

\begin{aligned}A={}&63365028312971999585426220\\&{}+28337702140800842046825600{\sqrt {5}}\\&{}+384{\sqrt {5}}(10891728551171178200467436212395209160385656017\\&{}+4870929086578810225077338534541688721351255040{\sqrt {5}})^{1/2}\\B={}&7849910453496627210289749000\\&{}+3510586678260932028965606400{\sqrt {5}}\\&{}+2515968{\sqrt {3110}}(6260208323789001636993322654444020882161\\&{}+2799650273060444296577206890718825190235{\sqrt {5}})^{1/2}\\C={}&-214772995063512240\\&{}-96049403338648032{\sqrt {5}}\\&{}-1296{\sqrt {5}}(10985234579463550323713318473\\&{}+4912746253692362754607395912{\sqrt {5}})^{1/2}\end{aligned}

$$\frac{\sqrt{-C^3}}\pi=\sum _{n=0}^\infty\frac{(6n)!}{(3n)!(n!)^3}\frac{A+nB}{C^{3n}}$$

This series only requires about 15 terms to get 707 digits of $\pi$.

The last example I will show:

\begin{aligned}a_{0}&={\frac {1}{3}}\\r_{0}&={\frac {{\sqrt {3}}-1}{2}}\\s_{0}&=(1-r_{0}^{3})^{1/3}\end{aligned}

\begin{aligned}t_{n+1}&=1+2r_{n}\\u_{n+1}&=(9r_{n}(1+r_{n}+r_{n}^{2}))^{1/3}\\v_{n+1}&=t_{n+1}^{2}+t_{n+1}u_{n+1}+u_{n+1}^{2}\\w_{n+1}&={\frac {27(1+s_{n}+s_{n}^{2})}{v_{n+1}}}\\a_{n+1}&=w_{n+1}a_{n}+3^{2n-1}(1-w_{n+1})\\s_{n+1}&={\frac {(1-r_{n})^{3}}{(t_{n+1}+2u_{n+1})v_{n+1}}}\\r_{n+1}&=(1-s_{n+1}^{3})^{1/3}\end{aligned}

$$a_k\to\frac1\pi$$

To get 707 digits of $\pi$, you only need to evaluate out to $a_5$ or $a_6$. (I have no idea, but apparently if $a_n$ approximates $\pi$ out $k$ digits, then $a_{n+1}$ approximates $\pi$ out approximately $9k$ digits. Insane!)