Pi question

Factual Questions
1

Some of my friends and I were talking about pi the other day and the subject came up of just exactly how good an approximation of pi the fraction 22/7 was. I thought it was good enough for anything we would ever do, less than a 1% difference. But the others argued that they could obviously see a “large” difference.

So I set about to find the best fraction I could within the limits of Quickbasic. I went denomenator by denominator looking for the best fractions. Along the way I found something very interesting-



3/1
13/4
16/5
19/6
22/7
179/57
201/64
223/71
245/78
267/85
289/92
311/99
333/106
355/113
148 fractions between 52163/16604 and 104348/33215
208341/66317
312689/99532
833719/265381
1146408/364913
3126535/995207
4272943/1360120
5419351/1725033
42208400/13435351
47627751/15160384
53047102/16885417
58466453/18610450
63885804/20335483
22060516/22060516
74724506/23785549
80143857/25510582

Between 52163 and 104348 is what I like to call a “Petty Island of Pi Fraction Activity.” I define a PIPFA (OK, maybe I need a snazzier acromym) as starting at point X (in this case 52163) and ending at almost, but not quite exactly 2X (in this case 104384) that contain a great deal of changes in the best fractional approximation of pi. After I discovered (in the sense of could possibly miss) the first one I realized I had two other smaller islands-- 13/4 to 22/7 and 179/57 to 355/113. There is possibly another small one starting at 42208400/13435351 but I passed beyond Quickbasics ability to calulate in this case. [digression] I once had a QB library that would let you calculate quadruple length real numbers, but I seemed to have lost it, probably a couple of computers ago. Does anyone know where I can find it again? [/digression]

My question is, why do these islands exist? They can’t possibly be a coincidence.

2

How’s this?

3

It’s not exactly what I wanted (it’s for integers not real numbers) but I could make it work if I wanted. Thanks.

4

You may want to learn about continued-fraction approximations. (These are the best rational approximations possible with denominator less than a given bound.) Your PIPFAs are associated with particularly good rational approximations (like 22/7 and 355/113). Consider, for example, this subsequence of rational approximations:

Now 179/57 turns out to be a pretty good approximation to pi, but it’s a little bit too small. 22/7 is also a pretty good approximation, but a little too big. So what about (179+22)/(57+7)=201/64? You can convince yourself that this strange way of combining fractions (from a/b and c/d to (a+c)/(b+d)) produces one of intermediate value, so it’s got to be even better than 179/57. This process continues until you find another Really Good approximation (and until the new approximation errs in the same direction as the old good approximation 22/7), in this case at 355/113 (which, like 22/7, is slightly larger than pi). These Really Good approximations are the ones produced by a continued-fraction expansion.

5

I’m not entirely sure what you mean (and I’m not claiming that I’ll be able to answer your question once I do figure that out, but maybe someone else can).

What do you mean by “a great deal of changes in the best fractional approximation of pi”?

Looking at your list, I’m getting the impression (which may be wrong, of course) that you’re considering only those denominators which allow for a “good” approximation of pi.

For example, you include 333/106, but do not include 336/107. Is it because the first is a “better” approximation than the second? If so, do you have any specific criteria on which you base whether or not a given rational number is a “good” approximation for pi or not?

6

Sorry. I coulda sworn there were real number arbitrary-precision QB libraries on that page somewhere.

7

Yes, his list is of fractions which produce a better approximation (smaller value of |pi - m/n|) than any fraction with smaller denominator. Perl script:


