Check if a double = 1/3

Question

I have made a function that converts a double to a simplified fraction in Java:

public static int gcm(int a, int b) {
    return b == 0 ? a : gcm(b, a % b);
}
public static String toFraction(double d) {
    int decimals = String.valueOf(d).split("\\.")[1].length();
    int mult = (int) Math.pow(10, decimals);
    int numerator = (int) (d * mult);
    int denominator = mult;
    // now simplify
    int gcm = gcm(numerator, denominator);
    numerator /= gcm;
    denominator /= gcm;
    return numerator + "/" + denominator;
}

It works, except for the fact that if I use toFraction(1.0/3), this will, understandably, return "715827882/2147483647". How may I fix this to return "1/3"?

Answer 1

You have to allow for a certain error and not all fractions can be exactly represented as scalar values.

public static String toFraction(double d, double err) {
    String s = Long.toString((long) d);
    d -= (long) d;
    if (d > err) {
        for (int den = 2, max = (int) (1 / err); den < max; den++) {
            long num = Math.round(d * den);
            double d2 = (double) num / den;
            if (Math.abs(d - d2) <= err)
                return (s.equals("0") ? "" : s + " ") + num +"/"+den;
        }
    }
    return s;
}

public static void main(String... args) {
    System.out.println(toFraction(1.0/3, 1e-6));
    System.out.println(toFraction(1.23456789, 1e-6));
    System.out.println(toFraction(Math.E, 1e-6));
    System.out.println(toFraction(Math.PI, 1e-6));
    for (double d = 10; d < 1e15; d *= 10)
        System.out.println(toFraction(Math.PI, 1.0 / d));
}

prints

1/3
1 19/81
2 719/1001
3 16/113
3 1/5
3 1/7
3 9/64
3 15/106
3 16/113
3 16/113
3 3423/24175
3 4543/32085
3 4687/33102
3 14093/99532
3 37576/265381
3 192583/1360120
3 244252/1725033
3 2635103/18610450

Note: this finds the 21/7, 333/106 and 355/113 approximations for PI.

Answer 2

No double value is equal to one third, so the only way your program can be made to print 1/3 is if you change the specification of the method to favour "nice" answers rather than the answer that is technically correct.

One thing you could do is choose a maximum denominator for the answers, say 100, and return the closest fraction with denominator 100 or less.

Here is how you could implement this using Java 8 streams:

public static String toFraction(double val) {
    int b = IntStream.rangeClosed(1, 100)
                     .boxed()
                     .min(Comparator.comparingDouble(n -> Math.abs(val * n - Math.round(val * n))))
                     .get();
    int a = (int) Math.round(val * b);
    int h = gcm(a, b);
    return a/h + "/" + b/h;
}

There is no nice approach to this. double is not very good for this sort of thing. Note that BigDecimal can't represent 1/3 either, so you'll have the same problem with that class.