Date: Fri, 27 Jan 95 09:47:22 CST
From: rusin (Dave Rusin)
To: rreid@ecst.csuchico.edu
Subject: Re: integer fractions for pi
Newsgroups: sci.math

In article <3gag5n$3om@charnel.ecst.csuchico.edu> you write:
>
>After dealing with the approximation for pi 22/7 for years, I decided
>that there must be a more accurate fraction available.  So, I wrote a

Umm, you're not likely to get a lot of positive feedback on this. Among
other problems, your code has a pretty generous notion of what it takes
to be a "good" approximation, and doesn't take advantage of the well-known
continued fraction algorithm for this purpose.

Continued fractions: given  x, compute successive approximations to x by
computing   x(1)=x, p(-1)=0, q(-1)=1, p(0)=1, q(0)=0 and then recursively
	d(n)=int(x(n)) 
	p(n)=d(n)*p(n-1)+p(n-2)
	q(n)=d(n)*q(n-1)+q(n-2)
	x(n+1)=1/(x(n)-d(n)). 
Then the approximations you want are  p(n)/q(n)  for n>0. 
These approximations have the property that  |x-(p/q)| < 1/(q^2) if and
only if (p/q) is one of the fractions p(n)/q(n), that is, these fractions
are "good" and are the only "good" ones. In fact, |x-(p(n)/q(n))|  is
less than  1/(q(n)*q(n+1)) so the n'th fraction is particularly good
when the next  d(n+1) is rather large (as a rule they tend to be
close to  1  or  2). There are oodles of other interesting facts about
the p(n)/q(n) -- they strictly oscillate around  x, they're in lowest terms,
|x-(p(n)/q(n))| is less than any |x-(p/q)| with  q<= q(n), and so on.

Applied to pi, we get the first few terms to be 3/1, 22/7, and
355/113.  These all appear in your tables of course, but they are so
good that they deserve better mention. And, of course, the labor
needed to find them is miniscule compared to an exhaustive search.

This is not to say that your table of values is without merit, but to
warn you that few readers of sci.math are likely to be impressed.

dave