Antimatroid, The

thoughts on computer science, electronics, mathematics

Archive for July 2008

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);
       }
}
Advertisements

Written by lewellen

2008-07-27 at 9:30 pm

Posted in Algorithms

Tagged with ,

Automated inheritance refactoring

leave a comment »

Over time, we all gain experience and insight in deciding how to generalize the principle actors of our problem domains into different layers of abstraction to minimize the amount of code we write. After awhile, this practice becomes tedious and one begins to wonder whether or not it is feasible to have an integrated refactoring (in our IDE of choice) that will review our class inheritance hierarchy and suggest to us an idealized class inheritance hierarchy. After all, an optimal solution would be able to identify relationships that our minds would otherwise not be able to fathom- as is the case as our code bases and development costs increase.

What we’re really interested in is an automated version of Extract Superclass that takes in a collection of classes and returns some number of superclasses. Thing is, we are back to our original problem where we have a collection of classes that we want to generalize. If we continue this process as a feedback loop we end up eventually with an irreducible collection of classes. The original collection along with the rest of the generated collections constitute the idealized class inheritance hierarchy.

During the mid-nineties this topic was the subject of a handful of masters and doctorate programs but since then, there seems to be a significant gap in the flow of academic material on the subject. Furthermore, there seems to be little recent evidence from industry to indicate work being done on a solution. Is such a solution simply not needed? Are the outputs of solutions impractical? What is the blocking element to adoption? The only evidence of this idea getting any momentum is given by Guru– a solution targeted at the Self programming language. Where are the solutions for C++, Java, C# et al.?

Written by lewellen

2008-07-20 at 8:00 pm

Posted in Software Engineering

Tagged with

One tree, many possibilities: Part 2

with one comment

Implementation

In my previous post, I wrote about how to construct a rule based tree that allows one to generate the outputs of a number of counting functions. In this installment, I am providing the corresponding implementation in C#. All five functions rely on the basic tree definition of T_{n}(S, \sigma) which is treated as a kernel function in the implementation.

private List<List<T>> kernel<T>(List<T> S, Func<List<T>, int, List<T>> sigma, int N) {
    return kernel<T>(S, sigma, N, new List<T>());
}

private List<List<T>> kernel<T>(List<T> S, Func<List<T>, int, List<T>> sigma, int N, List<T> u) {
    List<List<T>> R = new List<List<T>>(new List<T>[] { u });
    if (N <= 0)
        return R;

    for (int n = 0; n < S.Count; n++) {
        List<T> v = new List<T>(u);
        v.Add(S[n]);
        R.AddRange(kernel<T>(sigma(S, n), sigma, N - 1, v));
    }

    return R;
}

Apart from the kernel, we still need a couple surjective functions to implement the remaining functions. As discussed in the previous post, we need two functions, one that returns all elements of a list except for a specified index, and one that returns all elements of a list greater than a specified index.

private List<T> notEqual<T>(List<T> S, int n) {
    return new List<T>(S.Where((x, m) => m != n));
}

private List<T> greaterThan<T>(List<T> S, int n) {
    return new List<T>(S.Where((x, m) => m > n));
}

The remaining implementations of the n-ary Cartesian Product, Permutation, k-Permutation, Power Set and n-Combination are now rather trivial.

public List<List<T>> nAryCartesianProduct<T>(List<T> S, int n) {
    List<List<T>> R = kernel<T>(S, (x, y) => x, n);
    R.RemoveAll((x) => x.Count < n);
    return R;
}

public List<List<T>> permutation<T>(List<T> S) {
    return kPermutation<T>(S, S.Count);
}

public List<List<T>> kPermutation<T>(List<T> S, int k) {
    List<List<T>> R = kernel<T>(S, notEqual, k);
    R.RemoveAll((x) => x.Count != k);
    return R;
}

public List<List<T>> powerset<T>(List<T> S) {
    return kernel<T>(S, greaterThan, S.Count);
}

public List<List<T>> nCombination<T>(List<T> S, int n) {
    List<List<T>> R = kernel<T>(S, greaterThan, n);
    R.RemoveAll((x) => x.Count != k);
    return R;
}

Written by lewellen

2008-07-06 at 7:50 pm