Wolfram Blog
Jon McLoone

All Rational Approximations of Pi Are Useless

June 30, 2011 — Jon McLoone, International Business & Strategic Development

When I first learned about π, I was told that a good approximation was 22/7. Even when I was 12 years old, I thought this was utterly pointless. 22/7 agrees with π to two decimal places (so three matching digits):

N[22/7]

3.14286

Since there are three digits to remember in 22 and 7, what have you gained? You have just as much to remember, but have lost the notion that π is “just over 3”.

Is there a better rational approximation where we actually get out more digits than we put in? Here is a brief and rather low-brow investigation (and the chance to win something if you can do better).

First we need a function to count digits in the fraction. I am going to generalize a bit and count all characters in the plaintext form of the input. This function is slightly over-engineered to avoid automatic simplification and to strip white space, for reasons that will become clear at the end.

Counting digits in the fraction

characterCount[22/7]

4

This counts the “/” as a character, but, to be fair, we will add 1 to the matching digits to count the “.” in the output as a character too.

matchingCharacters

I don’t want to have to specify the number of digits to evaluate expressions to, so I will give Mathematica permission to use as much automation as it needs to resolve numerical values:

$MaxExtraPrecision ∞;

matchingCharacters[22/7, π]

4

Now I will enumerate a lot of rational approximations. This gets increasingly slow as the approximations get better, so it’s best to do this once and then analyze the resulting list.

Enumerating rational approximations

Here for example is the 100th candidate:

Candidates[[100]]

100th candidate

It has 103 characters to remember:

103 characters to remember

103

And yields 103 characters of π:

matchingCharacters[candidates[[100]], π]

103

Let’s look at the trend.

ListPlot[characterCount /@candidates]

ListPlot graph

That’s pretty linear; we are not going to get better just by virtue of going larger. Let’s look at how many more or less digits we get out compared to those we put in (higher is better).

More or less digits we get out than we put in

ListPlot[freeDigits, PlotRange -> All]

ListPlot graph

So it is possible to get three free digits in the first thousand trials. And in fact, we find that we get four such wins:

Position[freeDigits, 3]

{{432}, {433}, {434}, {435}}

Let’s get the first candidate that gives us three free digits.

candidates[[432]]

First candidate that gives three free digits

Hmm, that’s a lot to remember for just three free digits.

characterCount[Evaluate[%]]

434

Less than 1% return on our investment. Perhaps we should really be looking for the best fractional gain rather than largest absolute gain. Again, let’s look at the trend:

fractionalGain trend

fractionalGainData

ListPlot[fractionalGainData, PlotRange -> All]

fractionalGainData graph

It looks like the trend works against us, and the best values are near the start. The best result is 1 free character for every 7 remembered.

Max[fractionalGainData]

1/7

Putting all these steps together, here is a function to find the best approximation for a number by fractional gain:

Finding the best approximation by fractional gain

findBestApproximation[π, 1000]

355/113

N[%, 20]

3.1415929203539823009

So if you have to tell people to learn a rational approximation of π, it should be 355/113, which gives you 8 characters of correct results for only 7 memorized. But that is still pretty useless.

I searched as high as 10,000 candidates and found no better. If you repeat this analysis with other well-known irrational numbers √2 and e, you find the same behavior. No doubt this is obvious to number theorists! Here are the best results for √2 and e:

findBestApproximation[√2, 1000]

99/70

…with 1 free digit for 5 remembered, and…

findBestApproximation[E, 1000]

848456353/312129649

…with only 1 free digit for 19 remembered.

When I sent this to the blog team to put on the website, Ed Pegg, who writes here regularly, suggested a nice non-rational approximation:

Non-rational approximation

Which by my metrics gives:

Non-rational approximation

38

matchingCharacters

48

Which is an impressive gain of 26%.

Can anyone beat that? If anyone can, I will send a Mathematica T-shirt to the person with the best score at the end of July. (Scoring uses the functions in this blog. Anything that I judge to be outside of the spirit of the competition will be disqualified—that includes the use of programs, integrals, sums, inverse trig functions, π-related values of special functions, or π-related constants (such as π).)

Leave a Comment

59 Comments


Ed Pegg Jr

I also mentioned 7^7/4^9 = 3.1415.

http://www.wolframalpha.com/input/?i=6-6^%28-EulerGamma%29-FeigenbaumAlpha uses just a few characters in the input interpretation for 3.14159269

Posted by Ed Pegg Jr    June 30, 2011 at 3:46 pm
Ed Pegg Jr

Log[((Sqrt[2] Root[x^9-99x^8+38x^7-89x^6+42x^5-65x^4+ 37x^3-22x^2+5x-1,1])^24-24)^2-552]/Sqrt[5692]

