Method or algorithm for finding rational approximation to real

Question

I'm looking for an method for finding a small rational number within some specified tolerance of a given number, possibly real.

By way of illustration, a solution to the problem of finding a rational approximation to $\pi$, accurate to within $0.001$, is $\frac{201}{64}$. Similarly, $\frac{82}{45}$ is a solution to finding a rational approximation of $\sqrt{2}^\sqrt{3}$, accurate to within $\frac{1}{2048}$.

The Mathematica software provides a function Rationalize[] which gives solutions to similar problems, but I'm looking for an explanation, or even more usefully, a published description, of a suitable algorithm.

Answer 1

Yes, this is indeed all about continued fractions.

A good place to start is indeed https://en.wikipedia.org/wiki/Continued_fraction

But it is useful to have an illustration so as to get an idea of the principle behind it all. Let’s look for approximations to π

π = 3 + 0.141592653589793

so, approximating that number: 0.141592653589793 = 1/ 7.062513305931046

7.062513305931046 = 7 + 0.062513305931046

so, approximating that number: 0.062513305931046 = 1/ 15.99659440668572

Unwinding that calculation with decimals:

• 16
• Invert = 0.0625
• Add 7 = 7.0625
• Invert = 0.141592920353982
• Add 3 = 3.141592920353982

…which is a pretty good approximation.

Unwinding again, but this time with fractions:

• 16
• Invert = 1/16
• Add 7 = 113/16
• Invert = 16/113
• Add 3 = 355/113

…and 355/113 is indeed the “best possible” approximation with numerator and denominator of that sort of size. Similarly if you stopped the calculation one step earlier you’d get 22/7, which is “best possible” of that size. And one step earlier is 3/1, again best possible.

With more ingenuity you can construct the approximating fractions as you go along, rather than (as I did) first going forwards and then constructing the fractions by going backwards.