compare fraction without overflow

Question

I am coding in C++. I am given 2 fractions, a/b and c/d where a,b,c,d are int. Does anyone know of a way to do a/b>c/d without overflow. For example, if I set a,b,c,d as the 4 largest primes less than 2147483647. How would I determine if a/b>c/d is true. I am not allowed to use any other types other than int (ie. I can't convert to long long or double).

Answer 1

Here is one way that works for positive integers:

bool greaterPositiveFraction(int a,int b,int c,int d);

bool greaterOrEqualPositiveFraction(int a,int b,int c,int d)
{
  if (b == 0) return true;
  if (d == 0) return false;
  if (a/b > c/d) return true;
  if (a/b < c/d) return false;
  return !greaterPositiveFraction(b,a%b,d,c%d);
}

bool greaterPositiveFraction(int a,int b,int c,int d)
{
  if (d == 0) return false;
  if (b == 0) return true;
  if (a/b > c/d) return true;
  if (a/b < c/d) return false;
  return !greaterOrEqualFraction(b,a%b,d,c%d);
}

The idea is that if the integer division is less or greater, then you know the answer. It is only tricky if the integer division gives you the same result. In this case, you can just use the remainder, and see if a%b/b > c%d/d. However, we know that a%b/b > c%d/d if b/(a%b) < d/(c%d), so we can just turn the problem around and try it again.

Integer division with remainders of negative values is a bit more messy, but these can easily be handled by cases:

bool greaterFraction(int a,int b,int c,int d)
{
  if (b<0) { b = -b; a = -a; }
  if (d<0) { d = -d; c = -c; }
  if (a<0 && c<0) return greaterPositiveFraction(-c,d,-a,b);
  if (a<0) return false;
  if (c<0) return true;
  return greaterPositiveFraction(a,b,c,d);
}

Answer 2

You could do the standard algorithm (compare a*d with b*c), but do the multiplications using something other than 64-bit multiplication. Like divide your numbers into 16-bit chunks and use a standard biginteger multiplication routine to compute the result.