gives 153 digits of Pi.

Posted by Ed Pegg Jr    June 30, 2011 at 3:55 pm
Mike Bryniarski

I saw this and immediately thought of convergents of continued fractions.
It turns out that the best approximations found by your method are all convergents:
Last[Convergents[Pi, 4]] = 355/113
Last[Convergents[Sqrt[2], 6]] = 99/70
Last[Convergents[E, 23]] = 848456353/312129649

I am not sure if they will always yield the highest efficiency rational approximation but it seems reasonable (though the base could be important?).

Posted by Mike Bryniarski    June 30, 2011 at 5:06 pm
frud

atan(1)*4 yields an infinite number of digits of pi. That’s easy to remember. :)

Posted by frud    June 30, 2011 at 5:15 pm
Greg Buchholz

Hmm. We can use the natural logarithm and square roots? This will be hard to beat:

(ln -1)/sqrt(-1)

Posted by Greg Buchholz    June 30, 2011 at 5:50 pm
Sophia

Are you Jon going ot be in the conference Wolfram will have at the headquarters?

Posted by Sophia    June 30, 2011 at 9:09 pm
Ken Levasseur

1/989 (4 digits) is the exact value of itself and its decimal representation is 462 repeating digits. Not sure what the score is since I couldn’t locate a Notebook version of the posting to do the calculations.

Posted by Ken Levasseur    June 30, 2011 at 9:57 pm
Jon McLoone

@Ed
When I cleaned up the definitions 7^7/4^9 doesn’t do well, because the ^ count as characters, making it more input than output. The second one is pretty spectacular with a character count of 106 for 154 output characters. However, I am going to introduce a new rule which is “No WRI staff” I am sure you already have enough Mathematica T-Shirts!

Posted by Jon McLoone    July 1, 2011 at 3:08 am
Vadim Ponomarenko

Interesting post. Using decimals is not exactly a fair comparison to fractions, since there is an implicit denominator (and base) that decimals get for free, and fractions don’t. It’s surprising to me that the results are so close.

This may not be in the desired spirit, but allow me to try to revive the value of 22/7. It is equal to 3.1 [base 7], which agrees with 3.14 [base 10], for a savings of 25%.

Posted by Vadim Ponomarenko    July 1, 2011 at 6:56 am
Professor Hubert J. Farnsworth

Here’s one.

π/1

Posted by Professor Hubert J. Farnsworth    July 1, 2011 at 7:40 am
Luboš Motl

Log[I]*2/I + Exp[-4631]

is accurate up to 2011 digits and I only used roughly 5 digits in the formula. ;-)

Posted by Luboš Motl    July 1, 2011 at 8:32 am
Daniel

I always liked the cube root of 31. It gets you four digits for two memorized. I used to use it when my caclulator didn’t have a pi button.

Posted by Daniel    July 1, 2011 at 9:41 am
Jon McLoone

@Greg and Lubos, I definitely had Log[-1] and Log[I] in mind with the “Pi related values of special functions” and “inverse trig functions” limitations, although Lubos, extra points for throwing in the useless Exp term to confusing things.
@ Prof Farsnworth Pi/1 definitely falls foul of the “no Pi related constants (such as Pi) rule.

@Vadim and Danial are both in the spirit of the competition. Unfortunately, my definition of using Mathematica InputForm, perhaps slightly unfairly, works against both of you as the “7^^3.1″ is the base 7 input form at 6 characters, and cube root is “31^(1/3)” at 8 characters.

Sorry notebook was not included, I will try and get that changed. In the meantime, here are two crucial measures…

matchingCharacters[expr_, target_] := Ceiling[-Log10[Abs[expr - target]]] + 1;
characterCount[expr_] := StringLength[StringReplace[ToString[Unevaluated[expr], InputForm], ” ” -> “”]];
SetAttributes[characterCount, HoldAll];

Posted by Jon McLoone    July 1, 2011 at 11:04 am
Jon McLoone

@ Sophia
I go to the annual technology conference most years.
I recommend it to everyone. I don’t think the dates have been announced for this year’s yet but here is info from last years event…
http://www.wolfram.com/events/techconf2010/

Posted by Jon McLoone    July 1, 2011 at 11:14 am
Larry

You can actually get twice the digits you put in for any number of digits input. By using Newton’s iteration to find the root of sin(x), you can calculate pi very efficiently. For example, let a=3.14159. Now, we can find more digits of pi than put in by using:
a=a-(sin(a)/cos(a))
returning 3.1415926535897932(446…), 16 digits for 6 digits memorized.

If we double the digits I put in, I get:
a=3.14159265358, a-(sin(a)/cos(a)), returning 3.14159265358979323846264338327950(319…) = 36 digits for 12 input. (Triple!)

