Date: Thu, 29 Jul 1999 22:07:37 -0700
From: Brian Tung
Message-Id: <199907300507.WAA03381@ude.isi.edu>
To: faber, johnh 
Subject: Re: rational approximations to pi

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John,

Interesting stuff.

There is, by the way, a pretty efficient method of obtaining good rational
approximations to numbers, based on continued fractions.  Here's the basic
idea, illustrated again with PI = 3.141592653589793+.

The first thing you do is break the number into two portions--one is the
integer part, and the second is the decimal part:

    3 + 0.14159...

Then you take the reciprocal of the decimal part to get

              1
    3 + ------------
         7.06251...

Now repeat the above two steps:

               1
    3 + ----------------
         7 + 0.06251...

                1
    3 + -------------------
                   1
         7 + -------------
              15.99658...

With decimal parts greater than 0.5, you can go down from above rather
than up from below:

                    1
    3 + ---------------------------
                      1
         7 + ---------------------
                          1
              16 - --------------
                    292.98696...

To turn this into a rational approximation, start from the bottom and
work up.  We truncate the above fraction and rewrite in one line as
follows:

            1
    3 + ----------
              1
         7 + ----
              16

           1
    3 + -------
          113
         -----
           16

          16
    3 + -----
         113

     335
    -----
     113

Shorter truncations yield 22/7 and of course, the state of Indiana's
very broad approximation, 3/1.  Good approximations are revealed by
a large jump in the size of the numbers in the *following* approximation.
For example, the first four fractions in the series for pi are

         3/1          3.000000000000000
        22/7          3.142857142857143
       355/113        3.141592920353983
    104348/33215      3.141592653921421

The median increase in numerator and denominator is about 4 times.  The
average increase, believe it or not, is undefined--it is infinite.

Now, I realize that this is different from your list--it does not
produce the complete series of approximations that improve in closeness.
This series converges a heck of a lot faster, though.

Here is some C code, not terribly efficiently written, which does the
above work:

#include <stdio.h>
#include <math.h>

main ()
{
    double x;
    int a[100];
    int i;
    int j;
    int d;
    int n;
    int t;
    int s;

    x = PI;
    s = 1;
    for (i = 0; i < 10; i++) {
        if (x < 0) {
            s *= -1;
            x = -x;
        }
        if (x-floor (x) > 0.5)
            a[i] = s*((int) x+1);
        else
            a[i] = s*((int) x);
        x -= (double) (s*a[i]);
        x = 1/x;
        n = a[i];
        d = 1;
        for (j = i-1; j >= 0; j--) {
            t = n;
            n = a[j]*t+d;
            d = t;
        }
        if (n < 0) {
            n = -n;
            d = -d;
        }
        printf ("%10d/%10d     %18.15f\n", n, d, (double) n/d);
    }
}

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv

iQA/AwUBN6EzFvxWUiHQcCAeEQJ4iQCfe8BPYjEteGmBdmTriSVZx9fIbuUAnAvX
vV3+ciN1DDL+BaVb5fNfns6S
=djQe
-----END PGP SIGNATURE-----