Mediant approximation trick

本文主要是介绍Mediant approximation trick，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

近似值的一个取值技巧

如果知道一个数值变量的上限和下限，那么有一种快速的方法，快速获取该变量更准确的近似值。

比如，已知变量e的大小范围是19/7 < e < 87/32，就可以快速得到它的近似值。

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 - e0.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 - e2.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.

好图

Mentally computing mathematical functions
Mentally calculating day of the week in 2023

[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.

这篇关于Mediant approximation trick的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！