Convert double into BigRational (two BigInteger for numerator/denominator)

Question

I have a custom made BigRational class in java. It is implemented as two BigInteger, representing numerator and denominator.

I have a "from string" method that take input in the form "-1234/43" but I would like to implement a from double/from float; I'm not scare of generating a very large number, but I would like to keep all the precision present in the floating point representation; thus if I converted them in some decimal representation I would lose precision thanks to rounding.

-How do I generate a pair of BigIntegers that interpreted as numerator/denominator represents the same exact number as a given float/double?

(Hopefully by being in Java I do not need to worry about bigendian/littleendian, but I would like a confermation too)

Are you going to add a method that takes ONE float and creates your BigRational? — drkblog, Sep 20 '20 at 03:59
https://stackoverflow.com/questions/51142275/exact-value-of-a-floating-point-number-as-a-rational — drkblog, Sep 20 '20 at 04:05
yes, one method that takes a double and produces a BigRational. I'm searching for an elegant way using java standard library features — Marco Servetto, Sep 20 '20 at 04:24
I see. From the question liked above I understand there is no java standard method for solving this. Probably because is a complex mathematical problem and not usually needed in day to day programming. Maybe google for know algorithms that solve this and implement your version of one you like. — drkblog, Sep 20 '20 at 14:23

Marco Servetto · Answer 1 · 2020-09-22T05:06:41.720

So, thanks to a good friend I have found a good solution, so I will post it here for anyone in need. It is not using any string representation so it should also be quite on the fast side. I have tested it "reasonably" and It seams to work and to keep the exact representation. Of course, we should still add some 'if' to handle NANs.

final static int mantissaBits=53;
public static BigRational from(double num){
  int exponent=Math.getExponent(num);
  long man=Math.round(Math.scalb(num, mantissaBits-exponent));
  long den=Math.round(Math.scalb(1.0, mantissaBits-exponent));
  return new BigRational(BigInteger.valueOf(man),BigInteger.valueOf(den));
}

Andreas · Answer 2 · 2020-09-20T17:55:28.467

Caveat: Not all numbers are rational, e.g. PI is not a rational number. However, given that double (and float) have limited precision, there are a limited number of digits in a floating-point value, so you can always find a rational number for that. E.g. Math.PI is a double with the value 3.141592653589793. That number is the rational number 3_141_592_653_589_793 / 1_000_000_000_000_000.

Understanding the caveat that floating-point values aren't accurate, you can find the rational number with the help of BigDecimal, then normalize the rational number using BigInteger.gcd().

Like this:

static void printAsRational(double value) {
    printAsRational(BigDecimal.valueOf(value));
}
static void printAsRational(float value) {
    printAsRational(new BigDecimal(Float.toString(value)));
}
static void printAsRational(BigDecimal value) {
    BigInteger numerator, denominator;
    if (value.signum() == 0) {
        // Zero is 0 / 1
        numerator = BigInteger.ZERO;
        denominator = BigInteger.ONE;
    } else {
        BigDecimal bd = value.stripTrailingZeros(); // E.g. 1.20 -> 1.2
        if (bd.scale() < 0)
            bd = bd.setScale(0); // E.g. 1.7e3 -> 1700
        numerator = bd.unscaledValue(); // E.g. 1.25 -> 125
        denominator = BigDecimal.valueOf(1, -bd.scale()).toBigInteger(); // E.g. 1.25 -> 100
        
        // Normalize, e.g. 12/8 -> 3/2
        BigInteger gcd = numerator.gcd(denominator);
        if (! gcd.equals(BigInteger.ONE)) {
            numerator = numerator.divide(gcd);
            denominator = denominator.divide(gcd);
        }
    }
    System.out.println(value + " = " + numerator + " / " + denominator);
}

Tests

printAsRational(Math.PI);
printAsRational(Math.E);
printAsRational(1.25);
printAsRational(1);
printAsRational(0);
printAsRational(-1.25);
printAsRational(1.25e9);
printAsRational(1.25e-9);

Output

3.141592653589793 = 3141592653589793 / 1000000000000000
2.718281828459045 = 543656365691809 / 200000000000000
1.25 = 5 / 4
1.0 = 1 / 1
0.0 = 0 / 1
-1.25 = -5 / 4
1.25E+9 = 1250000000 / 1
1.25E-9 = 1 / 800000000

Question asks how to generate a numerator/denominator pair of `BigInteger` values from a given `float`/`double`, and this answer shows exactly how to do it, so why don't people like the answer? Why down-vote? What am I missing/misunderstanding here? — Andreas, Sep 20 '20 at 17:55
Hi, I think the reason is as follow: in the documentation of https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/math/BigDecimal.html#valueOf(double) You can read """a BigDecimal whose value is equal to or **approximately** equal to the value of val.""" That is, to convert to floating point to DECIMAL notation the system may be forced to lose some precision. — Marco Servetto, Sep 20 '20 at 22:18
@MarcoServetto But the thing is that the precision is really already lost *before* that point, given the fact that a [floating-point](https://en.wikipedia.org/wiki/Floating-point_arithmetic) value is an *approximation* to begin with. If you store 0.4 in a `double`, the correct answer is rational number 2/5, not what you get from not using that `valueOf()` method, which would be 3602879701896397/9007199254740992 (from `0.40000000000000002220446049250313080847263336181640625`). — Andreas, Sep 21 '20 at 16:11
Of course the float is an approximation of the decimal, but once the value is in the float, that value does represents a specific number. I want to turn that exact number into a BigRational without any loss from that point on. — Marco Servetto, Sep 22 '20 at 05:10
@MarcoServetto Which is what this code is doing, turning the *specific* number represented by a `double` into a pair of numerator/denominator `BigInteger` values, **without loss of precision**, i.e. if you convert it back to a `double`, it will be the *same value*! That is why I'm confused about the down-votes, because this is exactly what the question is asking for. — Andreas, Sep 22 '20 at 16:21

Convert double into BigRational (two BigInteger for numerator/denominator)

2 Answers2