4 ms·
Sure, using a denominator of 10^n gives 1/10^n precision, which is pretty good. And this is fine for applications! However, defining goodness in terms of absolu
by mauricioc 7y ago
Sure, using a denominator of 10^n gives 1/10^n precision, which is pretty good. And this is fine for applications! However, defining goodness in terms of absolute error makes the resulting problem of "how good an approximation can we get?" become trivial, because the answer is "arbitrarily good, always".
A different measure of goodness takes into consideration not only the distance between the real number and its rational approximation, but how big the denominator of the approximation is. Note that, in the scheme you describe, a denominator of q guarantees an error of 1/q. But if you are allowed to choose both the numerator and the denominator of the rational approximation, then perhaps you can make the denominator smaller?
It turns out you can! Dirichlet showed that for every irrational alpha there are infinitely many "good approximations" of the form p/q where |alpha - p/q| < 1/q^2. It turns out the golden ratio shows that you can't do better than 1/(sqrt(5) * q^2) if you want the result to hold for every irrational number. This leads to the problem of identifying "interesting" sets of irrational numbers that allow approximations substantially better than Dirichlet's bound (this is the problem of Diophantine approximation [0]). Klaus Roth got his Fields Medal primarily for a result in this area [1].
[0] https://en.wikipedia.org/wiki/Diophantine_approximation https://en.wikipedia.org/wiki/Diophantine_approximation
[1] https://en.wikipedia.org/wiki/Roth%27s_theorem https://en.wikipedia.org/wiki/Roth%27s_theorem