Since I can now double the number of digits I memorize, does that mean I win the contest, or does that count as a “pi-related value of a special function”? It does not directly return infinite digits like, say, sqrt(6*Zeta(2)) or log(-1)/sqrt(-1).

You could also logically extend this to higher order by using a cubic or higher order iteration like Halley’s method. If all else fails, lim n-> inf. of x_n+1=x_n-cos(x_n) = pi/2, letting you use the same principle applied to root solving for memorizing pi/2.

Anyway, just ideas. I guess I win if that is allowed; it doubles the memorized digits.

Posted by Larry    July 2, 2011 at 12:17 am
Ricardo

Not in te spirit of the T-Shirt contest but elegant enough to post
pi + pi^2 + 4 pi^3 = 1 / FineStructureConstant
(within 0.01%)

Posted by Ricardo    July 2, 2011 at 9:35 am
Greg Buchholz

2*(1.5708+cos(1.5708)+cos(1.5708+cos(1.5708))+cos(1.5708+cos(1.5708)+cos(1.5708+cos(1.5708)))+cos(1.5708+cos(1.5708)+cos(1.5708+cos(1.5708))+cos(1.5708+cos(1.5708)+cos(1.5708+cos(1.5708)))))

Posted by Greg Buchholz    July 2, 2011 at 2:09 pm
Larry

For an improved approximation, a-tan(a) sec^2(a) triples digits of pi.
Example:
3.14-tan(3.14) sec^2(3.14)=3.14159265(897…)
Which triples the input digits. (three correct in, 9 correct out)

Based on Householder’s method of sin(x)=0, then simplified trig.

Posted by Larry    July 3, 2011 at 12:24 am
Nabil Fares

Hi,
Here’s a possibility that does marginally better than 26%. Not earthshaking but it works although I don’t know if it is still in the spirit. My candidate is below:

36^^stqx16ojy6l0ingb8qsnm98frdc3kphixo5941pejlq7r26iu8gz30nln9075qzd4t6147fdjkciosc6q22u6fhn91s3nbz323hxlwgk2tft9qvfx4n4bbvwkqc5r79pz2vpdk31g6lt28x9qjj74il991mf73yri5lld3ptunmg08le2qxivkcatjohc9eo1z6ss0kylj2zt56xaylpito2ffezsf29e6tdyvofsnv58mqvid2kty91sxyqfe5hakic47rwcjpw0gr4lkettaqei25wsmzgcsol5baytu5g61o2m0k1g0img82t1 /
36^^96bpnsjun85xvchdyf6ljmy3vtyee0lboj79zymed7mw37nzyd76xzm7y2yx6lxs88dw2kqkybshqvl81106hf35k3u7e2225yxpx6h93fxruawzhiqkiqstipr6alv826rtp8i5h8vpm81vn5qxf9mf3dkvoahhbd4cudb9da9llihtx9ayxgp9u7w5ewizoicnzm8v3ku0phbpbzua2ff4qdxnia6gdyquzcozidwnztctaui0moz3sm1cumh2yswfoetvmlesht4pa479t23j205hco03gp8kww14x2i0mjb03ez9qav5vauy6

The main issue in this challenge is that of data compression. It’s clear that higher bases are often more compact than lower bases. I simply recast numerator and denominators of the convergents of pi into a higher base. The highest base I could use automatically in Mathematica is 36 (otherwise we have to extend the letter base 26 letters + 9 digits + 1). This higher base yielded efficiencies of around 35% at convergents of around 1000.

Of course, bases require extending the digit set from 9 digits to more characters. If we’re allowed to extend the character set indefinitely then we could, in principle, represent all countables (eg. the 1000′th convergent of pi) by one character which gives an efficiency of about 999/1000. This of course would come at the expense of (our) memory in identifying enough single symbols and establishing a universally accepted convention for such digits.

Posted by Nabil Fares    July 3, 2011 at 10:02 am
Larry

3.14159265359-tan(3.14159265359)-tan(3.14159265359
tan(3.14159265359))
gives 117 digits of pi.

3.1415926536-tan(3.1415926536)-tan(3.1415926536-
tan(3.1415926536))-tan(3.1415926536-tan(3.1415926536)-
tan(3.1415926536-tan(3.1415926536)))
gives over 300 digits of pi.

3.1416+sin(3.1416)+sin(3.1416+sin(3.1416))
gives 50 digits of pi

(1.5707963268+cot(1.5707963268)+cot(1.5707963268+cot(1.5
707963268))+cos(1.5707963268+cot(1.5707963268)+cot(1.570
7963268+cot(1.5707963268))))*2
gives around 310 digits of pi

