Efficient Integer Representations of Irrationals

[CRGreathouse]

Originally Posted by ewmayer

I don`t like decimal-fetishism myself, so allow me to propose the following 2 possible efficiency metrics for rational approximations p/q:

Why not just compare log pq to -log (|p/q - pi|/pi)? That gets rid of the discreteness issues.

[ewmayer]

Originally Posted by CRGreathouse

Why not just compare log pq to -log (|p/q - pi|/pi)? That gets rid of the discreteness issues.

The boldfaced formula I give above does just that - the first 2 were more or less "thinking aloud".

[m_f_h]

Originally Posted by ewmayer

Efficiency E(x;p,q) = log(x/|x - p/q|) / (log(p) + log(q)).

E(22,7) = 1.55...

So based on this metric, 22/7 is the efficiency champion for rational approximants to pi, with 355/113 running a close second. Can anyone beat 22/7?

3=3/1 is better :
efficiency(3,1) = 2.82... ;-)

[ewmayer]

Originally Posted by m_f_h

3=3/1 is better :
efficiency(3,1) = 2.82... ;-)

True indeed, although one could argue this is due more to large granularity when #digits is small than anything else. If you do similarly with e replacing pi you get roughly half the efficiency(3,1).

But in a way it make perfect sense ... you can get within a few %accuracy for pi using just one digit, which is very efficient. If you want more accuracy, you have to sacrifice some efficiency.

Perhaps the relevant question is "for a given desired level of accuracy, what is the most efficient approximation?" In that context, of one can gain accuracy with little or no sacrifice in efficiency it's a win.

[Uncwilly]

I was thinking (while traveling) of the p function that is used in chemistry.

p[x]=-log₁₀(x)

I would measure the efficiency as (subing r for p for clarity):

E[x;r,q] = p[|x - r/q|] / (int(log₁₀(r) + int(log₁₀(q)))
or
E[x;r,q] = p[|x - r/q|] - (int(log₁₀(r) + int(log₁₀(q)))

For decimal numbers this rewards accuracy, but doesn't punish numbers like 101 v. 999.

I don't have time to run the formulas to show how well they work on 4, 3, 22/7, and 355/113.

[Raman]

Here is one interesting observation:
Take the continued fraction expansion of log 2, log 3, etc. for base = 10.
wims.unice.fr is well equipped with excellent online calculators, plotters, interactive exercises, and then mathematical recreation tools.

CFRAC calculator is available at wims.unice.fr website.
log 2
1/3+ 1/3+ 1/9+ 1/2+ 1/2+ 1/4+ 1/6+ 1/2...
The convergents are given by
1/3, 3/10, 28/93, 59/196, 146/485, 643/2136...
2^Denominator is close to 10^{[SIZE=+1][SIZE=2]Numerator[/SIZE][/SIZE]}

That is, 8, 1024, 9903520314283042199192993792, etc. are all close to power of 10.

Take log 3.
1/2+ 1/10+ 1/2+ 1/2+ 1/1+ 1/13+ 1/1+ 1/7+ 1/18...
Convergents = 1/2, 10/21, 21/44, 52/109, 73/153, 1001/2098, 1074/2251, 8519/17855...
3^{[SIZE=+1][SIZE=2]Denominator[/SIZE][/SIZE]} will be =
9
10460353203
984770902183611232881
9989689095948428268966921126195809393034773710522520293009978943147202723

Ok. Now for any general number say or e.
Will you have to examine for or , for its powers, to be close to a power of 10, having the (numerator + 1) number of digits? Starting up with 1, and keeping on multiplying by in a calculator or taping off its exponent (keeping every value less than 10, by using
, for the k^{[SIZE=+1]th[/SIZE]} power of ), is an interesting task to do so.

= 3 + 1/7+ 1/15+ 1/1+ 1/292+ 1/1+ 1/1+ 1/1+ 1/2+ 1/1+ 1/3+ 1/1+ 1/14...

But, e follows up with a regular pattern, in its continued fraction expansion itself only...
2 + 1/1+ 1/2+ 1/1+ 1/1+ 1/4+ 1/1+ 1/1+ 1/6+ 1/1+ 1/1+ 1/8+ 1/1+ 1/1+ 1/10...

You can even try out with where is the golden ratio = , which has no possible rational approximation at all, since
= 1 + 1/1+ 1/1+ 1/1+ 1/1+ 1/1+ 1/1...

But for sufficiently large n is approximately equal to the n^{[SIZE=+1]th[/SIZE]} Lucas Number, and then n^{[SIZE=+1]th[/SIZE]} Fibonacci Number is approximately equal to the

[Batalov]

For e, the efficient fraction just may be based on the fact that there's Leo Tolstoy year of birth, twice, then the angles of the right isosceles triangle (45,90,45), but we are not going to use the last part, so
(27+1828/9999)/10 = 271801/99990 ?
Does CF sequence contain it?

[JonBarleycorn]

... An efficient integer representation of an irrational number is defined as two integers p/q which, when expressed as a decimal, gives at least as many significant digits as the sum of the digits in p and in q. ...

Finding an efficient representation for e is a little more challenging. While 2721/1001 (= 2.71828172) is accurate to more than one part in 9 million, it does not quite qualify as efficient, and, while 193/71 (= 2.71831) is borderline efficient, it is only accurate to about one part in 36,000.

JB

[mart_r]

Originally Posted by Batalov

For e, the efficient fraction just may be based on the fact that there's Leo Tolstoy year of birth, twice, then the angles of the right isosceles triangle (45,90,45), but we are not going to use the last part, so
(27+1828/9999)/10 = 271801/99990 ?
Does CF sequence contain it?

Not quite.
CF(e)___________=2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,...
CF(271801/99990)=2,1,2,1,1,4,1,1,6,1,1,8,1,1,5.

[Uncwilly]

Originally Posted by Uncwilly

E[x;r,q] = p[|x - r/q|] / (int(log₁₀(r) + int(log₁₀(q)))

I tweaked the formula such that the length of r and q work correctly.

So for a few chosen approximations (of pi) we have (the greater + the better)

r	q	E
4	 	-0.93
3	 	-0.15
22	7	-0.10
333	106	-1.92
355	113	 0.57
312689	99532	-0.46

[Batalov]

Originally Posted by mart_r

Not quite.
CF(e)___________=2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,...
CF(271801/99990)=2,1,2,1,1,4,1,1,6,1,1,8,1,1,5.

Indeed, not the best fraction. It is simply 'worse' than trimming before the 10: 2,1,2,1,1,4,1,1,6,1,1,8,1,1 =>
49171/18089 = 2.7182818287357... (with Tolstoy still happy)