Mediant | Hacker News Reader

Mediant

johndcook.com

55 pointsggeorgovassilis23 comments

Open articleView on HN

Watch out for negative numbers

The mediant inequation is: a/b < (a+c)/(b+d) < c/d

If a=1, b=2, c=-1, d=-1

1/2 < 0/1 < -1/-1

1/2 < 0 is obviously wrong

If you remove negative signs in the denominators by multiplying by -1/-1, it works

1/2 < 2/3 < 1

> The mediant inequation is: a/b < (a+c)/(b+d) < c/d

The equality is more fun & shows up frequently on the Nationals. It states:

a/b = c/d => a/b = c/d = (a+c)/(b+d)

For example - On the AIME 2023 this Tuesday (Feb 7), Problem 12 was literally this equality. (see solution 2 below) https://artofproblemsolving.com/wiki/index.php/2023_AIME_I_P...

How does it follow that the mediant (a+c)/(b+d) is a better approximation than both a/b and c/d? One of the bounds could be very close to the quantity you are trying to approximate already.

Looking at the comments, you can iterate this, and eventually you will get a better approximation than both a/b and c/d. But sure enough, after a single iteration, (a+c)/(b+d) is not always better.

If you iterate this, I think you get the continued fraction convergents, which are the "best" rational approximation to the irrational you're trying to approximate. (I did some numerical experiments and this looks true; I didn't prove it.)

I found the thing about iteration quite strange.

To iterate, we need to know if our mediant is larger or smaller than the true value.

How do we know that?

Edit: elsewhere in the thread someone explained that the purpose of iterating is to find an approximation with small denominator.

e isn't the best example for this, because you would need a good decimal expansion. But say we're trying to approximate sqrt(2) by this method. Say we've already established that it's in the interval [7/5, 10/7]. We can verify because 7^2 < 2*5^2 and 10^2 > 2*7^2. Then the mediant is 17/12, and since 17^2 = 289 > 288 = 2*12^2, we know 17/12 > sqrt(2). So [7/5, 17/12] is a smaller interval containing sqrt(2). Repeating this, [24/17, 17/12] is even better, and so on.

That was also a (up to now) unanswered question a reader posted.

It doesn't. Neither is the average.

To say such a thing, we need:

1. Some assumption about the distribution of the true value. 2. And a metric measuring the "cost" of being wrong.

Assuming a uniform distribution, and measuring cost as the expected absolute value of the error, we find that the average of the interval is the best guess.

Using the same assumptions, any number in the interval is a better estimate than the endpoints.

From that it (obviously) follows that the mediant is a better approximation than both endpoints.

The average of the interval is the best guess if you are only trying to minimize the error. But if you want to also keep the denominator small that's when the problem gets more interesting.

Maybe it's better to formalize this in terms of having a rational interval as the approximation of an irrational - for example the interval [19/7, 87/32] approximates e. That's an interval of width 1/224. Then if [a/b, c/d] contains the irrational number x, then: - either [a/b, (a+c)/(b+d)] or [(a+c)/(b+d), b/d] contains x, and - whichever one contains x is smaller than the original. Written that way it's trivial, though. The real meat, I suppose, is that using the mediant keeps the numerators and denominators small.

In this case, [106/39, 87/32] has width 1/1248 and contains e, whereas using the mean would give you the interval [1217/448, 87/32] of width 1/448.

Went on a tangent on Wikipedia and found this:

> assume that the pair of reduced fractions a/c < b/d has the property that the reduced fraction with smallest denominator lying in the interval (a/c, b/d) is equal to the mediant of the two fractions. Then the determinant relation bc − ad = 1 holds.

Okay sounds reasonable...

> This fact may be deduced e.g. with the help of Pick's theorem

Wait what?

if you want to keep having your mind blown follow the "Pick's theorem" tangent - apparently there are lots of proofs.

This does not make an awful lot of sense. I have 1/2 and 3/4. The mediant is 4/6 which is 2/3. Okay. Now I have 1/2 and 6/8. Actually, these are the same numbers, it is just a different representation of 3/4. Now the mediant is 7/10..... Uhm.....

Author is demonstrating a kind of binary search. Of course, binary search requires a target value, something to search, so your toy problem is underspecified.

Then your next interval would be (1/2, 2/3) or (2/3, 3/4) depending on whether s > 2/3 or s < 2/3, where s is your search term.

This is completely irrelevant.

TIL: the mediant of two fractions

a/b < (a+c)/(b+d) < c/d

Easy to prove too.

Just found the proof, that's also how I noticed it doesn't work when one of the denominators is negative.

If one of the denominators (not both) is negative, you are guaranteed to be outside of the range.

There are pathological cases where this can converge very slowly. If the denominators are very different, the new "midpoint" is very close to one of the previous bounds. For example, estimating 0.5000000000001 this way takes a ton of iterations.

I found a potential optimization though. If you find that you're repeatedly adjusting the upper/lower bound, you can start adding increasing multiples. It's a provisional step, dependent on the result still being on the same side of the target.

The same author wrote another very useful post in 2010 that also involved mediants:

https://www.johndcook.com/blog/2010/10/20/best-rational-appr...

Is there an efficient method of iterating this so that it converges to the mean? I can think of ways that would include storing the previous iterations...

It's not given that it will converge. Feels like it should, but still needs to be proven.

Reply on news.ycombinator.com