Efficient Integer Representations of Irrationals

[JonBarleycorn]

What are the most efficient integer representations of the irrational numbers Pi and e?

An efficient integer representation of an irrational number is defined as two integers p/q such that their decimal representation gives at least as many significant digits as the sum of p + q.

For example, 22/7 is an efficient integer representation of Pi since p/q (= 3.1428) returns a little better than 3 significant digits.

Hint:

(Pi – 22/7)-1 = -791. In other words 22/7 is good to better than one part in 791.

(Pi - 22/7 + 791-1)-1 = ?

[mart_r]

A good one is 355/113.
There's this number 20776 at position 432 in the continued fraction expansion of pi, if I would calculate the fraction of the 431 previous terms I would also get an efficient integer representation, or whenever such a large number in the continued fraction appears.

The best known approximation is log(640320³+744)/sqrt(163) - it gives 31 significant digits!

Edit: but I don't know of any really good approximations for e.

[CRGreathouse]

An especially good rational representation in this sense is

1901870728566923076090143944714770339621590768313546337192526115562704339680963564320007808107929370299752345187688835741387003036853361285671158059867702399073227994426905220194699766118756059055619036488502928002591
------------
605384255146420326102361023215940531716391478150345020739231253172134740688232476946000058713774549796561447468267746412874022717544100946587144148739626803435133473281606663121381125761746030151344353855924025288111

which represents pi to 3+ more decimal places than the sum of the digits in the numerator and denominator.

[jasonp]

One can produce a stream of these efficient representations by using the continued fraction esxpansion of pi or e. There is a huge body of analysis on this subject, including theorems that in order to get a better rational approximation than a truncated continued fraction, you must use a fraction with larger terms in the numerator and denominator.

Of course, to get a continued fraction expansion of a transcendental number you need to know its decimal expansion first, so it's not exactly like this is a free lunch.

One of my favorites: 6^(0.25) is close to pi/2.

[fivemack]

Of course, to get a continued fraction expansion of a transcendental number you need to know its decimal expansion first, so it's not exactly like this is a free lunch.

That turns out, strangely, not to be the case: if your transcendental number can be written in terms of hypergeometric functions, there are algorithms that get the continued fraction terms directly:

http://www.inwap.com/pdp10/hbaker/hakmem/cf.html

[R.D. Silverman]

Originally Posted by JonBarleycorn

For example, 22/7 is an efficient integer representation of Pi ?

No, it is not. You are confusing the word 'representation'
with the word 'approximation'. A representation of PI is EXACT.
An approximation is not. There are many representations of PI
that use only integers. (e.g. infinite series). There are many
representations that use e.g. elementary transcendental functions such
as 4*ATAN(1). There are infinitely many approximations as the ratio
of two integers.

Furthermore, the word "efficient" needs to be quantified. One way to
do this is in terms of the height of the rational approximation. One
can always find p1/q1 and p2/q2 so that both ratios are good approximations
to PI. But the better the approximation, the larger p_i and q_i will be.
So, if one uses an approximation using the ratio of integers near (say) 20
digits in size and compares it against a ratio using 10 digit integers,
then one must ask: which is more "efficient". The former will be more
accurate, but requires more digits.

You need to tell US what you mean by "efficient".

[axn]

Originally Posted by R.D. Silverman

No, it is not. You are confusing the word 'representation'
<snip>
You need to tell US what you mean by "efficient".

Originally Posted by JonBarleycorn

An efficient integer representation of an irrational number is defined as two integers p/q such that their decimal representation gives at least as many significant digits as the sum of p + q.

.

[R.D. Silverman]

Originally Posted by axn

.

An efficient integer representation of an irrational number is defined as two integers p/q such that their decimal representation gives at least as many significant digits as the sum of p + q.

This definition makes no sense.
Perhaps it merely needs to be reworded.


Take 22/7. p=22, q=7. What does
"their decimal representation" mean?

I will assume that what is meant is that the RATIO 22/7 gives,
in its decimal representation, an approximation [to PI] that is correct to
the specified number of digits. Is this what is meant?

Their decimal representation is
22 and 7 respectively. Their sum is 29. 22/7 does not yield
an approximation to PI that is good to 22 + 7 = 29 digits.

[CRGreathouse]

I looked for rationals a/b such that the number of digits in a and the number of digits in b, subtracted from the number of correct decimals in a/b, was large. My solution has 'goodness' 3.378... which is the highest I found.

I used

