Rational Approximations (Part II)

Last week, we noticed a fun connection between lattices and fractions, which helped us get rational approximations to real numbers. Since only points close to the (real-sloped) line are of interests, only those points representing fractions are candidates for rational approximation, and the closer to the line they are, the better.

But what if we find a point real close to the line? What information can we use to refine our guess?

Geometrically, the gap between a point and the line also gives you the angle between the real number (seen as a line) and the rational approximation (also seen as a line, shown in blue in the figure):

So we can use this information to correct our estimate. But since the angle is itself irrational (since an irrational minus a rational is an irrational), we kind of end up with the same problem: to get a corrected rational approximation, we should get a rational approximation of the error!

Well, it’s not as bad as it seems. Since the error is (hopefully) tiny, the approximation of the error should also have itself a tiny error. So we can guess somewhat roughly, and add that correction to the current approximation. How do we get a rough approximation rapidly?

If \varepsilon is the (rather small) error, we can choose some denominator d such that

\displaystyle \varepsilon \geqslant \frac{1}{d}.

Turns out, if we put

\displaystyle d=\left\lceil \frac{1}{\varepsilon} \right\rceil,

we just have found an acceptable fraction.

Then the algorithm is pretty simple. We start at some initial guess g (that doesn’t have to be very good), say something like

\displaystyle g=\frac{ c 1000 }{1000},

for the constant of interest, c. We set \varepsilon=c-g, find \displaystyle d=\left\lceil \frac{1}{\varepsilon} \right\rceil, and compute

\displaystyle g'=g+\frac{1}{d}.

We iterate until we reach machine-precision.

* *

The surprise is how fast this simple algorithm converges. Using Mathematica (because of arbitrary precision arithmetic), for c=\pi, we get the first few iterations:

Iter Fraction Numerically Error
0 \displaystyle \frac{31}{10} 3.1 0.0415926535
1 \displaystyle \frac{157}{50} 3.14 0.0015926535
2 \displaystyle \frac{49323}{15700} 3.1415923566… 2.97 × 10-7
3 \displaystyle \frac{10382850073}{3304963825} 3.141592653589… 6.97 × 10-15
4 \displaystyle \frac{1489212077954063443669932}{474030927037084335860675} 3.141592653589… 2.25 × 10-29

* *

So now we have an algorithm that more or less doubles the number of significant digits per iteration. That’s fine, but that still doesn’t solve the really interesting problem that is, how do we get “cute” and precise rational approximations?

2 Responses to Rational Approximations (Part II)

  1. plasmacel says:

    I didn’t success to implement this algorithm. Could you provide some pseudo code?

    • Here’s a small Mathematica implementation:

      a = \[Pi]
      s = 10
      c = Floor[a  s]/s (* 1st candidate *)
      For[i = 1, i < 7, i++,
       e = a - c; 
       d = Ceiling[1/e];
       c += 1/d;
       Print[c, "\t", N[c, 20], "\t", N[a - c, 20]];

      That’s the code I used to produce the results above (and beyond).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: