Antimatroid, The

thoughts on computer science, electronics, mathematics

Converting a Floating-point Number to a Fraction

with 2 comments

The problem

How do we go about converting a floating point number q to a quotient of natural numbers n, m to a given precision p such that \gcd(n, m) = 1?

There are two ways to go about this, one of which is a subset of the other. We could use the Farey Sequence, but that is limited to mapping floating point values to fractions which fall into the range \lvert q \rvert \in [0, 1] or we can use a Stern-Brocot tree, which allows for values to fall into the range \vert q \rvert \in [0, \infty].

If we think of the Stern-Brocot tree as a list whose composition is determined by iteration, we will want to define the initial list as the domain \frac{0}{1}, \frac{1}{0}. We want to know a value that lies between these two values such that the numerator and denominator are coprime. (So that the tree we construct contains only fractions that are in minimal terms.) The mediant achieves that goal and is defined as \frac{a}{c} < \frac{a + b}{c + d} < \frac{b}{d}. If we insert the mediant between every pair in the list until the last pair is accessed we’ve completed an iteration. If we take this process ad infinitum we get the Stern-Brocot tree. For example:

\displaystyle T_{0} = \{ \frac{0}{1}, \frac{1}{0} \}
\displaystyle T_{1} = \{ \frac{0}{1}, \frac{1}{1}, \frac{1}{0} \}
\displaystyle T_{2} = \{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0} \}
\displaystyle T_{3} = \{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0} \}

It is worth noting that if we had instead started with \frac{0}{1}, \frac{1}{1} that we would instead be operating over the Farey Sequence where every iteration is denoted as \mathfrak{F}_{n}. Arguably, we could have gone with this sequence by inverting all q > 1 and then inverting the resolved fraction- which would have added unnecessary complexity to the end implementation.

The implementation

Using the Stern-Brocot structure, we can implement a simple binary search over the list to map a floating point number to a fraction within a given precision. The following C# implementation illustrates how this can be done but it is not complete nor is it optimized in any way.

public static Fraction toFraction(this double q, int precision) {
    if (double.IsNaN(q))
        return null;
    if (double.IsPositiveInfinity(q))
        return new Fraction(1, 0);
    else if (double.IsNegativeInfinity(q))
        return new Fraction(-1, 0);
    else if (q == 0.0)
        return new Fraction(0, 0);

    bool negative = q < 0;
    double val;

    Fraction L = new Fraction(0, 1);
    Fraction R = new Fraction(1, 0);
    Fraction M = null;

    q = Math.Round(Math.Abs(q), precision);

    do {
        M = Fraction.mediant(L, R);
        val = M.getValue(precision);

        if (val < q)
            L = M;
        else if(val > q)
            R = M;
    } while (val != q);

    return new Fraction(negative ? -1 : 1 * M.N, M.D);
public class Fraction {
       public long N, D;

       public Fraction(long n, long d) {
           N = n; D = d;

       public double value(int precision) {
           return Math.Round(N / (double)D, precision);

       public static Fraction mediant(Fraction l, Fraction r) {
           return new Fraction(l.N + r.N, l.D + r.D);

Written by lewellen

2008-07-27 at 9:30 pm

Posted in Algorithms

Tagged with ,

2 Responses

Subscribe to comments with RSS.

  1. Why were the comments made at the time of the July 2008 posting removed?

    Todd Trimble

    2009-04-26 at 4:55 pm

  2. Hi Todd, the original comments did not add any value my post so I removed them while doing some spring cleaning- the same spring cleaning that must have triggered an auto-pingback to your site. I Apologize for the auto-pingback. I will be removing the reference to your site shortly. Please feel free to delete the auto-pingback on your site.


    2009-04-26 at 5:21 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: