Skip to content
May 23, 2009 / cdsmith

Approximations of Pi (and other numbers) as Fractions

A discussion with a friend and his daughter this morning led me to remember an intriguing function from the Haskell standard library – approxRational.  We were talking about his daughter learning in school that pi is (according to her class notes; it’s quite likely that the teacher was actually more correct) “3.14, or 22/7″.  Even the 11-year-old among us knew that something was wrong; her calculator told her that 22/7 was not exactly 3.14.  They are both approximations, of course, which was easy to explain.  But then she wanted to know why we choose those particular approximations.  And that was an interesting question.

With decimal numbers, of course, you just pick a number of digits and round it off.  Sure, this depends on the base used to represent the number, and that’s ugly… but it’s called the decimal system for a reason.  With fractions, the situation is less clear.  Why would you want to remember 22/7?  There’s a whole host of other possibilities: for instance, 3/1, or 7/2, or 16/5, or 311/99, or 355/113.  (That last one, as we’ll see later, is a particularly good choice.)  Some of those fractions are easier to remember than 22/7.  Others are closer to pi than 22/7.

We’ve got two competing values here:

  1. We want the result to be easy to remember.  If we seek a result (as I do) that’s not somewhat arbitrary (note that using base 10 itself is arbitrary, and therefore so are criteria like wanting round numbers, or numbers whose digits form patterns) then the only good interpretation of “easy to remember” is “using small numbers”.
  2. We also want a number that’s close to pi.

Clearly, we’re looking for some kind of a balance here.  Well, Haskell’s approxRational function to the rescue.  The documentation for this function says:

