# Approximating $\pi$ with least digits

Do you a digit efficient way to approximate $\pi$? I mean representing many digits of $\pi$ using only a few numeric digits and some sort of equation. Maybe mathematical operations also count as penalty.

For example the well known $\frac{355}{113}$ is an approximation, but it gives only 7 correct digits by using 6 digits (113355) in the approximation itself. Can you make a better digit ratio?

EDIT: to clarify the "game" let's assume that each mathematical operation (+, sqrt, power, ...) also counts as one digit. Otherwise one could of course make artifical infinitely nested structures of operations only. And preferably let's stick to basic arithmetics and powers/roots only.

EDIT: true. logarithm of imaginary numbers provides an easy way. let's not use complex numbers since that's what I had in mind. something you can present to non-mathematicians :)

-
Section 7.6 of this Wikipedia page contains much of the information you desire. – Clive Newstead Aug 7 '12 at 20:37
@CliveNewstead: do you see a particularly efficient way in these equations which "saves digits"? – Gerenuk Aug 7 '12 at 20:43
I can't help but mention that if you represent pi with a decimal, you achieve a 1:1 ratio. If you use a larger-than-10 base for this number, though, you can achieve a very good ratio. I think this method, if legal, would give you the best ratio among the non-exact methods. Unfortunately this method is also not very interesting. – Eric Thoma Aug 7 '12 at 20:44
You may be interested in math.stackexchange.com/a/147422/27624 – Argon Aug 7 '12 at 20:51
@EricThoma: true, but not very efficient ;) Of course on other base system one would have to adjust for the larger digit variety by entropy means. – Gerenuk Aug 7 '12 at 21:27

Perhaps you can use the Gauss Legendre Algorithm ? With 25 iterations, you will produce more than 45 million digits

For example, use bc with the desire scale, and do the algorithm. For a scale of 50, you obtain :

$$\pi_0=\color{red}{2.91421356237309504880168872420969807856967187537693}$$ $$\pi_1=3.14\color{red}{057925052216824831133126897582331177344023751285}$$ $$\pi_2=3.1415926\color{red}{4621354228214934443198269577431443722334535}$$ $$\pi_3=3.141592653589793238\color{red}{27951277480186397438122550483492}$$ $$\pi_4=3.1415926535897932384626433832795028841971\color{red}{1467828263}$$ $$\pi_5=3.14159265358979323846264338327950288419716939937\color{red}{240}$$

(the last 3 digits of error don't come from the algorithm but from the limited scale)

For a scale of 1000, you obtain :

$\pi_9=$3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164$\color{red}{199382}$

So you work on a fixed scale and stop when the algorithm is almost on a fixed point. Only the (very) few last digits will be wrong. And you only need $\log(n)$ iterations for a scale of $n$ ($n$ digits).

-
is it efficient? or will it give an exponential explosion of operations, too? – Gerenuk Aug 7 '12 at 20:41
You can efficiently use this algorithm, with pseudo linear size memory and operations. Of course $k.n\log(n)$ when $n$ is 45'000'000 can be a little too much for the memory part. But it's a very nice algorithm anyway.. – Xoff Aug 7 '12 at 20:49
Sure it's efficient. But if you write out the full equation you will get a very long expression which again isn't efficient anymore? – Gerenuk Aug 7 '12 at 21:28
you can't expect an "algorithmic" expression shorter than the result. But if you stick to square root, multiplication and addition, this method will gives you the shortest for sure. Of course computing arithmetic on very large precision takes a lot of computing steps... – Xoff Aug 8 '12 at 6:29
Can you write out a specific example? I believe with every steps the expression size grows exponentially. – Gerenuk Aug 8 '12 at 7:54

With pure rational approximations, there are sharp limits (related to Roth's Theorem) in terms of how far you can go.

More generally, this will depend strongly on the operations allowed. For example, $$\log(0-1)/\sqrt{0-1}$$ has 5 operations and 4 digits and is exact.

-
true. missed that. but not quite what i meant :) – Gerenuk Aug 7 '12 at 20:40

Using continued fractions you may get as many ratios as you wish and all the ratios are as good as possible!) :

I'll steal part of what I wrote in this other thread and adapt it!

To use continued fractions for evaluation of $x=\pi$.

At each step :

