Possible error while dividing doubles

Question

I would like to check for equality 2 fractions. I think that the method I wrote is not correct because of possible loss of accuracy. Am I right or wrong?

public boolean equals(Rational r) {
    return (double) numerator / denominator == (double) r.numerator / r.denominator;
}

Are the numerator and denominator integers? – Richard Tingle Dec 22 '13 at 09:18 — Richard Tingle, Dec 22 '13 at 09:18

score 5 · Accepted Answer · answered Dec 22 '13 at 09:17

5

I think this would be better:

public boolean equals(Rational r) {
  return numerator * r.denominator == r.numerator * denominator;
}

answered Dec 22 '13 at 09:17

Juvanis

25,802
5
69
87

Thanks but should I divide those two or just find common denumerator and then compare them? – Yoda Dec 22 '13 at 09:18
@Yoda No. Think of this example: 3/5 == 6/10 ? Then 3*10 == 5*6? Yes it is, so they are equal. – Juvanis Dec 22 '13 at 09:19
Nice approach, I nearly didn't spot that you are multiplying with each other's divisors. – Tim B Dec 22 '13 at 09:21
The problem with this approach is that you can overflow the numeric range of the underlying integer types, assuming the rational type is based on integers. If it's based on doubles (which seems odd), then you could still get loss of precision if the product exceeds the precision of the significand of a double (53 bits). – Joe Z Dec 22 '13 at 09:24
1

In that case, use BigIntegers. The nice thing is that it will give a correct result, which won't be the case with solutions using division, even with BigDecimal. – JB Nizet Dec 22 '13 at 09:26
@JBNizet : You can get an exact answer without BigIntegers by always using normalized rationals (ie. the GCD is guaranteed factored out). You can either make the class keep rationals normalized, or you can normalize as part of the comparison process. – Joe Z Dec 22 '13 at 09:27

score 2 · Answer 2 · answered Dec 22 '13 at 09:17

2

You are correct, this check will fail in a lot of cases.

The only way to make it work is to either convert the result to a BigDecimal or a String and then compare that or to define an allowed error - i.e.:

public boolean equals(Rational r) {
    double c1 = ((double) numerator) / denominator;
    double c2 = ((double) r.numerator) / r.denominator;
    return c2 > (c1-allowedError) && c2 < (c1+allowedError);
}

answered Dec 22 '13 at 09:17

Tim B

40,716
16
83
128

A common pattern is to write `Math.abs(c1 - c2) <= allowedError` – Peter Lawrey Dec 22 '13 at 09:18
Yes, I nearly wrote that instead but figured this was clearer. – Tim B Dec 22 '13 at 09:23
1

I'm not certain you can define an `allowedError` that will work over the entire range. – Joe Z Dec 22 '13 at 09:52

Keerthivasan · Answer 3 · 2013-12-22T09:24:30.847

1

You can do this way

public boolean equals(Rational r) {
    return numerator * r.denominator == r.numerator * denominator;
}

edited Dec 22 '13 at 09:24

answered Dec 22 '13 at 09:17

Keerthivasan

12,760
2
32
53

-1 `3 / 4 = 0` and `5 / 9 = 0` but `3 / 4 != 5 / 9`. – Peter Lawrey Dec 22 '13 at 09:19
@Peter Lawrey i just wanted to mention it should be casted after division in his logic. I have updated my answer correctly – Keerthivasan Dec 22 '13 at 09:23
Thanks Peter, i did post the initial answer assuming it was a cast problem. I want to always correct the problems which i make! ;) – Keerthivasan Dec 22 '13 at 13:39

Joe Z · Answer 4 · 2013-12-22T09:37:54.077

If your rationals have reduced all common factors out of numerator and denominator, then you can do this:

return (numerator == r.numerator) && (denominator == r.denominator);

If your rationals have not done that factorization, then I suggest you implement a GCD function that will allow you to do that. Then compare the reduced numerator and denominator against the reduced r.numerator and r.denominator.

Example, assuming int is the underlying type for your rational numerator and denominator:

int gcd_lhs = gcd( numerator,   denominator   );
int gcd_rhs = gcd( r.numerator, r.denominator );

int lhs_red_num = numerator   / gcd_lhs;
int lhs_red_den = denominator / gcd_lhs;
int rhs_red_num = r.numerator   / gcd_rhs;
int rhs_red_den = r.denominator / gcd_rhs;

return (lhs_red_num == rhs_red_num) && (lhs_red_den == rhs_red_den);

This approach has the advantage of being exact in all cases, and it will never exceed the precision of the underlying type that you're using for numerator and denominator.

Approaches relying on multiplication, or on dividing something out of the values other than the GCD risk overflowing the precision available in the underlying types. (Division can "overflow" the available precision by producing a repeating binary fraction that must be rounded to fit in the available bits, assuming you cast to double first. Dividing by GCD is always exact, and remain as integer division.)

You can mitigate that by using a BigInteger type and applying the cross-multiplication approach. That has its own costs. If you're already using BigInteger to store numerator and denominator, that may be the easiest approach, though.

peter.petrov · Answer 5 · 2013-12-22T09:25:35.703

One way to do this is as follows:

boolean eq = Math.abs( (double) numerator / denominator - 
                       (double) r.numerator / r.denominator ) < EPS;

where

EPS is some small positive constant like e.g. EPS=0.00001.

If the eq variable is set to true, it means your numbers are "equal"
except for possible precision errors which you want to ignore here.

Of course in Java operations with floating point
numbers are not 100% precise as in many other languages.

Alternatively, as other people suggested here,
you may decide to not use doubles at all for this
particular task / but you cannot always avoid them ;) /

score 0 · Answer 6 · edited May 23 '17 at 10:32

0

Using == with doubles can be dangerous because certain fraction (including some that are expressible in decimal) can't be expressed in a binary floating point system

You can rearrange your equations such that you never need doubles (assumimg your numerator and denominator are integers)

r.denominator*numerator==denominator*r.numerator

edited May 23 '17 at 10:32

Community

1
1

answered Dec 22 '13 at 09:22

Richard Tingle

16,906
5
52
77

Possible error while dividing doubles

6 Answers6