Mediant approximation trick
Suppose you are trying to approximate some number x and you've got it sandwiched between two rational numbers:
a/b < x < c/d.
Now you'd like a better approximation. What would you do?
The obvious approach would be to take the average of a/b and c/d. That's fine, except it could be a fair amount of work if you're doing this in your head.
I recently stumbled across an article [1] that suggested taking the mediant of the two fractions rather than the mean. The mediant of two fractions simply adds the numerators and denominators, the very thing you might have gotten your hand slapped for doing in elementary school. It's not a valid way to add two fractions, but it is a valid way to get a new fraction between two fractions. That is,
a/b < (a + c)/(b + d) < c/d.
So the mediant of a lower bound and an upper bound is going to be a better approximation than either bound.
There are two advantages to using the mediant rather than the mean:
- It's easier to compute mentally.
- It generally results in smaller numerators and denominators.
For example, suppose you know that 19/7 and 87/32 are both approximations to e, with
19/7 < e < 87/32.
Then (19 + 87)/(7 + 32) = 106/39 should be better than either of the previous approximations.
Here's a little Python calculation to illustrate that this is the case.
>>> from math import exp >>> e = exp(1) >>> 19/7 - e -0.003996114173330678 >>> 87/32 - e 0.0004681715409549092 >>> 106/39 - e -0.0003331105103270282
So 106/39 is an order of magnitude more accurate an approximation to e than 19/7 is. The approximation 106/39 is also more accurate than 87/32, though it's not as much an improvement over 87/32 as it was over 19/7.
You might notice that while 87/32 overestimates e, 106/39 underestimates e, and by roughly the same amount. This suggests repeating our process would give an even better approximation. Let's check it out.
The mediant of 87/32 and 106/39 is 193/71.
>>> 193/71 - e 2.8030695884417867e-05
This shows that 193/71 is an order of magnitude better than 106/39 as an approximation to e.
Here's a plot of the last three approximations.
[1] Tom M. Apostol and Mamikon A. Mnatsakanian. Good Rational Approximations to Logarithms. The College Mathematics Journal, May, 2001, Vol. 32, No. 3. pp. 172-179.
The post Mediant approximation trick first appeared on John D. Cook.