(1.5707963268+cot(1.5707963268)+cot(1.5707963268+cot(1.5
707963268))+cos(1.5707963268+cot(1.5707963268)+cot(1.570
7963268+cot(1.5707963268)))+cos(1.5707963268+cot(1.5707963268)+cot(1.5707963268+cot(1.5707963268))+cos(1.5707963268+cot(1.5707963268)+cot(1.5707963268+cot(1.5707963268)))))*2
Gives a few digits of pi!

Let a = 3.1416,
a+tan(a)+tan(a+tan(a))+tan(a+tan(a)+tan(a+tan(a)))+tan(a+tan(a+tan(a+tan(a))+tan(a+tan(a)+tan(a+tan(a))))
gives many digits of pi with very few actual digits to memorize, but a large function.

sqrt(sqrt(sqrt(9488.531)))
returns 2 free digits for 7 memorized

29809.1^(1/9)
returns 2 free digits

Posted by Larry    July 3, 2011 at 6:37 pm
Robert Nowak

Well, if irrational functions are allowed so why not allow transcendental ones ?

ArcCos[-1]

Just on Number to remeber and its the very first natural one.

Cheers Robert

Posted by Robert Nowak    July 4, 2011 at 7:19 am
Robert Nowak

Hi again,

why not go complex ?

-i Log[-1] or

Cheers Robert

Posted by Robert Nowak    July 4, 2011 at 9:25 am
Larry

31415926535897932384626433832795028841 is prime.

If you could find pi(31415926535897932384626433832795028841), then the
nth prime number
n=pi(31415926535897932384626433832795028841) is 3141592653…841
since the n-th prime number is the inverse of the pi(x) for x is prime. So take (pi(3141592653…841)-th prime)/10^37

Unfortunately, the largest calculation of pi(x) I know of only
found values up to 4*10^22, and even that was only specific
values (they did not calculate anything other than a constant
times a power of ten). You could still try and calculate pi(x) for
large values with more modern tech. That calculation used the
most powerful home computers in the world as of the early
2000′s. Anyone with powerful computers today could at least try
and find pi(3141592653…841)

Posted by Larry    July 4, 2011 at 2:27 pm
Joshua Burkholder

Does the following violate any of the rules?

Module[{n=2^11,b=0},Do[b=Sqrt[2+b],{i,n}];b=Sqrt[2-b];2^(n+1)b]

If not, then I get the following results:
In[1]:=
mep=$MaxExtraPrecision;
$MaxExtraPrecision=Infinity;

matchingCharacters[expr_,target_]:=Ceiling[-Log10[Abs[expr-target]]]+1;
characterCount[expr_]:=StringLength[StringReplace[ToString[Unevaluated[expr],InputForm],”"->”"]];
SetAttributes[characterCount,HoldAll];

characterCount[Module[{n=2^11,b=0},Do[b=Sqrt[2+b],{i,n}];b=Sqrt[2-b];2^(n+1)b]]
matchingCharacters[Module[{n=2^11,b=0},Do[b=Sqrt[2+b],{i,n}];b=Sqrt[2-b];2^(n+1)b],Pi]

$MaxExtraPrecision=mep;
Remove[mep,matchingCharacters,characterCount];

Out[1]= 84
Out[2]= 1235

Of course, if I increase the module’s n, then the module matches more characters of Pi.

Additionally, this module creeps along in “exact” mode. One of the many ways to speed things up is to do the following:

Module[{n=2^11,b=0},Do[b=N[Sqrt[2+b],n],{i,n}];b=Sqrt[2-b];2^(n+1)b]

Very Respectfully,
Joshua Burkholder

Posted by Joshua Burkholder    July 7, 2011 at 1:47 am
Joshua Burkholder

If recurrence relationships are not disallowed, then the following method has good 9th degree convergence (i.e. more “bang for the buck” than the 2nd degree convergence of the Newton-Raphson method):

In[1]:=
(* ——————————————————————— *)
mep=$MaxExtraPrecision;
$MaxExtraPrecision=Infinity;

matchingCharacters[expr_,target_]:=Ceiling[-Log10[Abs[expr-target]]]+1;
characterCount[expr_]:=StringLength[StringReplace[ToString[Unevaluated[expr],InputForm],”"->”"]];
SetAttributes[characterCount,HoldAll];

Timing[
characterCount[
Block[{n=6,p,aP,rP,sP,t,u,v,w,aN,rN,sN},p=3*9^(n-1);aP=N[1/3,p];rP=N[(Sqrt[3]-1)/2,p];sP=N[(1-rP^3)^(1/3),p];Do[t=1+2rP;u=(9rP(1+rP+rP^2))^(1/3);v=t^2+t*u+u^2;w=27(1+sP+sP^2)/v;aN=aP*w+3^(2(i-1)-1)(1-w);sN=(1-rP)^3/((t+2u)v);rN=(1-sN^3)^(1/3);aP=aN;rP=rN;sP=sN;,{i,n}];aN^-1]
]
]
Timing[
matchingCharacters[
Block[{n=6,p,aP,rP,sP,t,u,v,w,aN,rN,sN},p=3*9^(n-1);aP=N[1/3,p];rP=N[(Sqrt[3]-1)/2,p];sP=N[(1-rP^3)^(1/3),p];Do[t=1+2rP;u=(9rP(1+rP+rP^2))^(1/3);v=t^2+t*u+u^2;w=27(1+sP+sP^2)/v;aN=aP*w+3^(2(i-1)-1)(1-w);sN=(1-rP)^3/((t+2u)v);rN=(1-sN^3)^(1/3);aP=aN;rP=rN;sP=sN;,{i,n}];aN^-1]
,
Pi
]
]

$MaxExtraPrecision=mep;
Remove[mep,matchingCharacters,characterCount];
(* ——————————————————————— *)

This gives the following output:

Out[1]= {0.,383}
Out[2]= {2.776,161125}

So for 383 input characters, this matches the first 161,125 characters of Pi without having to wait around very long (2.776 seconds … if you are also using a laptop from 2008 that’s on its “last leg”).

Note: The “n=6″ part in the Block controls everything … and “n=6″ means that we only did 6 iterations of this method to get 161,125 characters of Pi. If we bump that up, then we’ll get a better approximation at the cost of time. Example:

- For n = 7, the Timing on matchingCharacters returns {34.897,1450165} … so if n = 7, then we’ll match the first 1,450,165 charcters of Pi in about 35 seconds.
- For n = 8, the Timing on matchingCharacters returns {504.694,13051532} … so if n = 8, then we’ll match the first 13,051,532 characters of Pi in around 8 minutes 30 seconds

Method Reference: J.M. Borwein & F.G. Garvan, “Approximations to Pi via the Dedekind eta function”, March 1996, accessed on July 9, 2011 from:
http://oldweb.cecm.sfu.ca/organics/papers/garvan/paper/html/node12.html

Very Respectfully,
Joshua Burkholder

Posted by Joshua Burkholder    July 9, 2011 at 1:16 pm
Joshua Burkholder

If recurrence equations are allowed, then here’s one that has 9th degree convergence (as opposed to the 2nd degree convergence of the Newton-Raphson method everyone keeps using above):

In[1]:=
(* --------------------------------------------------------------------- *)
mep=$MaxExtraPrecision;
$MaxExtraPrecision=Infinity;

matchingCharacters[expr_,target_]:=Ceiling[-Log10[Abs[expr-target]]]+1;
characterCount[expr_]:=StringLength[StringReplace[ToString[Unevaluated[expr],InputForm],""->""]];
SetAttributes[characterCount,HoldAll];

Timing[
characterCount[
Block[{n=8,p,aP,rP,sP,t,u,v,w,aN,rN,sN},p=3*9^(n-1);aP=N[1/3,p];rP=N[(Sqrt[3]-1)/2,p];sP=N[(1-rP^3)^(1/3),p];Do[t=1+2rP;u=(9rP(1+rP+rP^2))^(1/3);v=t^2+t*u+u^2;w=27(1+sP+sP^2)/v;aN=aP*w+3^(2(i-1)-1)(1-w);sN=(1-rP)^3/((t+2u)v);rN=(1-sN^3)^(1/3);aP=aN;rP=rN;sP=sN;,{i,n}];aN^-1]
]
]
Timing[
matchingCharacters[
Block[{n=8,p,aP,rP,sP,t,u,v,w,aN,rN,sN},p=3*9^(n-1);aP=N[1/3,p];rP=N[(Sqrt[3]-1)/2,p];sP=N[(1-rP^3)^(1/3),p];Do[t=1+2rP;u=(9rP(1+rP+rP^2))^(1/3);v=t^2+t*u+u^2;w=27(1+sP+sP^2)/v;aN=aP*w+3^(2(i-1)-1)(1-w);sN=(1-rP)^3/((t+2u)v);rN=(1-sN^3)^(1/3);aP=aN;rP=rN;sP=sN;,{i,n}];aN^-1]
,
Pi
]
]

$MaxExtraPrecision=mep;
Remove[mep,matchingCharacters,characterCount];
(* --------------------------------------------------------------------- *)

This gives the following output:

Out[1]= {0.,383}
Out[2]= {504.694,13051532}

This means that we found the first 13,051,532 characters on Pi in about 505 seconds (a little under 8 minutes and 30 seconds) using just 383 characters of input text. In other words, the output is a little more than 3,407,710% of the input.

As before, the “n=8″ in the Block controls everything. To make things faster, decrease n (n=6 gives about 150,000 in about 3 seconds). To makes thing more accurate, increase n … since this method has 9th degree convergence, then every new iteration is 9 times better than the previous iteration.

Method Reference: J.M. Borwein and F.G. Garvan, “Approximations to Pi via the Dedekind eta function”, March 1996, retrieved on July 9, 2011 from: oldweb.cecm.sfu.ca/organics/papers/garvan

Specifically, oldweb.cecm.sfu.ca/organics/papers/garvan/paper/html/node12.html

Very Respectfully,
Joshua Burkholder

Posted by Joshua Burkholder    July 9, 2011 at 3:55 pm
Américo Tavares

Motivated by the title of your nice post: some rational approximations give better irrationality measures (μ) than others. The upper bound of 7.6063 is due to Salikhov (2008), according to http://mathworld.wolfram.com/IrrationalityMeasure.html
Very Respectfully,
Américo Tavares

Posted by Américo Tavares    July 15, 2011 at 3:18 am
Alex

I was going to try to get the t-shirt, but then realized that like the title says, it would be completely useless, so I’m going back to working on my hoverboard.

Posted by Alex    July 19, 2011 at 3:16 pm
paul martin

Much prefer the toothpick and floorboard approach – lots of physical exercise

Posted by paul martin    July 23, 2011 at 1:42 am
Larry

Pseudocode:
(define p to be a rational value with M digit precision)
p = 3.14
p = p – tan(p)
p = p – tan(p) + tan(p)^3/3
p = p – tan(p) + tan(p)^3/3 – tan(p)^5/5
p = p – tan(p) + tan(p)^3/3 – tan(p)^5/5 + tan(p)^7/7

p = p – tan(p) + …. tan(p)^n/n
(define pi to be a built in approximation to pi to M digits)
print p-pi
(end of pseudocode)
yields to some extent b^O(n!) digits for some constant b (in our
case 10).
for n = 6, the decimal digits generated is about 50000.
You could easily fit n=6 in 300 characters.
I’d say character count runs about O(n^2)
The main advantage of this approach is that it requires no while
loops and still has the potential to gain infinite digits/char
It increases the degree of convergence with each added line.
Quick informal proof of lim n-> (char count order of convergence n)/(digits out)=0:
Let the char count = c
Let the current degree of convergence = n
if each added line adds one more degree of convergence to pi, and it takes an extra m character per line,
then sum of k from k*m = 1…n = m*(k^2+k) simplifies to m*k^2 or O(m^2) char count
Now let L be the digits out of an iterative progression of degree n.
If the added digits are d_new=d_old*O(n), and n is variable, we reach
d_n_end = product of O(k)*d_n_strart+k from k = n_start … n_end
for n start at one equals O(k)! = O(k!) digits out
Now we just find our final limit:
lim n -> inf. of n^2/n! = 1/(Gamma(n+1)* (polygamma(0, n+1)^2+polygamma(1, n+1))) = 0 (by L’Hopitals rule)

What this means:
This program would let you achieve an infinite ratio of characters in to digits out, while still staying close to the rules by not employing while loops, products, sums, etc.

See http://numbers.computation.free.fr/Constants/constants.html for info on the iteration

Posted by Larry    July 30, 2011 at 3:03 am
Richard Chapling

((99998! 2)/BernoulliB[99998])^(1/99998)/2
does very well: it’s not a program, and delivers 30,108 characters for 42 memorised (provided Mathematica is to hand, of course!)

And there’s a theorem commonly found in number theory books that states that the best rational approximations to a real number are the convergents of its continued fraction, although I haven’t got an online version to hand.

Posted by Richard Chapling    July 31, 2011 at 8:03 am
Óscar

22/7 is the best aproximation but not matematically, I mean in practice. 22 and 7 are relatively small numbers than can be used in the real world, for construction for example. The next pair of numbers (44/14, 66/21, 69/22, 47/15…) are not as good as 22/7 and not practical (29 real pieces vs 58, 87, 91…). There are more reasons for 22/7 than the simply compression of data, so they are useless in therms of storing info but no useless at all.

Great work anyway!

Posted by Óscar    August 15, 2011 at 5:44 pm
Jon McLoone

Since the month has now passed, I will officially draw the competition to a close.

I am going to declare Larry the winner both by the rules that I laid out and for the depth of his contributions. I think the Wolfram marketing budget can stretch to some runners-up for which I choose Nabil for clever use of bases and Richard Chapling (who I suspect broke the rule on special values of special functions, but in clever enough way that I couldn’t find the definition he based it on) and while they didn’t succeed in terms of the challenge, I liked Greg, Ricardo and Americo Tavares’ contributions. So T-shirts of their choice are going to each of these people. (Contact me if you were one of these people and didn’t get mail from me).

Posted by Jon McLoone    August 24, 2011 at 8:28 am
Mark Samuel Tuttle

Just coming across this now; I understand that it’s closed. The (favorable) exploration of higher bases let me to the following question. Is it always true that “lower” bases are less “efficient” when used for rational approximations? For example, think (Turing machine tapes) unary, then binary, then base 3, etc. I’m guessing that higher bases are always better than lower bases, but that’s only my intuitive feel. (I didn’t take number theory either – a mistake.)
– Mark

Posted by Mark Samuel Tuttle    September 15, 2011 at 10:21 am
gheorghe DRAGAN

Yes indeed, it is useless to mention more than 2 decimals. Practically it is useless to take into consideration more than 3 digits for any measured quantity because the precision ranges between 1/999 and 1/100.
Think about PC vs slide rule.

Posted by gheorghe DRAGAN    September 17, 2011 at 7:16 pm
Heinz-Alfred Fricke

What I like in 355/113 is that it is so easily remenbered: Put down
113355, split it in the middle and just divide (knowing that pi is around 3)!

Posted by Heinz-Alfred Fricke    September 18, 2011 at 9:15 am
Albert van der Horst

I must admit that the article was an eye opener, and the provocative title is aptly choosen.
Still there are situations where the decimal approximation is unfit. 22/7 is better for in the head calculations. In using 16 bits micro processors without floating point 355/113 is usable for scaling: multiply into double precision, then divide. Multiplying by 31,416 then divide by 100,000 is not an option because the latter numbers are too big. This is explained in some detail in the classic “Starting Forth”.

Posted by Albert van der Horst    July 8, 2012 at 7:58 pm
Anon

You were counting raw numbers and missed the one pattern that makes 355/113 better than the rest.

355 / 113

Reverse the order:

113 355

Remove duplicates:

1 3 5

So you only have to “remember” three digits, but do have to remember to “duplicate” each and the flip the order of the first and last three.

And in fact, you don’t have to memorize digits at all, as the three digits are the “first three odd positive integers”.

Posted by Anon    October 1, 2012 at 1:02 pm
notcole

Using 37 decimal digits of PI one can calculate the circumference of a circle the size of the visible universe, and only be off by about 1 nanometer. That’s good enough for most applications.

Posted by notcole    October 1, 2012 at 2:19 pm
Jeroen

I’ve always thought the reason to use a rational approximation of pi isn’t accuracy, but to ease calculations without the use of a calculator or computer.

I was never taught pi is about 22/7, but my grandmother was, somewhere in the 1940′s. In those days the average high-school student most definitely did not have access to a calculator, making 22/7 a handy approximation to let her finish her homework.

Posted by Jeroen    October 1, 2012 at 3:14 pm
JD

http://pi.lacim.uqam.ca/eng/approximations_en.html <- I think this is what you were looking for

Ramanujan's log(262537412640768744)/sqrt(163) seems best

Posted by JD    October 1, 2012 at 3:42 pm
Florian

I know this will be judged as outside of the spirit of the competition, but this C program will compute pi to 15000 digits

a[52514],b,c=52514,d,e,f=1e4,g,h;
main(){for(;b=c-=14;h=printf(“%04d”,e+d/f))
for(e=d%=f;g=–b*2;d/=g)d=d*b+f*(h?a[b]:f/5),a[b]=d%–g;}

Posted by Florian    October 1, 2012 at 4:36 pm
Gene

here…. all you have to do is remember how to spell pie, which by the time you learn 3.14 does not take any extra memory:
http://s3-ec.buzzfed.com/static/imagebuzz/web03/2010/4/12/5/pi-pie-29590-1271063492-58.jpg

…that’s better than remembering 3 digits.

I win.

Posted by Gene    October 1, 2012 at 5:56 pm
    Ryan

    That’s not as efficient as you’d think, when you take 0x into account.

    0xFF vs 255 is one extra “digit”.
    0xFFFF vs 65535 is no gain, add one and you’re behind by a digit.
    0xFFFFFFFF is 10, vs 10 digits for 4294967295, and again, just add one to go behind again.

    Posted by Ryan    October 2, 2012 at 2:39 am
Derek

õ/N, ascii values 245/78 = 3.1410255

Posted by Derek    October 1, 2012 at 7:29 pm
Mu

I think you may have missed the point of the 22/7 approximation. It’s not there to make things easier to remember. It’s there so that e.g. builders, gardeners building things know that if they have ‘integers’ (aka slabs, plant pots) they can arrange them in lines/circles in a 22/7 ratio with relatively few problems that glue can’t solve. The error at that level is manageable and is ‘positive’ e.g. your center line of 7 things fits into your circle of 22 rather than overlapping it.

Posted by Mu    October 1, 2012 at 7:53 pm
yonemoto

This is interesting, but what about the inverse problem. Can you construct an irrational number x in base N such that for each M there exists an approximation p/q, where digits(p) = digits(q) = M, and digits(x) – M is an increasing function of M

Posted by yonemoto    October 2, 2012 at 12:47 am
Storm

22/7 is actually less entropic a string than 3.14. And therefore easier to remember (by a tiny margin)

Posted by Storm    October 2, 2012 at 5:01 am
Raf Fulcher

Does pi squared qualify? In that case its an easy to remember 3 digit number divided by another easy to remember 3 digit number divided by a number which is three repeated numbers followed by two repeated numbers followed by a final number reoccuring. Trust me ; its pi correct to 10DP with the last one correctly rounded up . Work it out.

Posted by Raf Fulcher    February 4, 2013 at 6:12 pm
Lucian

The whole trick with Ramanujan’s approximation is that the 30-digit number he managed to obtain can be written as a 6-digit cube + 744. Hence the great reduction of digit size. He based himself not on fractions, but on powers (of e to a multiple of Pi). The whole idea is to be able to re-write that N-digit numerator, or denominator, or power in a way which drastically decreases its digit-size. Try calculating for instance Round (Pi ^ N), and then try to muster up some sort of digit reducing alternative spelling for the number thus obtained, then write Pi as Radical of order N from that alternatively spelled large number. Though I have to warn that I’ve already tried that, as well as few other tricks, based on other Ramanujan-inspired approximations, and came up short. :-)