use POSIX; $pi=4*atan2(1,1); $e=1;
for($n=1;$n<100000;++$n) {
  $m = floor($n*$pi+0.5);
  $en= abs($een=$pi-$m/$n);
  if( $en < $e ) {
    $e = $en;
    printf( "%5d/%-5d : %13.10f
", $m, $n, $een );
  }
}
8

Gotcha, that makes sense.

I don’t really know much about the continued fraction for pi (it’s been about 15 years since I thought about continued fractions at all), but like Omphaloskeptic mentioned, it seems as though that’s where you should look. I thought I’d provide a direct link to a page about the (simple) continued fraction for pi:

http://mathworld.wolfram.com/PiContinuedFraction.html

9

My program starts with “1” as a close approximation to pi. It then goes through the procedure described above until it finds a closer one. If you still have trouble, here’s the source code. Try not to laugh too much at my programming because I started to do the output one way and they switched midstream to another, hence some of the variables. Also, it was written on a PDA (using Quickbasic 4.5 and PocketDOS) in less than 5 minutes. It was never intended to be a sleek, well trimmed program.


      ON ERROR GOTO 1000
      OPEN "pifrac.txt" FOR APPEND AS #1
      DIM x AS DOUBLE
      DIM x2 AS DOUBLE
      DIM x3 AS DOUBLE
      DIM y AS LONG
      CLS
      DIM z AS LONG
      DIM a(20, 2) AS LONG
      DIM pi AS DOUBLE
      pi = ATN(1) * 4
      a(1, 1) = 1
      a(1, 2) = 1
      z = 1
100   b$ = INKEY$
      IF b$ <> "" THEN END
      y = INT(pi * z)
      x = y / z
      x2 = ABS(pi - x)
      x = a(1, 1) / a(1, 2)
      x3 = ABS(pi - x)
      IF x2 < x3 THEN GOSUB 200
      y = y + 1
      x = y / z
      x2 = ABS(pi - x)
      x = a(1, 1) / a(1, 2)
      x3 = ABS(pi - x)
      IF x2 < x3 THEN GOSUB 200
      IF z / 1000 = INT(z / 1000) THEN
        LOCATE 20, 1
        PRINT z
      END IF
      z = z + 1 
      GOTO 100
1000  PRINT ERR, ERL
      END
200   CLS
      PRINT y; "/"; z,
      PRINT y / z; ABS(pi - y / z)
      WRITE #1, y, z
      LOCATE 20, 1
      PRINT z
      a(1, 1) = y
      a(1, 2) = z
      IF x2 = 0 THEN END
      RETURN
10

Something of a WAG: I would imagine that it is influenced by the fact that you are using the compiler’s interpretation of what “pi” actually is. In my C compiler, pi is defined as 3.1415926535897931000000000000000. So if I wrote a C program to do what you did, I would get fractions closer and closer to that value, not the “true” value of pi.

An additional possible: The program starts dealing with very tiny numbers (the differences), which it doesn’t handle well. Computers are not very good at saying if .00000567 is bigger than .00000819.

What I’m saying is this: your results could be the result of your computer’s inherent rounding error and not any intrinsic property of the number pi itself.

And I’m glad that my 100th post is so studious! :cool:

11

It’s good to be careful around computations involving small differences of large numbers, but the result he sees is real. (You’d expect artifacts when the denominators q are about 1/sqrt(EPS), where EPS is the floating-point precision (denominators in the tens of millions) but not much before that.)

Suppose m/n and p/q are consecutive convergents to pi (from its continued-fraction expansion–e.g., m/n=22/7 and p/q=333/106). The convergent errors alternate in sign, so let’s suppose m/n > pi > p/q just to be concrete. Now the errors are e[sub]n[/sub] = m/n - pi and e[sub]q[/sub] = pi - p/q (so we have 0 < e[sub]q[/sub] < e[sub]n[/sub]).

Now think of the PIPFA preceding p/q; these are fractions of the form (p-am)/(q-an) for a=1,2,3,… . Jimby asks when these fractions will be better approximations to pi than m/n: that is, when
e[sub]n[/sub] = m/n - pi > pi - (p-am)/(q-an) = [algebra omitted] = (q e[sub]q[/sub] + an e[sub]n[/sub])/(q-an).
which reduces to
a < (q/2n)(1 - e[sub]q[/sub]/e[sub]n[/sub]).
So when consecutive convergents have very different denominators (q>>n) and the errors aren’t too close (e[sub]q[/sub]/e[sub]n[/sub] << 1) there will be a nontrivial sequence of values (p-am)/(q-an) with smaller approximation errors than m/n. (For the example above, with m/n=22/7 and p/q=333/106, the errors are about 1.3e-3 and 8.3e-5, so this bound is a < (106/(2*7))(1-8e-2) ~ 7.1 and we predict 7 terms between 22/7 and 333/106, just as you found. Similarly this predicts 146 terms in the sequence preceding 103993/33102, as you found.

12

The Stern-Brocot tree method for finding the best rational approximation to any number is the gold standard. You really need to read about it in Knuth, Graham and Patashnik. (Which is why my copy is 4’ away and has a Post-It marking the section.)

http://en.wikipedia.org/wiki/Stern-Brocot_tree

Here’s some info on using it for Pi.

http://qin.laya.com/tech_projects_approxpi.html

13

Unless I’m blind, Quickbasic doesn’t define pi directly. If you look at my program, I defined “pi” as a double length number then as “pi=ATN(1)*4”. It takes pi to equal 3.141592653589793. I double checked this against a value of pi from a 1000 digit precision floating point calculator program I found on the internet. I took a certain amount of care to check for potential rounding errors and the only fractions that have a difference of .000000000000002 from the previous fraction are the last 3. I’ll conceed they may be wrong.

Part of the reason what is printed to the screen is there is to help me see when differences were getting close to the significant digit. But, and trust me on this, by the time I got to the 25 millionth+ cycle of the program, I didn’t quite care enough to check the program on the screen and just opened the results in Excel.

Computers only have a difficulty in telling if very small numbers are greater/less than each other if you are very close to the last significant digit and then they should be double checked by a different method. I could have done this in Mathcad, but I wasn’t writing a math paper, I was trying to boggle the minds of my math illiterate friends. And did it ever.

14

I don’t know if you’re still interested in another answer after nearly five years, but since I found this question through a Google search and noticed you haven’t got the definitive answer yet (or rather, Omphaloskeptic gave it but it may not have been concrete enough with actual numbers): the explanation comes from continued fractions.

Basically, the continued fraction representation of the number is the following: write the number as [an integer] + [fractional part], then write the [fractional part] as the reciprocal of a number, and repeat. So for instance,



3.14159 = 3 + 0.14159 = 3 + 1/7.0625
        = 3 + 1/(7 + 0.0625) = 3 + 1/(7 + 1/15.9966)
        = 3 + 1/(7 + 1/(15 + 0.9966)) = 3 + 1/(7 + 1/(15 + 1/1.0034))
        = 3 + 1/(7 + 1/(15 + 1/(1 + 0.0034))) = 3 + 1/(7 + 1/(15 + 1/(1 + 1/292.6346)))
        = 3 + 1/(7 + 1/(15 + 1/(1 + (1/(292 + ...))))

(I’ve cheated a bit, using the actual value of π at each step instead of 3.14159.)
This representation is called the continued fraction. Since this is unwieldy to write, another notation used is:

π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2…]

Now all the fractions you listed come from the continued fraction, in the following way. Truncate the continued fraction, and replace the final term successively by all numbers from half the final term to the final term itself. Thus, the approximations you get are precisely:



3/1     = [3]

13/4    = [3; 4]
16/5    = [3; 5]
19/6    = [3; 6]
22/7    = [3; 7]

179/57  = [3; 7, 8]
201/64  = [3; 7, 9]
223/71  = [3; 7, 10]
245/78  = [3; 7, 11]
267/85  = [3; 7, 12]
289/92  = [3; 7, 13]
311/99  = [3; 7, 14]
333/106 = [3; 7, 15]

355/113 = [3; 7, 15, 1]

52163/16604  = [3; 7, 15, 1, 146]
52518/16717  = [3; 7, 15, 1, 147]
*… (terms from [3; 7, 15, 1, 148] to [3; 7, 15, 1, 291])...*
103993/33102 = [3; 7, 15, 1, 292]

104348/33215 = [3; 7, 15, 1, 292, 1]
...

etc. So the “island” of 146 fractions you see from 52163/16604 to 103993/33102 is because of the large term 292 in the continued fraction of π, and similarly the “island” of 7 fractions from 179/57 to 333/106 is because of the large term 15, etc.

Using continued fractions is also the best way of finding all these best fractional approximations, immensely faster than looping through all denominators.

Hope this helps (and sorry for bumping up an old thread),

15

For a second I though we had zombie QED. Only a zombie thread though.

16

Yeah, that was kind of scary for a second.

17

Took me a moment to remember who QED was. Thanks a lot, guys. :frowning:

On the bright side, I’m hungry for some pumpkin & vinegar pi. Does that sound irrational? It should! :wink:

18

Transcendental, even. Yum.