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.

Rigel

245/78 is a better approximation to PI with byte-sized numerator and denominator. – Determined

Note that Java bytes are signed, so 245 isn't a byte value in Java. – Tale

This should probably be tagged "math". I'd do it myself, but I don't have sufficient reputation yet. – Orford

"Note that Java bytes are signed, so 245 isn't a byte value in Java" - Oops. Guess I wanted unsigned bytes – Rigel

Check rosetta code it have implementation in different languages rosettacode.org/wiki/Convert_decimal_number_to_rational – Tomchay

Answer 1

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.

Orford

Answer 2

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

Rigel

I.e. you are using the convergents of continued fractions. en.wikipedia.org/wiki/… This yields some approximation, but why should it be the optimal one in the given range of numerators/denominators? – Arbiter

Answer 3

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

Volution

Efficiency isn't really an issue. However, I was hoping (and vaguely recall) that there is a method that is more efficient than brute force. – Rigel

No, you don't Johannes - given a specific denominator, you can calculate the closest numerator directly - since you want A and B such that A/B=C, you simply calculate B*C and round to the nearest integer, and that is your numerator. – Volution

This is better than the continued fraction approach since you are restricted to byte values. – Paperhanger

Answer 4

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)

Inchon

Answer 5

You should look at the Farey Sequence.
Given a limit on the denominator d, the Farey Sequence is every fraction having denominator <= d.

Then, you would simply take your float and compare it to the resolved value of the Farey fraction. This will allow you to represent your float in terms of repeating-decimal reals.

Here is a page on its implementation in java:
http://www.merriampark.com/fractions.htm

Here is a good demonstration of their use:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/fareySB.html

Ss

The first link (merriampark.com/fractions.htm) is dead. – Oui

Answer 6

What about using Apache's BigFraction:

import org.apache.commons.math3.fraction.BigFraction;

public static BigFraction GetBigFraction(double input)
{
    int precision = 1000000000;
    return new BigFraction((int)(input * (double)precision), precision);
}

Ivonne

Answer 7

I reached out here out of curiosity, but I remembered there's such feature in Python standard library fractions.

Maybe, we can look into the source code of the two functions:

• Fraction.from_float
• Fraction.limit_denominator

Zebrawood

I would add a link to python limit_denominator implementation: github.com/python/cpython/blob/… – Enjambement