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:
- 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”.
- 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.)