approxRational, applied to two real fractional numbers x and epsilon, returns the simplest rational number within epsilon of x. A rational number y is said to be simpler than another y' if

  • abs (numerator y) <= abs (numerator y'), and
  • denominator y <= denominator y'.

Any real interval contains a unique simplest rational; in particular, note that 0/1 is the simplest rational of all.

The claim that any real interval contains a unique simplest rational is an interesting one.  Simplicity, as defined here, is a partial order.  That is, 1/2 is simpler than 2/3, which is in turn simpler than 3/4.  But if one asks which of 2/3 or 3/2 is simpler, there is no answer.  Those numbers are incomparable with respect to the simplicity order; neither is simpler than the other.  In general, with a partial order, there may be any number of minimal elements in a given set; possibly none at all, or possibly infinitely many.  The claim here is that with this particular partial order of simplicity, and this particular set being an interval of real number, there is precisely one.

This turns out to be not terribly hard to prove.  Suppose you have two rational numbers a/b and c/d. Then let e=min(a,c) and f=min(b,d).  It’s not hard to see that e/f is at least as simple as either a/b or c/d (this by definition, basically; if e/f can be reduced, the result is more simple, not less), and also that it falls between a/b and c/d so that it must be in any interval that contains them.  It’s not necessarily the simplest rational in the interval, but it proves that no two rational numbers can both be minimally simple over an interval than contains both of them.

This also provides a pretty powerful tool in answering our question.  If we decide in advance how much inaccuracy we’re willing to accept in our approximation, then there is a unique approximation that’s easiest to remember, and approxRational will tell us what it is.  This immediately eliminates some possible approximations.  For example, you should never approximate pi as 7/2, because 3 is both easier to remember, and closer to pi.  By considering ever smaller intervals and using approxRational, one can obtain a sequence of approximations that are simplest for some amount of allowable inaccuracy.

Prelude Data.Ratio> map (approxRational pi) [0.5^k | k <- [1..6] ]
[3%1,3%1,13%4,16%5,19%6,22%7]

Up to a certain level of accuracy, the best approximations appear to be 3, 13/4, 16/5, 19/6, 22/7, or 201/64.   But ah, how to choose.  One clue is afforded by the fact that the number 3 appears twice in the list.  In fact, if we extended the list further, we’d discover that 22/7 appears 3 times!  If a number is simple enough to beat out other approximations for somewhat large intervals, but also good enough to keep winning for very small intervals, then this bodes well for its being a good general-purpose choice.  It’s a decent measure of the efficiency of the number.  Let’s get some more precision in the choice of intervals, and then count up the number of occurrences:

Prelude Data.Ratio Data.List Control.Arrow Data.Function> take 10 $ reverse $ sortBy (compare `on` fst) $ map (length &&& head) $ group $ map (approxRational pi) [0.99^k | k <- [1..10000] ]
[(6414,884279719003555%281474976710656),(572,355%113),(297,22%7),(288,5419351%1725033),(194,3%1),(168,1146408%364913),(143,312689%99532),(120,833719%265381),(110,80143857%25510582),(109,165707065%52746197)]

I did the same sort of thing, but considered many more values for epsilon, then grouped recurring elements of the list, measured their lengths, and sorted on them.  Initially, the best approximation seems to be quite ugly:884279719003555/281474976710656.  That’s an illusion, though.  Because pi is itself a floating point constant in Haskell, it is actually equal to a rational number, and that’s the one.  So it’s occurrence at the top of the list means only that we’ve looked as far as we can.  The remaining answers are true approximations.  22/7 does indeed fair pretty well, though it’s narrowly edged out by 355/113, which is an even more efficient (in fact, to get closer to pi than 355/113, you have to go all the way to 52518/16717!

The lesson?  Who knows?  22/7 is a pretty decent choice for teaching 11-year-olds about fractions that are close to pi.  355/113 would be better, if you think they can remember numbers that big.  And approxRational is fun.

Exercise for the interested reader: implement an inverse to approxRational.  That is, given a rational number, can you determine the adjacent simpler rationals?  If so, you could work backwards: take the most precise possible rational approximation of pi that fits in a Double, and then determine how far you have to move away to get a simpler rational that approximates it.  (Hint: there are only finitely many rationals simpler than a given rational.  You shouldn’t consider them all, but if you think about what it would look like to list them, you can find a decent search strategy.)

About these ads

23 Comments

Leave a Comment
  1. Thomas Danecker / May 23 2009 4:47 pm

    I thought the reverse would be to find a simple irrational approximation to a rational number :)

  2. BMeph / May 23 2009 4:49 pm

    Those results are part of what make continued fractions so much fun – the continued fractions for numbers, when stopped after a certain point in the sequence and evaluated as regular fractions form what are called convergents for those numbers. The interesting part, though, is that those convergents are the simplest representations of those numbers, using those denominators.

    Even better: say your convergent of choice is p/q. Then p/q is within 1/q^2 of your original number.

    Anyway, the series for pi’s continued fraction starts [3, 7, 15, 1, 292, 1, 1, 1, 2,...], and the first four convergents are then 3, (3+1/7) or 22/7, (3+1/(7+1/15)), or 333/106, and (3+1/(7+1/(15+1/1))), which is the pleasantly-almost-symmetrical 335/113. In case you’re curious, the fifth convergent works out to 103993/33102 – obviously, the bigger the number in the sequence, the bigger the size of the next denominator will be. There are lots of other interesting odd facts about continued fractions (such as the numbers that are solutions to quadratic equations work out to have continued fraction sequences that repeat after a while – and vice versa), with the stuff about convergents being just the tip of the iceberg.

  3. Thomas Danecker / May 23 2009 6:02 pm

    The most interesting continued fraction is the one of Phi. As you can see, there’s no such approximation like 22/7 that lasts for a bigger range of epsilon. Phi is the single irrational number that is worst to be approximated by rational numbers.

  4. Thomas Danecker / May 23 2009 6:03 pm

    The most interesting continued fraction is the one of Phi [1]. As you can see, there’s no such approximation like 22/7 that lasts for a bigger range of epsilon. Phi is the single irrational number that is worst to be approximated by rational numbers.

    [1] http://en.wikipedia.org/wiki/Golden_ratio

  5. Jade NB / May 23 2009 6:22 pm

    @Thomas: It’s not quite clear what you mean. Obviously, for example, φ and 1 + φ are equally well approximated by rationals, so φ is not unique in this respect. An obvious remedy would be to say that the Q-coset of φ consists of the ‘worst-approximable’ irrational numbers, but I’m not sure what you mean by that: it is an amusing fact that, if you discard the trivial approximation, rationals are worst approximated by rationals, in the sense of the denominator of the approximant remaining small as the distance to the approximated number becomes small.

  6. Thomas Danecker / May 24 2009 4:49 am

    If you use approxRational to approximate φ and constantly cut epsilon into halves (starting with 0.5), you’ll see that no single approximation stays the best for more then two intervals. When you do the same with e.g. pi or e, you’ll get some better approximations sometimes. E.g. for pi, 355/113 stays the best for eight intervals, 22/7 for four, …

    Unfortunatly the floating-point representation of those irrational numbers doesn’t have that many digits, so the result isn’t that representative.

    PS: the choice of 0.5^k isn’t arbitrary; it represents the number of matching bits that is constantyl increased by one.

  7. Daelin the Cruel / May 24 2009 4:48 pm

    If you’re having problems with pi being a floating-point number, you could write a function that calculates pi from scratch using rationals, all the way down to the desired precision, and then call approxRational on that.

  8. Asokan / May 24 2009 11:17 pm

    Actually 355/113 _is_ easy to remember:
    Step 1: Write down the first three odd numbers->135
    Step 2: repeat each number->113355
    Step 3: Put a long division bracket in the middle->113)355

    Of course the idea is OLD. IIRC, I read it in Rouse Ball’s classic Recreational Mathematics book

  9. Gruul / Nov 17 2009 10:15 am

    Another easy one to remember is 666/212 = 3.1415WRONGDECIMALS

  10. sfrgfr / Apr 21 2010 9:16 pm

    what i don’t get it i feel so dumb

  11. John / Sep 7 2010 12:09 am

    Hi, I implemented this in Factor, if you’d like to see what it looks like in another language:

    http://re-factor.blogspot.com/2010/09/approximating-rationals.html

  12. Mark Ransom / Oct 17 2010 8:10 am

    Just for fun I wrote a program to find the closest fraction to a decimal number. I decided to test it using pi. While searching the web for data to verify my own results, I came across your page.

    You make the statement “to get closer to pi than 355/113, you have to go all the way to 52518/16717″ but I found that not to be true – 52163/16604 is (barely) closer than 355/113.

  13. Рајко Велимировић / Jul 19 2011 7:10 am

    I found a new formula for the number of PI
    PI=180*m*sin(1/m)
    sin in degrees
    for m=10 :PI=3.14159
    for m=100:PI= 3.1415926
    for m=1000 :PI=3.141592653
    for m=10 000 :PI=3.14159265358
    for m=100 000 :PI=3.1415926535897
    for m=1000 000 :PI=3.141592653589793
    for m=10000000:PI= 3.14159265358979323
    for m=100000000 :PI=3.1415926535897932384
    for m=1000000000:PI= 3.141592653589793238462
    For millions across the value of PI free calculator XP,XM,….. recommend m=1.0E+10000000
    to the success of the calculator you need to install netframework2.0
    http://harry-j-smith-memorial.com/index.html
    Рајко Велимировић

  14. Рајко Велимировић / Apr 18 2012 10:08 am

    PI = 360 * m * sin (1 /2 m)

    sin in degrees
    see the proof

    http:// en.wikipedia.org/wiki/User:Рајко_Велимировић

    for :m=1

    PI=3.1415

    for:m=10

    PI=3.141592

    for:m=100

    PI=3.1415926

    for:m=1000

    PI=3.1415926535

    for:m=10000

    PI=3.141592653589

    for:m=100000

    PI=3.1415926535897

    involving millions get through to calculators XP,XM………. http://harry-j-smith-memorial.com/index.html recommendation m=1.0E+10000000

  15. Kenneth Mollohan / May 30 2012 1:00 am

    You have lots of requests for fractional approximations for Pi. Try this: (Correct to 9 decimals, and easy to memorize): (3*1109377/1059377)=3.14159265304042
    Kenneth Mollohan

  16. Mardeg / May 6 2013 11:43 am

    7^7/4^9 is accurate to 4 decimal places, though hard to say if it’s more memorable than 355/113

    5^(4333/6092) and (2143/22)^(1/4) are accurate to 7 and 8 decimal places respectively, more accurate than 355/113 but definitely NOT easier to remember.

  17. Justin / Nov 21 2013 6:37 pm

    Cool! In fact, 52163/16604 gets closer to pi than 355/113. I found a scary approximation:

    2595730897165797211593340467841630035030853330521178267351313167 / 826246806440593758242827735111030202858868304763792133731752324

    Don’t ask me how accurate it is! I only know there is no smaller fraction with more accuracy.

  18. Justin / Nov 21 2013 6:46 pm

    Even more, this is an AMAZING fraction with 258 digits correct!!!

    11470607307161132716588859789437271840000798468219508525085448960062402821241970285202775001996784319885772780138414238670402064758
    /
    3651207706401417758577438077383177726074790491037819709434096621864877255825019944180015629313589782838738505101104441533461516175

  19. Justin / Nov 21 2013 6:49 pm

    If anyone likes Phi, it can easily be approximated by the ratio of successive Fibonacci numbers.

  20. Justin / Dec 3 2013 4:54 pm

    And if you want all this, use 3 + 1 / (7 + 1 / (15 + 1 / (1 + 1 / (292 + 1 / (1…..)))))

    These give approximations like 3,22/7,333/106,355/113,103993/33102,104348/33215,208341/66317…….

    22/7′s difference from pi is less than the reciprocal of its denominator times the next fraction’s denominator (i.e. 7*106=742), or 1 / 742. For 355 / 113, 1 / (113 * 33102) = 1 / 3740526!

  21. Justin / Dec 3 2013 4:55 pm

    This is my original code:

    ““
    from math import pi
    from time import time
    x=1
    difference=pi-3
    D=pi-3
    Time=time()

    while D!=0:
    y=round(pi*x)
    D=abs(pi-float(y)/x)
    if D<difference or x==1:
    difference=D
    print str(y)+'/'+str(x)+'='+str(float(y)/x)+'. It is '+str(D)+' away from pi! Time spent: '+str(time()-Time)+' seconds, precisely.'
    if D==0: break
    Time=time()
    x+=1
    “`

    It times the amount of time to take each approximation and only gives the best ones.

Trackbacks

  1. popurls.com // popular today

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 62 other followers

%d bloggers like this: