Converting a Floating-point Number to a Fraction

The problem

How do we go about converting a floating point number to a quotient of natural numbers to a given precision such that ?

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 or we can use a Stern-Brocot tree, which allows for values to fall into the range .

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 . 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 . 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:

It is worth noting that if we had instead started with that we would instead be operating over the Farey Sequence where every iteration is denoted as . Arguably, we could have gone with this sequence by inverting all 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);
       }
}

Advertisements