Ever needed to convert a decimal number into a fraction, like 0.5 into 1 / 2 ?
There is a simple method to do this, but it doesn't always work:
public static long[] toFraction(double decimal) { String decimalAsString = String.valueOf(decimal); int decimalPlaces = decimalAsString.length() - decimalAsString.indexOf('.') - 1; long divisor = (long) Math.pow(10, decimalPlaces); long dividend = (long) (decimal * divisor); long gcd = greatestCommonDivisor(dividend, divisor); return new long[] { dividend / gcd, divisor / gcd }; } public static long greatestCommonDivisor(long... numbers) { return greatestCommonDivisor(LongStream.of(numbers)); } public static long greatestCommonDivisor(LongStream numbers) { return greatestCommonDivisorLong(numbers.boxed()); } public static long greatestCommonDivisorLong(Stream<Long> numbers) { return numbers.reduce(0L, (x, y) -> gcd(x, y)); } private static long gcd(long x, long y) { return (y == 0L) ? x : gcd(y, x % y); }
This works nice as long as you don't pass "periodic" numbers like 1.333333333333333 to that method. It would return 1333333333333333 / 1000000000000000, not 4 / 3 like expected.
Now there are libraries on the web that resolve this problem, the most popular being Apache Commons Math. The only problem for me was that there are so many other solutions in this library (of size 2.2 MB) that I would never need for my very small project. So I decided to go into that source and look if I could adapt some snippet. What I came across was not really understandable code, but trying it out showed that it worked well also for periodic numbers:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | /** Adopted and simplified from apache-commons-math BigFraction. */ public class Fraction { private static final double DEFAULT_EPSILON = 1e-5; // 1.0e-20 private static final int DEFAULT_ITERATIONS = 100; // 10000 private final double doubleValue; private final BigInteger dividend; // numerator private final BigInteger divisor; // denominator /** * @param dividend numerator, the number above the fraction line. * @param divisor denominator, the number below the fraction line. */ public Fraction(long dividend, long divisor) { this((double) dividend / (double) divisor); } /** * @param value the number to turn into a (reduced) fraction. */ public Fraction(double value) { this(value, DEFAULT_EPSILON, Integer.MAX_VALUE, DEFAULT_ITERATIONS); } private Fraction(double value, double epsilon, int maxDenominator, int maxIterations) { this.doubleValue = value; final long overflow = Long.MAX_VALUE; double r0 = value; long a0 = (long) Math.floor(r0); if (Math.abs(a0) > overflow) { throw new RuntimeException("MAX_VALUE overflow!"); } // check for (almost) integer arguments, which should not go to iterations. if (Math.abs(a0 - value) < epsilon) { dividend = BigInteger.valueOf(a0); divisor = BigInteger.ONE; return; } long p0 = 1; long q0 = 0; long p1 = a0; long q1 = 1; long p2 = 0; long q2 = 1; int n = 0; boolean stop = false; do { ++n; final double r1 = 1.0 / (r0 - a0); final long a1 = (long) Math.floor(r1); p2 = (a1 * p1) + p0; q2 = (a1 * q1) + q0; if ((p2 > overflow) || (q2 > overflow)) { // in maxDenominator mode, if the last fraction was very close to the actual value // q2 may overflow in the next iteration; in this case return the last one. if (epsilon == 0.0 && Math.abs(q1) < maxDenominator) { break; } throw new RuntimeException("maxDenominator overflow!"); } final double convergent = (double) p2 / (double) q2; if ((n < maxIterations) && (Math.abs(convergent - value) > epsilon) && (q2 < maxDenominator)) { p0 = p1; p1 = p2; q0 = q1; q1 = q2; a0 = a1; r0 = r1; } else { stop = true; } } while (!stop); if (n >= maxIterations) { throw new RuntimeException("maxIterations overflow!"); } if (q2 < maxDenominator) { dividend = BigInteger.valueOf(p2); divisor = BigInteger.valueOf(q2); } else { dividend = BigInteger.valueOf(p1); divisor = BigInteger.valueOf(q1); } } /** @return the calculated-by-division or constructor-given value. */ public double doubleValue() { return doubleValue; } /** @return the reduced dividend (numerator). */ public BigInteger getDividend() { return dividend; } /** @return the reduced divisor (denominator). */ public BigInteger getDivisor() { return divisor; } } |
112 lines of code against a 2.2 MB library (that may also change its API in course of time) is not bad. I confess that I don't understand lines 26 to 95, but I also don't understand many other things that I use daily.
Here are two applications for class Fraction, which I have put into MathUtils.java:
/** 1.5 -> 3/2 */ public static long[] toFraction(double number) { final Fraction fraction = new Fraction(number); return new long[] { fraction.getDividend().longValue(), fraction.getDivisor().longValue() }; } /** 10/4 -> 5/2 */ public static long[] reduceFraction(long dividend, long divisor) { final Fraction fraction = new Fraction(dividend, divisor); return new long[] { fraction.getDividend().longValue(), fraction.getDivisor().longValue() }; }
Following JUnit-5 test code in MathUtilsTest.java showed that it works:
@Test void periodicNumberToFraction() { long[] fraction; fraction = MathUtils.toFraction1(1.333333333333333); assertEquals(4, fraction[0]); assertEquals(3, fraction[1]); fraction = MathUtils.toFraction(1.666666666666666); assertEquals(5, fraction[0]); assertEquals(3, fraction[1]); fraction = MathUtils.toFraction(1.777777777777777); assertEquals(16, fraction[0]); assertEquals(9, fraction[1]); fraction = MathUtils.toFraction(0.777777777777777); assertEquals(7, fraction[0]); assertEquals(9, fraction[1]); fraction = MathUtils.toFraction(1.599999999999999); // ~ 1.6 assertEquals(8, fraction[0]); assertEquals(5, fraction[1]); }
If you can't put a truck onto your bicycle, you may want to use a photo of it:-)
Hope this is helpful to someone!