Although I know both Pi and E and Phi with over 40 digits each, I think that the best bargain for Pi is 3. 14 16, because it gives you a precision in the range of 10^-6 for only 4 (instead of 6) digits memorized, with 3 + 1 = 4, and 14 & 16 being consecutive even numbers. 355 / 113 is also easy to remember, once you realize that it’s constructed from the first three odd numbers (1, 3, and 5), each appearing twice, starting with the denominator. Likewise for Sqrt (2): it is best to remember that 1 / Sqrt (2) ~= 0.707 (a simple-looking repeating sequence obviously close to 70 / 99), from which the 99 / 70 approximation flows easily.

Posted by Lucian    July 31, 2013 at 8:48 pm
Jesse Elliott

Base 10 is infinitely inferior to other mathematical notations. Just remember an infinite series expansion for pi, such as 4*sum_{n = 0}^infinity (-1)^n/(2n+1) (24 characters), and then you can compute as many digits of pi as you like, to your heart’s content. That’s what computers and calculators do.

http://mathworld.wolfram.com/PiFormulas.html

Posted by Jesse Elliott    November 9, 2013 at 6:54 pm
bigjeff5

So, I’m very late to the party (like all of the last few posters), but I really think it’s important to stress what Paul Draper and others have pointed out:

Human memory doesn’t work the same way computer memory does. We remember patterns far more easily than abstract numbers. I’m not a mathematician or an engineer, so I rarely calculate the circumference of a circle, and thus only remembered pie to 3 digits (3.14, obviously). Paul’s “For I know I chose knowledge to obtain life’s goal” has, in the last 5 minutes, taught me another 7 digits almost immediately. It’s easier to remember than 3.14159, let alone 3.141592654.

I think you should re-do all of these calculations based on entropy, rather than raw digits. If you do, you’ll see the rational representations shoot way ahead.

355/113 is only about 10-15 bits of entropy, assuming 3.3 bits per decimal digit (a standard estimate) as you only have to remember 3 digits – 1, 3, and the pattern. That’s actually really high, considering it’s also ignoring the pattern that cuts the entropy down to somewhere around 1 bit per digit. The value of pi that that 10-15 bits of entropy generates is about 23 bits of entropy – a huge savings. Also remember that each number you add is harder to remember than the last, which is kinda the point of the entropy calculation, so that 15 is a whole lot easier than that 23.

The phrase is a lot harder to calculate, because assuming each word is random you get an insane amount of entropy (thousands of bits), yet it is easier to remember than 355/113, so it’s obviously around 15 bits of entropy or less. It’s hard to quantify how much the pattern cuts it down, but it’s obviously a huge amount. 3.141592654 is much harder to remember. Plus, it looks a heck of a lot better as a signature than the number.

Posted by bigjeff5    March 16, 2014 at 1:47 pm


Leave a comment

Loading...

Or continue as a guest (your comment will be held for moderation):