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 a way to do a / b> c / d without overflow. For example, if I set a, b, c, d to be the 4 largest primes less than 2147483647. How would I determine if a / b> c / d is true. I am not allowed to use types other than int (i.e. I cannot convert to long long or double).

Answer 1

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

Answer 2

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 integer division is less or more, then you know the answer. It is difficult if integer division gives you the same result. In this case, you can simply use the remainder and see if there is% 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 simply reverse the problem and try it again.

Integer division with residuals of negative values ​​is a bit more random, but they can be easily handled on occasion:

 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 3

You can use the long school split method to get the dividend and coefficient and continue the division recursively, as in the following pseudo-code:

 bool compare(a,b,c,d) a/b = n + r/b c/d = m + q/d if (n == m) if (r == 0 && q == 0) return false if (r == 0) return false if (q == 0) return true if (a < b && c < d) if (c/a == d/b && c%a == 0 && d%b == 0) return false return !compare(b,r,d,q) //flip it to continue if (n > m) return true //a/b > c/d else if (n < m) return false //a/b < c/d else return compare(r,b,q,d) //need to continue comparing 

Answer 4

Just do std int division, like here: http://en.wikipedia.org/wiki/Division_algorithm (see the "Integer" (unsigned) section with the remainder). Div int int does not overflow, and you get both a factor and a reminder. Now, if Q1> Q2 or Q1 <Q2 it is clear, if Q1 == Q2, then you compare R1 / b and R2 / d.

eg. take the difficult case of Q1 == Q2, 25/12 and 44/21, Q1 = 2 and R2 = 1, Q2 = 2 and R2 = 2, so Q1 == Q2, and now you need to compare 1/12 and 2 / 21, Now you make a common divisor, which is 12 * 21, but you do not need to multiply them, you just need to compare 1 * 21 and 2 * 12. That is, you compare (1 * 21) / (12 * 21) and (2 * 12) / (12 * 21), but since the divisors are the same, this means comparing only 1 * 21 and 2 * 12.

Hm, but both 1 * 21 and 2 * 12 can overflow (if it's not 12, but maxint). OK anyway, maybe this will give some ideas.

For a better solution, just implement your own 128-bit (or N-bit) integer class. It’s not so difficult to do, maybe half a day. You simply save the large and low 64-bit parts separately and overload the + - * / → <operator

Answer 5

(a / b> c / d) can be partially written to avoid arithmetic in some cases, and then to avoid arithmetic overflow and lower flow in other cases. Note that the latter case remains as an exercise for the reader.

 bool fractioncompare(int a, int b, int c, int d) { bool cd_negative = (c < 0 && d > 0) || (c > 0 && d < 0); bool ab_negative = (a < 0 && b > 0) || (a > 0 && b < 0); // if c/d negative and a/b positive then a/b is larger if(cd_negative && !ab_negative) return true; // if c/d postive and a/b negative then a/b is not larger if((!cd_negative && ab_negative) return false; bool both_negative = cd_negative && ab_negative; // limited cases were a/b > c/d can be determined without needing to // do arithmetic calculations (so no risk of overflow / underflow) if(a > c && b < d) return !both_negative; if(a < c && b > d) return both_negative; int ab = a/b; int cd = c/d; bool no_trunc = a % b && c % d; if(no_trunc) return ab > cd; // No risk of overflow with divide and skipping the equal case avoids //truncation issues if(ab > cd) return true; if(ab < cd) return false; // truncation may mean ab and cd aren't actually equal so do some // comparisons on differences to determine the result if(!both_negative) { // use subtraction only to avoid overflow if(ab == 0) return (b-(ba) > d-(dc)); else return (b-(ba) < d-(dc)); } else { // TODO subtract values with same sign and add with // different signs and compare appropriately to determine result } } 

Answer 6

For unsigned integers, you can do the following:

 // We want to compare a/b and c/d given integers a, b, c, d while b != 0 and d != 0 if (a/b > c/d) then "a/b is greater than c/d" if (a/b < c/d) then "c/d is greater than a/b" b = b >> 1 d = d >> 1 if (b == d) then "a/b is equal to c/d" if (b == 0) then "a/b is greater than c/d" "c/d is greater than a/b" 

With signed integers, I would first check their signs, and then convert them to signed ones and, if necessary, perform the above operation. Unfortunately, up to 64 iterations are required for a 64-bit number. This can be optimized by simplifying relationships using GCD and Euclid. Some of the other answers here may have more effective solutions.