• note the integer part $j\leftarrow \lfloor x\rfloor$ (illustrated in blue)
• compute the new fraction $f$ as illustrated :
• write the previous fraction
• multiply the numerator and denominator by $j$
• add the numerator and denominator of the previous previous fraction (starting with $\frac 10$)
• evaluate the fractional part $x\leftarrow x-j$
• stop when $x$ becomes $0$ or at least very small (depending of the precision of your evaluation) or when you decide too...
• else compute $x$'s multiplicative inverse $x\leftarrow \frac 1x$ and repeat

$\begin{array} {l|r|ccccc} x&j&&&&&f\\ \hline\\ 3.141592653589\cdots & \color{#0000ff}{3} & \color{#0000ff}{3}&=&\frac {\color{#0000ff}{3}}1&=&\frac 31\\ 1/0.141592\cdots=7.0625\cdots & \color{#0000ff}{7} &3+\cfrac 1{\color{#0000ff}{7}}&=& \frac {3\cdot \color{#0000ff}{7}+1}{1\cdot \color{#0000ff}{7} +0}&=&\frac {22}{7}\\ 1/7.0625\cdots=15.99659\cdots & \color{#0000ff}{15}&3+\cfrac 1{7+\cfrac 1{\color{#0000ff}{15}}}&=& \frac {22\cdot \color{#0000ff}{15}+3}{7\cdot \color{#0000ff}{15} +1}&=&\frac {333}{106}\\ 1/0.99659\cdots=1.0034172\cdots & \color{#0000ff}{1}&3+\cfrac 1{7+\cfrac 1{15+\cfrac 1{\color{#0000ff}{1}}}}&=& \frac {333\cdot \color{#0000ff}{1}+22}{106\cdot \color{#0000ff}{1} +7}&=&\frac {355}{113}\\ \cdots &\\ 1/0.003417231\cdots=292.63459\cdots & \color{#0000ff}{292}&3+\cfrac 1{7+\cfrac 1{15+\cfrac 1{1+\cfrac 1{\color{#0000ff}{292}}}}}&=& \frac {355\cdot \color{#0000ff}{292}+333}{113\cdot \color{#0000ff}{292} +106}&=&\frac {103993}{33102}\\ \cdots &\\ \end{array}$

without end since $\pi$ is transcendental!

-
However, unless you get an enormous continuant fairly early, your digit ratio will still be close to $1$. – robjohn Aug 7 '12 at 20:57
@robjohn: yes of course but the best quotients will be in this list (like $355/113$ because the next integer $j$ is large). I merely produced the best ones I was not doing miracles ;-) – Raymond Manzoni Aug 7 '12 at 21:01
As far as rational approximations go, you won't get better than continued fractions (if $|p-q\pi|<\frac1{2q}$, then $p/q$ comes from a continued fraction). I was just noting that the OP was considering digit ratios as important and, in general, continued fractions give a digit ratio of about $1$. – robjohn Aug 7 '12 at 21:09
Anyway I think that $355/113$ is the best result (the next large continuant $20776$ is too far to count...) so that 'extended' rules should be used instead of fractions... – Raymond Manzoni Aug 7 '12 at 21:09
@robjohn: yes I agree (as you see from my previous comment). In fact I was editing (and answering elsewhere) while the rules changed... – Raymond Manzoni Aug 7 '12 at 21:11

Here is a site that focuses on numerical computation of rational approximations of $\pi$: http://www.isi.edu/~johnh/BLOG/1999/0728_RATIONAL_PI/

Also, using a truncated form of the continued fraction will give nice approximations. The first few fractions given are $3$, $22\over7$, $333\over106$, $355\over113$, $103993 \over33102$ and $104348\over33215$. These numerators and denominators are given by the OEIS sequences A002485 and A002486 respectively.

You may be interested in this page. It states that $355 \over 113$ is the "best" (efficiency-wise) rational approximation with the denominator less then 30,000.

-

Let me throw in Clive's suggestion to look at the wikipedia site. If we allow for logarithm (while not using complex numbers), we can get 30 digits of $\pi$ with

$\frac{\operatorname{ln}(640320^3+744)}{\sqrt{163}}$

which is 13 digits and 5 operation, giving a ratio of about 18/30=0.6.

EDIT: Here is another one I found on this site:

$\ln(31.8\ln(2)+\ln(3))$

gives 11 digits of $\pi$ with using 5 numbers and 4 operations.

-

Apparently, I'm not the first to ask -> http://www.contestcen.com/pi.htm

However, they often don't count operations. Surely, but defining the set of allow operations (+, -, *, /, sqrt, pow, ...?) one could set up an information "entropy" measure to make it a fair game :)

-