Convert percentage to nearest fraction

Question

We have a very data intensive system. It stores raw data, then computes percentages based on the number of correct responses / total trials.

Recently we have had customers who want to import old data into our system.

I need a way to covert a percentage to the nearest fraction.

Examples.

1. 33% needs to give me 2/6. EVEN though 1/3 is .33333333
2. 67% needs to give me 4/6. EVEN though 4/6 is .6666667

I realize I could just compute that to be 67/100, but that means i'd have to add 100 data points to the system when 6 would suffice.

Does anyone have any ideas?

EDIT Denominator could be anything. They are giving me a raw, rounded percentage and i'm trying to get as close to it with RAW data as possible

Answer 1

Your requirements are contradicting: On the one hand, you want to "convert a percentage to the nearest fraction" (*), but on the other hand, you want fractions with small(est) numbers. You need to find some compromise when/how to drop precision in favor of smaller numbers. Your problem as it stands is not solvable.

(*) The nearest fraction f for any given (integer) percentage n is n/100. Per definition.

Answer 2

I have tried to satisfy your requirement by using continued fractions. By limiting the depth to three I got a reasonable approximation.

I failed to come up with an iterative (or recursive) approach in resonable time. Nevertheless I have cleaned it up a little. (I know that 3 letter variable names are not good but I can't think of good names for them :-/ )

The code gives you the best rational approximation within the specified tolerance it can find. The resulting fraction is reduced and is the best approximation among all fractions with the same or lower denominator.

public partial class Form1 : Form
{
    Random rand = new Random();

    public Form1()
    {
        InitializeComponent();
    }

    private void button1_Click(object sender, EventArgs e)
    {
        for (int i = 0; i < 10; i++)
        {
            double value = rand.NextDouble();
            var fraction = getFraction(value);
            var numerator = fraction.Key;
            var denominator = fraction.Value;

            System.Console.WriteLine(string.Format("Value {0:0.0000} approximated by {1}/{2} = {3:0.0000}", value, numerator, denominator, (double)numerator / denominator));
        }
        /*
            Output:
            Value 0,4691 approximated by 8/17 = 0,4706
            Value 0,0740 approximated by 1/14 = 0,0714
            Value 0,7690 approximated by 3/4 = 0,7500
            Value 0,7450 approximated by 3/4 = 0,7500
            Value 0,3748 approximated by 3/8 = 0,3750
            Value 0,7324 approximated by 3/4 = 0,7500
            Value 0,5975 approximated by 3/5 = 0,6000
            Value 0,7544 approximated by 3/4 = 0,7500
            Value 0,7212 approximated by 5/7 = 0,7143
            Value 0,0469 approximated by 1/21 = 0,0476
            Value 0,2755 approximated by 2/7 = 0,2857
            Value 0,8763 approximated by 7/8 = 0,8750
            Value 0,8255 approximated by 5/6 = 0,8333
            Value 0,6170 approximated by 3/5 = 0,6000
            Value 0,3692 approximated by 3/8 = 0,3750
            Value 0,8057 approximated by 4/5 = 0,8000
            Value 0,3928 approximated by 2/5 = 0,4000
            Value 0,0235 approximated by 1/43 = 0,0233
            Value 0,8528 approximated by 6/7 = 0,8571
            Value 0,4536 approximated by 5/11 = 0,4545
         */
    }

    private KeyValuePair<int, int> getFraction(double value, double tolerance = 0.02)
    {
        double f0 = 1 / value;
        double f1 = 1 / (f0 - Math.Truncate(f0));

        int a_t = (int)Math.Truncate(f0);
        int a_r = (int)Math.Round(f0);
        int b_t = (int)Math.Truncate(f1);
        int b_r = (int) Math.Round(f1);
        int c = (int)Math.Round(1 / (f1 - Math.Truncate(f1)));

        if (Math.Abs(1.0 / a_r - value) <= tolerance)
            return new KeyValuePair<int, int>(1, a_r);
        else if (Math.Abs(b_r / (a_t * b_r + 1.0) - value) <= tolerance)
            return new KeyValuePair<int, int>(b_r, a_t * b_r + 1);
        else
            return new KeyValuePair<int, int>(c * b_t + 1, c * a_t * b_t + a_t + c);
    }
}