Approximating Pi with Continued Fractions

Date: 03/18/2006 at 14:19:46
From: Titus
Subject: Approximation of pi using integers

Pi approximately equals 22/7.  How does one generate increasingly 
accurate approximations of pi using the division of one integer by 
another?  What are some of the results of this series?

There must be such a series, but I don't know how to generate it. 
Also, can one use an integer division to get a value of pi that has 
noticeably more places of accuracy than the number of digits used in 
the integer division, like some form of mathematical free lunch?

Date: 03/18/2006 at 16:39:12
From: Doctor Vogler
Subject: Re: Approximation of pi using integers

Hi Titus,

Thanks for writing to Dr. Math.  Your question has to do with the
topics of Diophantine approximation (how much accuracy you can get
with a certain number of digits) and continued fractions (the division
you referred to).

The idea of continued fractions is writing a number in the form

  pi = 3 + 1/(7 + 1/(15 + 1/(1 + 1/(292 + 1/...))))

By truncating this series after a certain number of steps, you get
pretty good rational approximations.  For example

  3 + 1/7 = 22/7

  3 + 1/(7 + 1/15) = 333/106

  3 + 1/(7 + 1/(15 + 1/1)) = 355/113

and so on.  To find the numbers 3, 7, 15, 1, etc., start with a good
decimal approximation of pi (for example, hit the "pi" button on your
calculator), and then subtract off the integer part (3) and write it
down.  This will leave you with something between 0 and 1.  Invert it.
(ie, divide 1 by that number.)  Write down the integer part of the
result and subtract it off.  Invert again, and so on.  That's how you
get the continued fraction for some number.

As for Diophantine approximation, that is the study of how close
rational numbers (or algebraic numbers) can get to other numbers. 
There are many results of various kinds in this field, and I would
recommend a book on the subject, such as Alan Baker's "Transcendental
Number Theory."  For example, there is an easy result that, given any
real number R, there are infinitely many rational approximations p/q
such that

  abs( R - p/q ) < 1/q^2.

Such approximations are called "good" rational approximations.  Note
that taking the first several digits after the decimal place almost
never gets you a good rational approximation.  But truncating
continued fractions often will.  Another result is that if e > 0 and R
is a rational or an algebraic number, then there are only *finitely*
many rational approximations p/q such that

  abs( R - p/q ) < 1/q^(2+e).

You can also state this as:  If e > 0, and R is an algebraic number,
then there is a constant C (depending on e and R) such that *every*
rational number has

  abs( R - p/q ) >= C/q^(2+e).

This means that, in some sense, "good" rational approximations don't
really get much better, at least for algebraic numbers.  Well, pi 
isn't algebraic.  It turns out that pi is hard to get a handle on.  It
is believed that the above statement (with e > 0) also applies to pi,
especially since it can be proved that the above statement applies to
*nearly* all real numbers.  But the best that I have seen proven is

  abs( pi - p/q ) >= 1/q^42.

In any case, I suppose that you would say that, since every real 
number has "good" rational approximations, the "free lunch" you are
referring to would be getting a large number for

  q^2 * abs( pi - p/q ).

It is not known if this quantity can get arbitrarily large or not (as
far as I know), but this at least gives you some precise meaning to
the questions you are asking.  And if you want to learn more, then you
should read some books on Diophantine approximation (a.k.a.
transcendental number theory) and perhaps some books on continued
fractions.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/