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