4

Let's say I have two fractions: a/b and c/d, where a,b,c,d are all integers greater than 0. Is it safe to check their equality using the following function?:

bool are_equal_fractions(int a, int b, int c, int d) {  
   return (static_cast<double>(a) / b == static_cast<double>(c) / d);
}

According to another question: can I compare two fractions if both have denominator with power of 2 I can use this method when both denominators are powers of 2, but what about more generic case?

Community
  • 1
  • 1
mechatroner
  • 1,272
  • 1
  • 17
  • 25
  • From that question: "all IEE754 floating point numbers are represented as M * 2 ^ E, where M and E are both integers (and may be negative). Hence 3 / 4.0 and 6 / 8.0 are both exactly equal to 3 * 2 ^ -2 and fully representable in IEE754 format." Arbitrary numbers aren't going to fit that scheme neatly. Why not reduce the fractions and then directly compare the integers, or a similar manipulation? – Matthew Read Apr 12 '15 at 21:32
  • 3
    Why don't you instead check whether `a*d == b*c` in integer arithmetic? – Oliver Charlesworth Apr 12 '15 at 21:32
  • 2
    @OliverCharlesworth, that could result in integer overfllow. – R Sahu Apr 12 '15 at 21:34
  • @OliverCharlesworth certainly because of potential overflow, for example if a is INT_MAX and d is 2... – Christophe Apr 12 '15 at 21:35
  • 2
    @RSahu/Christophe - avoidable by using a wider type (and if one doesn't exist, you can emulate it).. – Oliver Charlesworth Apr 12 '15 at 21:36
  • 1
    Could [`std::ratio`](http://en.cppreference.com/w/cpp/numeric/ratio/ratio) be of any help here? – πάντα ῥεῖ Apr 12 '15 at 21:39
  • @OliverCharlesworth I can use this check (a*d == b*c), but what I really want is to store bunch of fractions as doubles, and still have an option to check for equality later. – mechatroner Apr 12 '15 at 22:00

1 Answers1

9

Although every int can be represented as a double, many int ratios cannot be represented exactly, and very similar but slightly different fractions may round to the same double.

Consider a=2147483647, b=2147483646, c=2147483646, d=2147483645. The denominator of 2147483646/2147483645 will be a multiple of 5, even in its lowest terms. The denominator of 2147483647/2147483646 is not a multiple of 5, so they are not equal.

cout << are_equal_fractions(2147483647, 2147483646, 2147483646, 
        2147483645) << endl;

outputs "1".

In general, equal fractions in this pattern would mean:

(i+2)/(i+1) == (i+1)/i
i*(i+2) == (i+1)*(i+1)
i^2 + 2*i == i^2 + 2*i + 1
0 == 1

which has no solution.

The smallest counter-example following this pattern is are_equal_fractions(67114658,67114657,67114657,67114656). I do not think any other pattern could have a closer non-equal ratio, so it is probably safe for values less than this case.

Patricia Shanahan
  • 25,849
  • 4
  • 38
  • 75
  • Thanks, that's really useful. How did you come up with this lower bound? – mechatroner Apr 12 '15 at 22:37
  • @mechatroner Brute force. I ran a program that tested `are_equal_fractions(i + 2, i + 1, i + 1, i)` for each value of `i` starting at one until I got a true result. – Patricia Shanahan Apr 12 '15 at 22:38
  • 1
    I have a proof at https://stackoverflow.com/a/73394324/270986 that your example is the worst (best?) case: for `a`, `b`, `c` and `d` bounded in absolute value by `67114657`, `a/b == c/d` as IEEE 754 binary64 doubles guarantees that `a/b == c/d` as fractions. – Mark Dickinson Aug 18 '22 at 18:45