# Using continued fractions to generate rational approximations

A redditor asks:

How would I find a good rational approximation to something like $\log_{10}(7)$?

The Mathematical Ninja mutters 0.85 under his breath, as a matter of course, reasoning that $\log_{10}(7) \approx \log_{10}\left(\sqrt{ \frac {10^2 }{2} } \right)$, although my calculator says 0.845098, so he’s off by about 0.6%.

However, that’s not the question. The question is, how to come up with a good rational approximation, and the answer is to use *continued fractions*

The steps are to generate a series of numbers and turn it into a fraction. $\log_{10}(7) = 0.845098…$

- The first digit is 0, which you take away; divide 1 by what’s left over to get 1.18329…
- The first digit of this is 1, which you take away (0.183…) and divide 1 by what’s left over to get 5.4556…
- The first digit of this is 5, which you take away to get (0.455…) and… (you get the drift)

The sequence you end up with is [0; 1, 5, 2, 5, 6, 1, 4813…]. (That last number I worked out is comparatively huge, which means – even though the sequence goes on for ever, there’s a good rational approximation!)

What does this all have to do with fractions? Well, the continued fraction expression of $\log_{10}(7)$ is written as $0 + \frac{1}{1 + \frac{1}{5 + \frac{1}{2 + \frac{1}{ 5 + \frac{1}{ 6 + \frac{1}{ 1 + \frac{1}{ 4813 + …}}}}}}}$

Working out the convergents – the fractions you get as you truncate the sequence – you get:

- $0$ (rubbish approximation)
- $0 + \frac{1}{1} = 1$ (somewhat better)
- $0 + \frac{1}{1 + \frac{1}{5}} = \frac{5}{6}$ or 0.833… (much better)
- $0 + \frac{1}{1 + \frac{1}{5 + \frac{1}{2}}} = \frac{11}{13}$ or 0.846… (pretty decent)
- $0 + \frac{1}{1 + \frac{1}{5 + \frac{1}{2+ \frac{1}{5}}}} = \frac{60}{71}$ or 0.84507… (good)
- $0+ \frac{1}{1 + \frac{1}{5 + \frac{1}{2+\frac{1}{5 + \frac{1}{6}}}}} = \frac{371}{439}$ or 0.84510
- $0 + \frac{1}{1 + \frac{1}{5 + \frac{1}{2+\frac{1}{5 + \frac{1}{6 + \frac{1}{1}}}}}} = \frac{431}{510}$ or 0.845098 (correct to one part in a trillion)
- $0 + \frac{1}{1 + \frac{1}{5 + \frac{1}{2+\frac{1}{5 + \frac{1}{6 + \frac{1}{1+\frac{1}{4813}}}}}}} = \frac{2074774}{2455069}$ (a lot of work for an answer only marginally better).

So, depending on how accurate you need your logarithm, you can go for either $\frac{60}{71}$ (which is good enough for government work) or $\frac{431}{510}$, which is extremely accurate.

* Edited 2015-08-24 to fix a LaTeX error