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).
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.