goodness(r)={precision(-log(abs(r-Pi)/Pi)/log(10)-digits(numerator(r))-digits(denominator(r)),9)};
best(n)={my(s);if(type(c)!="t_VEC"||#c<n,default(realprecision,n*3);c=contfrac(Pi));s=c[n];forstep(k=n-1,1,-1,s=c[k]+1/s);s};
list(lim,expected=1.3)={for(n=1,lim,g=goodness(best(n));if(g>expected,print(n"\t"g)))};

in Pari to find them.

[R.D. Silverman]

Originally Posted by CRGreathouse

I looked for rationals a/b such that the number of digits in a and the number of digits in b, subtracted from the number of correct decimals in a/b, was large. My solution has 'goodness' 3.378... which is the highest I found.

I used

goodness(r)={precision(-log(abs(r-Pi)/Pi)/log(10)-digits(numerator(r))-digits(denominator(r)),9)};
best(n)={my(s);if(type(c)!="t_VEC"||#c<n,default(realprecision,n*3);c=contfrac(Pi));s=c[n];forstep(k=n-1,1,-1,s=c[k]+1/s);s};
list(lim,expected=1.3)={for(n=1,lim,g=goodness(best(n));if(g>expected,print(n"\t"g)))};

in Pari to find them.

Perhaps looking at pairs (p,q) such that

| p/q - PI| < RHS := 10^-(canonical height of (p/q))

is what is desired?

Or perhaps we want to search globally for the smallest such RHS?

I'm not sure whether RHS is bounded away from 0 for transcendentals.
It can't be too small for *algebraic irrationals* via Thue's Theorem.

[ewmayer]

Originally Posted by R.D. Silverman

This definition makes no sense.
Perhaps it merely needs to be reworded.

Take 22/7. p=22, q=7. What does
"their decimal representation" mean?

I will assume that what is meant is that the RATIO 22/7 gives,
in its decimal representation, an approximation [to PI] that is correct to
the specified number of digits. Is this what is meant?

Their decimal representation is
22 and 7 respectively. Their sum is 29. 22/7 does not yield
an approximation to PI that is good to 22 + 7 = 29 digits.

I'm pretty sure axn meant to write "...gives at least as many significant digits as the sum of the number of digits of p and q", e.g. their digit counts sum to 3, which is to be compared to the number of significant digits in the decimal form of the resulting approximation to pi.

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

1. Efficiency = (number of significant bits in the approximation p/q) / (sum of number of bits of p and q), where "number of bits" means sans any leading zeros, and the number of significant bits is based on the position of the first/leftmost non-matching bit of the irrational number being approximated by ;

2. Efficiency = (number of significant bits in the approximation p/q) - (sum of number of bits of p and q).

-----------------

I'm not sure whether the ratio or the difference is more appropriate. But I don't like either of these, because simple bit-counting can be very misleading as an error metric: for example (using decimals) 3.1415 has more matching leading decimal digits with respect to pi = 3.14159265358979323... than does 3.1416, but the latter is more accurate in terms of actual error. So I prefer an efficiency metric along these lines (here x is the number being approximated by p/q):

Take the logarithm of inverse relative error of the approximation to represent "number of digits of accuracy" in a base-independent way. Divide that by the sum of the same-base logs of p and q. The resulting definition of efficiency (where we assume x, p and q are all positive for the sake of simplicity - one can easily generalize this to handle arbitrary signs of x,p,q):

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

In word form, this formula could be summed up roughly as "number of significant digits in the rational approximation divided by number of input digits required to achieve it".

Let`s try it out - For the above approximations to pi, this gives the following values:

E(22,7) = 1.55...
E(23,7) = 0.60... (Sanity check #1: We expect that beginning with an efficient approximation and changing one of p or q while holding the other fixed should significantly reduce the efficiency of the result)
E(44,14) = 1.21... (Sanity check #2: Using a nonreduced form of a given ratio decreases efficiency)

E(355/113) = 1.53... (p and q roughly double the logarithm vs 22 and 7 and log of relative error is roughly halved, so E about the same as for 22/7)

E(1901870728566923076090143944714770339621590768313546337192526115562704339680963564320007808107929370299752345187688835741387003036853361285671158059867702399073227994426905220194699766118756059055619036488502928002591,605384255146420326102361023215940531716391478150345020739231253172134740688232476946000058713774549796561447468267746412874022717544100946587144148739626803435133473281606663121381125761746030151344353855924025288111)
= 1.01...

That is, using ~200 digits for each of p and q gives ~400 digits of accuracy in the resulting approximation, i.e. the total digits of accuracy is about the same as the total digits used to achieve it, hence E is around unity, making it less efficient that 22/7 and 355/113.

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?