Approximating Irrationals

Farey Sequence

The Mediant

The mediant is an operation over fractions which takes their sum in the intuitive, but incorrect way.

What I mean by this is instead of taking the sum properly, i.e. by first ensuring a common denominator and then adding together the numerators, you just add both numerators and denominators together: \(m(\frac{a}{b}, \frac{c}{d}) = \frac{a + b}{ c + d}\)

Of course the natural question is who cares, why would you want to do this? And the answer is that the mediant has a very useful property; the value of the mediant is always between the fractions it's operated over: \(\frac{a}{b} < \frac{a + b}{c + d} < \frac{c}{d}, \: where \: \frac{a}{b} < \frac{c}{d}\)

Generating The Sequence

Given this fact we can now generate the Farey sequence, a sequence which generates the set of all rational numbers. First we start our sequence with only two terms, \((\frac{0}{1}, \frac{1}{1})\). Then to generate the rest of the sequence, we take the mediant between all pairs of numbers, and insert it between said pairs. This is done as long as the mediant's denominator is less than or equal to n, where n is the largest denominator we wish to generate.

Farey Sequence up to n=4

\(F_{1} = (\frac{0}{1},\frac{1}{1})\)

\(F_{2} = (\frac{0}{1}, \frac{1}{2},\frac{1}{1})\)

\(F_{3} = (\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1})\)

\(F_{4} = (\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1})\)

Approximating Irrationals

Using the Farey Sequence

Now that we know how to generate the Farey sequence, we can use it approximate any irrational number with a rational number. How is this done you might ask? Quite simply actually, as we can utilize the sorted nature of the sequence.

The first thing we need to do is separate out the decimal places of our irrational number from its whole number. This is done as the decimals are the portion of the number we need to approximate.

Then we need to decide within how many decimal places our approximation must be; as there are an infinite number of rationals, there are an infinite number of approximates.

Now that we've got that all sorted we can start with the actual algorithm. Instead of generating up to the nth Farey order, we're going to selectively generate Farey terms to narrow in on our approximate. More specifically we're going repeatedly generate 3 fractions: \([a, m, b]\), where \(m\) is the mediant of \(a\) and \(b\).

Just like with the normal sequence, \(a\) will start at \(\frac{0}{1}\), and \(b\) will start at \(\frac{1}{1}\). If \(m\) is greater than our irrational's decimals, then we'll let \(b\) equal \(m\). If instead \(m\) is less than our irrational's decimals, then we'll let \(a\) equal \(m\). We'll stop this process when the difference between \(m\) and our irrational's decimals is within our previously determined accepted range. Once we've found our approximate the only thing left is to add our whole number as a fraction to it.

Approximating \(\sqrt{3}\) to two Decimals

Let \(\sqrt{3} = 1 + 0.732050808\)

  1. \([\frac{0}{1}\, \frac{1}{2}, \frac{1}{1}]\)

  2. \([\frac{1}{2}, \frac{2}{3}, \frac{1}{1}]\)

  3. \([\frac{2}{3}, \frac{3}{4}, \frac{1}{1}]\)

  4. \([\frac{2}{3}, \frac{5}{7}, \frac{3}{4}]\)

  5. \([\frac{5}{7}, \frac{8}{11}, \frac{3}{4}]\)
\(\sqrt{3}\approx\ 1 + \frac{8}{11} = \frac{19}{11}\)

Approximation Generator

A programmatic implementation of the described algorithm.


\(\frac{22}{7} = 3.142857142857143\)