сравнить дробь без перелива

Вот один способ, который работает для натуральных чисел:

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);
}

Идея состоит в том, что если целочисленное деление меньше или больше, тогда вы знаете ответ. Это только сложно, если целочисленное деление дает вам тот же результат. В этом случае вы можете просто использовать остаток и посмотреть, если a% b / b> c% d / d. Тем не менее, мы знаем, что a% b / b> c% d / d, если b / (a% b) < d / (c% d), поэтому мы можем просто перевернуть проблему и попробовать снова.

Целочисленное деление с остатками отрицательных значений немного более грязно, но это может быть легко обработано в следующих случаях:

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);
}

Просто сделайте стандартное разделение как здесь: http://en.wikipedia.org/wiki/Division_algorithm (см. Целочисленное деление (без знака) с остатком). Div int by int не переполняется, и вы получаете как частное, так и напоминание. Теперь, если Q1> Q2 или Q1 < Q2 понятно, если Q1 == Q2, тогда вы сравниваете R1 / b и R2 / d.

Например. возьмите сложный случай Q1 == Q2, 25/12 и 44/21, Q1 = 2 и R2 = 1, Q2 = 2 и R2 = 2, таким образом, Q1 == Q2, и теперь вам нужно сравнить 1/12 и 2/21 , Теперь вы создаете общий делитель 12 * 21, но вам не нужно их умножать, вам просто нужно сравнить 1 * 21 и 2 * 12. То есть Вы сравниваете (1 * 21) / (12 * 21) и (2 * 12) / (12 * 21), но поскольку делители одинаковы, это означает, что сравниваются только 1 * 21 и 2 * 12.

Хм, но и 1 * 21, и 2 * 12 могут переполниться (если это не 12, а maxint). Хорошо, в любом случае, может быть, это даст некоторые идеи.

Для лучшего решения просто реализуйте свой собственный 128-битный (или N-битный) целочисленный класс. Это не так сложно сделать, может быть, полдня. Вы просто разделяете верхние и нижние 64-битные части и оператор перегрузки + — * / >><<,

(a / b> c / d) можно частично записать, чтобы избежать арифметики в ряде случаев, а затем избежать арифметического переполнения и потери в остальных случаях. Обратите внимание, что окончательный вариант оставлен в качестве упражнения для читателя.

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-(b-a) > d-(d-c));
else return (b-(b-a) < d-(d-c));
}
else
{
// TODO subtract values with same sign and add with
// different signs and compare appropriately to determine result
}

}

Вы можете использовать метод школьного деления, чтобы получить дивиденды и частное и продолжить рекурсивное деление, как показано в следующем псевдокоде:

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