How can I turn a floating point number into the closest fraction represented by a byte numerator and denominator?

Question

How can I write an algorithm that given a floating point number, and attempts to represent is as accurately as possible using a numerator and a denominator, both restricted to the range of a Java byte?

The reason for this is that an I2C device wants a numerator and denominator, while it would make sense to give it a float.

For example, 3.1415926535... would result in 245/78, rather than 314/100 or 22/7.

In terms of efficiency, this would be called around three times at the start of the program, but after that not at all. So a slow algorithm isn't too bad.

Answer 1

How worried are you about efficiency? If you're not calling this conversion function 100s of times per second or more, then it probably wouldn't be all that hard to brute-force through every possible denominator (most likely only 255 of them) and find which one gives the closest approximation (computing the numerator to go with the denominator is constant time).

Answer 2

There is an algorithm using continued fractions.

Answer 3

I've written some code (in Java, even) to do just the thing you're asking for. In my case, I needed to display a scaling factor as both a percentage and a ratio. The most familiar example of this is the zoom dialog you see in image editors, such as the GIMP.

You can find my code here, in the updateRatio() method starting at line 1161. You can simply use it, so long as the LGPL license works for you. What I did essentially follows what's done in the GIMP---this is one of those things where there's pretty much only one efficient, sensible way to do it.

Answer 4

Here's the code I used in the end (based on uckelman's code)

public static int[] GetFraction(double input)
{
    int p0 = 1;
    int q0 = 0;
    int p1 = (int) Math.floor(input);
    int q1 = 1;
    int p2;
    int q2;

    double r = input - p1;
    double next_cf;
    while(true)
    {
     r = 1.0 / r;
     next_cf = Math.floor(r);
     p2 = (int) (next_cf * p1 + p0);
     q2 = (int) (next_cf * q1 + q0);

     // Limit the numerator and denominator to be 256 or less
     if(p2 > 256 || q2 > 256)
      break;

     // remember the last two fractions
     p0 = p1;
     p1 = p2;
     q0 = q1;
     q1 = q2;

     r -= next_cf;
    }

    input = (double) p1 / q1;
    // hard upper and lower bounds for ratio
    if(input > 256.0)
    {
     p1 = 256;
     q1 = 1;
    }
    else if(input < 1.0 / 256.0)
    {
     p1 = 1;
     q1 = 256;
    }
    return new int[] {p1, q1};
}

Thanks for those who helped

Answer 5

I would comment, but I don't have rep yet...

Eric's answer above doesn't consider the case where an exact result is possible. For example, if you use 0.4 as input, then the representation should be 2/5, in which case you end up with a division by zero in the third iteration of the loop (r=0 on second loop => r = 1/r error on third).

So you want to modify the while loop to exclude that option:

while(true)

should be

while(r != 0)