14
$\begingroup$

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 :)

  • 0
    I just tried the common powerful series approximations, but the$y$ give a constant number of pi digits, while requiring a lot of digits per term :( So again no "compression" of pi.2012-08-08

7 Answers 7

2

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 :)

12

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!

8

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.

  • 0
    true. missed that. but not quite what i meant :)2012-08-07
6

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).

  • 0
    Deeeply nested for sure, as you do geometric mean and arithmetic mean each step.2012-08-08
6

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.

4

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.