Finding Approximate Integer Fraction Representations of Decimal Numbers

A friend of mine had recently started a new podcast. For some reason he knew the percentage of his audience that was Canadian (38%) but had no idea how many people were actually downloading his podcast. He asked me if I could make an estimate of his audience size. Obviously his podcast was quite small and he figured the easiest fraction, 19/50 made his audience far to large. I, working on a short time budget did some quick guess and check and was able to find 5/13, which is .3846. which would round to his desired number, and seemed like a reasonable number of people for a new podcast.

This however wasn’t good enough for me. I figured there must be some way of generating these fractions that didn’t rely on guess and check. Through some short googling I found my solution. The Farey Sequence. This sequence is a list of numbers which includes all of the most reduced integer fractions with denominators equal to or smaller than n. So for example the sequence for n=6 is { 0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1 }. It Also has the excellent property that the value that will go between two values next can be calculated simply. Just add the numerators and the denominators together then reduce the fraction (so for between 1/3 and 1/2 we go 1+1/3+2 to generate 2/5). This makes the algorithm for generating approximations fairly straightforward. Simply take the two fractions, generate the next fraction between them. If the resulting fraction is greater than the target decimal, then it must lie between the lower of the original fraction, and the new fraction (vice versa for if its lesser). Add a check to see if the new fraction is closer to the target decimal than the original fraction, then repeat.

I built a program in C# fairly quickly and it uses what I was lead to believe during my research was the relatively slow Euclidian GCD algorithm (I chose it because it was more intuitive than the Binary GCD algorithm) it was still able to calculate the exact fractional representation of pi (3+36853866/260280919) in 25 microseconds (approximately). Remember that pi is not irrational in the standard .net math library.

Switching to using the Binary GCD algorithm (which wasn’t as scary as I first thought) actually slowed things down, making it take 125 microseconds. So obviously I have some work to do on my algorithm writing.

Oh and the fractions my friend wanted. The best fractional representations are: 1/2 ,1/3, 2/5, 3/8, 5/13, 8/21, 11/29, and 19/50.

You can check out the source code here. Though I don’t recommend it, its pretty scuffed