Skip to main content

On approximating irrational numbers as fractions (algorithms)

· 7 min read
Kiril Panayotov Blagoev

Rational numbers are easy. They include the integers, with which you can count up and down the number line, as well as fractions - written as the division of two integers or as a finitely-long decimal expansion.

But there aren't that many rational numbers on the real number line, as there are irrationals. These beasts of infinitely-long decimal expansions take the vast majority of the infinity of real numbers. They can't be written as a fraction, and they can't be written exactly as a decimal expansion (it would be infinitely long).

But the irrational numbers are far from being exotic beings or a small curiosity within mathematics. We use them in everyday life. The example that is on everyone's lips is π\pi, but there are many others that are very often used, like ee and 2\sqrt{2} to name a couple.

In order to be able to address these numbers, we've devised names for a few of them, like the above. We can address them, but in calculations we have to use their value. But we can't hope to ever compute the exact values of these numbers, so we use the next best thing - an approximation accurate within an agreed upon error.

Of course the magnitude of the error matters for different scenarios, like for example if you do your physics homework you might be OK with π=3.14\pi=3.14, but that might not be enough for calculating the fundamental physical constants, or how to stabilise your spacecraft. Although, probably in no practical scenario would you agree that π=3.2\pi=3.2.

"OK", you rightfully say - "but what if I need to remember π\pi to 60+ significant digits for writing my own maths library in my favourite programming language? That seems like a pain!" And you would be right (contrived example is contrived). It is a pain, even if people seem to do it for fun. That's where fractional approximations come in. You could remember either 3.1423.142 or 227\frac{22}{7}. Or you could remember  3.1415933.141593 or 355113\frac{355}{113}. As you go up in accuracy, fractions become more and more practical.

So, ideally, you nod in agreement, and start thinking more about it. After a while you might start having doubts whether every irrational can be approximated practically enough by a fraction. After all 3141510000=3.1415\frac{31415}{10000}=3.1415, but that's not particularly easy or practical to use or remember. What if the majority of irrationals can only be approximated like that.

Well, thankfully there exists a theorem by Dirichlet which states that for every irrational number, there exist infinitely many fractions that approximate the number evermore closely. Specifically, the error of each fraction is no more than 1 divided by the square of the denominator. So the fraction 227\frac{22}{7}, for example, approximates π\pi to within 172\frac{1}{7^2}, or 149\frac{1}{49}. Dirichlet proved that there is an infinite number of fractions that draw closer and closer to π\pi as the denominator of the fraction increases.

Fine. But how are we supposed to find these fractions that are so good at approximating a given irrational number? Also, ideally it wouldn't involve the pain that is calculating continued fraction expansions. Well thankfully we have this brilliant collection of theorems and algorithms provided by Jean-Louis Sikorav.

This paper provides us with useful theorems and algorithms for calculating fractional approximations by using the concept of the distance between an irrational number and its nearest integer. It's a very straightforward method, the caveat of which is that we need to a priori have a decent decimal-expanded approximation of the irrational number we're trying to approximate. Which isn't really a problem actually. What we're trying to do is to find a fractional approximation, so supposedly we know what we're trying to approximate.

By providing us with three different algorithms for finding the same thing, the paper allows us to find the best approximation by confirming it with three methods, and the relationship between their best results.

Here we will have a look at the first algorithm, and leave the rest as an exercise for now. This algorithm will give us the Best Rational Approximation of an Irrational Number of the 1-st kind (BRAIN I).

1) Let NN be a strictly positive integer. The following algorithm determine BRAIN I(α,k0)(\alpha,k_0), where k0k_0 is the largest integer such that qk0≤Nq_{k_0} \leq N among the irreducible fractions [qkα]qk\frac{[q_k\alpha]}{q_k} minimizing ∣∣qkα∣∣qk\frac{||q_k\alpha||}{q_k} with 1≤qk≤N1\leq q_k\leq N:

where:

  • [α][\alpha] known as the Gauss square bracket is the nearest integer to α\alpha, which is acquired in Javascript by Math.round().
  • ∣∣α∣∣||\alpha|| is the distance between α\alpha and the nearest integer, such that ∣∣α∣∣=∣α−[α]∣||\alpha|| = |\alpha - [\alpha]|, or Math.abs(Math.round(a) - a).
  • For each integer q,1≤q≤Nq,1\leq q\leq N, compute [qkα][q_k\alpha] and ∣∣qkα∣∣qk\frac{||q_k\alpha||}{q_k} . Sort the NN terms ∣∣qkα∣∣qk\frac{||q_k\alpha||}{q_k}  in ascending order and among the fraction(s) minimizing ∣∣qkα∣∣qk\frac{||q_k\alpha||}{q_k}  , retain the one having the smallest denominator qk0q_{k_0} : BRAIN I$ ( \alpha , k0 ) = \frac{[ q{k0}\alpha ]}{q{k_0}}$. In other words:
function gcd (x, y) {
    if ((typeof x !== 'number') || (typeof y !== 'number')) 
        return false;
    x = Math.abs(x);
    y = Math.abs(y);
    while (y) {
        const t = y;
        y = x % y;
        x = t;
    }
    return x;
}

const qs = []
for (let i = 1; i <= 1000; i++) {
    qs.push(i)
}
const table = []

for (const q of qs) {
    const obj = {}
    obj.q = q
    obj.gaussQPi = Math.round(q * Math.PI)
    obj.distQPiOverQ = Math.abs(q * Math.PI - obj.gaussQPi) / q
    obj.gcd = gcd(obj.gaussQPi, q)
    obj.enumerator = obj.gaussQPi / obj.gcd
    obj.denominator = q / obj.gcd
    table.push(obj)
}
    
table.sort((a, b) => a.distQPiOverQ - b.distQPiOverQ)

The determination of ∣∣Nα∣∣N\frac{||N\alpha||}{N} requires the knowledge of an approximation of α\alpha with an accuracy of about 1N\frac{1}{N} , and therefore with a number of digits proportional to log⁡N\log N. This in turn implies that computation of the product NαN\alpha grows with the square of log⁡N\log N and that the time needed to run the complete algorithm is proportional to N(log⁡N)2N(\log N)^2 . Indeed, in order to use this algorithm, we need to already know our irrational number to a satisfactory level of accuracy. For this experiment we used the Math.PI value in Javascript, which is more than accurate enough for our purposes. In fact, we would get the same answers for the value of 3.1423.142. Here are the top 10 results we get, sorted in descending accuracy. The fractions are reduced to their irreducible versions.

q[q𝛼]||q𝛼||/qfraction
56517752.66764e-7355 / 113
1133552.66764e-7355 / 113
2267102.66764e-7355 / 113
45214202.66764e-7355 / 113
90428402.66764e-7355 / 113
79124852.66764e-7355 / 113
33910652.66764e-7355 / 113
67821302.66764e-7355 / 113
89728189.59896e-62818 / 897
91128629.98088e-62862 / 911

And indeed, the most accurate fraction of 355/113355/113 is well a known relatively accurate approximation of π\pi such that π≈3.14159292...\pi \approx \boldsymbol{3.141592}92....

This is a very elegant and simple way to find a fractional approximation given an irrational number. The remaining two algorithms are very similar, such that they use the same variables, but treat them differently. The concept is the same, so I will leave them for now, and you can check them out in the above mentioned paper, which you can find here.