Как сравнить две обыкновенные дроби. - Алгоритмы

Привет.

Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.

 1        1
---   и  ---
 x        y

, где x и y это рациональные числа больше 1. При таких условия

1/x < 1/y равносильно тому, что x > y.

Значит, берём исходные дроби у которых числитель меньше знаменателя, переворачиваем их, и сравниваем "наоборот". Целая часть опять считается, если опять неопределённость, то у нас снова получаются две дроби, только теперь у них знаменатели стали меньше (т.к. исходно числитель меньше знаменателя). И т.п.

Очень похоже на алгоритм Евклида.

Но это так, рассуждение, правильный ответ -- использовать int64

Здравствуйте, ZAMUNDA, Вы писали:

ZAM>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.

a/b > c/d эквивалентно ad > bc.
Можно отсортировать ad и bc чтобы, для определённости было a<d и d<c, затем скрупулёзно расписать все варианты взаимного расположения a, b, c, d и для каждого расписать, что будет больше, ad или bc...
Но это долго и муторно (хотя, работать потом будет быстро). Поэтому лучше перевести всё в число с большей разрядностью.

Здравствуйте, ZAMUNDA, Вы писали:

ZAM>Привет.

ZAM>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.

comparator(a, b, c, d) сравнивает a/b и c/d:


int comparator_helper(int x, int a, int b, int y, int c, int d) {
  if (a < b && c < d) {
    if (x < y) {
      return -1;
    } 
    if (x > y) {
      return 1;
    } 
    if (a == 0) {
      return - (c > 0);
    }
    if (c == 0) {
      return (a > 0);
    }
    return comparator_helper(0, d, c, 0, b, a);
  }
  return comparator_helper(x + a / b, a % b, b, y + c / d, c % d, d);
}

int comparator(int a, int b, int c, int d) {
printf("comparator %d %d %d %d\n", a, b, c, d);
  if (b < 0) {
    return comparator(-a, -b, c, d);
  }
  if (d < 0) {
    return comparator(a, b, -c, -d);
  }
  if (a < 0 && c < 0) {
    return comparator(-c, d, -a, b);
  }
  if (a < 0) {
    return -1;
  }
  if (b < 0) {
    return 1;
  }
  return comparator_helper(0, a, b, 0, c, d);
}

Здравствуйте, SergH, Вы писали:

SH>Здравствуйте, ZAMUNDA, Вы писали:

ZAM>>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты).

SH>Понятно, что можно ограничиться только дробями от 0 до 1, т.к. целая часть считается. Т.е. у нас две дроби

SH>

SH> 1        1
SH>---   и  ---
SH> x        y
SH>

SH>, где x и y это рациональные числа больше 1. При таких условия
Рациональные числа? — Мб целые, рациональное это ж сама дробь.

SH>Очень похоже на алгоритм Евклида.
Вот как раз родил. Через остатки. Ща закину.

SH>Но это так, рассуждение, правильный ответ -- использовать int64 :)
В него исходные числители со знаменателями не лезут уже. :)

Здравствуйте, ZAMUNDA, Вы писали:

Пошагово сравниваю результаты цельно численного деления.
Взятие остатка, это собсно и есть получение знаменателя дроби [0,1). О чём говорил SergH.
Чётность numStep показывает какие дроби сравниваю — перевёрнутые или нет.

/*
Если Fraction0 > Fraction1, то верну положительное число.
Если Fraction0 < Fraction1, то верну отрицательное число.
Если Fraction0 = Fraction1, то верну ноль.
*/

int FractionsCmp(
    int numNumerator0_I, 
    int numDenominator0_I, 
    int numNumerator1_I, 
    int numDenominator1_I)
{
    if ( numNumerator0_I == numNumerator1_I 
    && numDenominator0_I == numDenominator1_I )
        return 0;

    int numResidue0 = numNumerator0_I;
    int numDivider0 = numDenominator0_I;
    int numResidue1 = numNumerator1_I;
    int numDivider1 = numDenominator1_I;

    for (int numStep = 0;;numStep++)
    {
        int numResult0 = numResidue0 / numDivider0;
        int numResult1 = numResidue1 / numDivider1;
        int numReturn = numResult0 - numResult1;

        if (numReturn)
            return numReturn ^ -(numStep % 2);

        int numDividerNew0 = numResidue0 % numDivider0;
        int numDividerNew1 = numResidue1 % numDivider1;
        
        numResidue0 = numDivider0;
        numResidue1 = numDivider1;
        numDivider0 = numDividerNew0;
        numDivider1 = numDividerNew1;

        if ( numResidue0 == numResidue1 
        && numDivider0 == numDivider1 )
            return 0;
    }
}

Здравствуйте, ZAMUNDA, Вы писали:

SH>>

SH>> 1        1
SH>>---   и  ---
SH>> x        y
SH>>

SH>>, где x и y это рациональные числа больше 1. При таких условия
ZAM>Рациональные числа? — Мб целые, рациональное это ж сама дробь.

Да, это в общем она и есть. Я же не дробь вида a/b написал, а дробь вида 1/x. a/b = 1/(b/a) = 1/x, x = b/a -- рациональное.

ZAM>В него исходные числители со знаменателями не лезут уже.

Ну тогда сделать длинную арифметику хотя бы на 128 битов. По производительности, если очень захотеть, кажется, 128 бит можно даже в SSE засунуть. Но тут я совсем не знаю деталей, могу ошибаться.

Главное, это более общий способ решения задачи, более понятный читателям, к нему не надо писать комментарий на страницу с объяснением алгоритма, можно взять готовую библиотеку, меньше шансов ошибиться. Ну, конечно, если уж почему-то никак не получается (например, мучительно лень искать библиотеку

), то да, можно руками, как я предложил.

Здравствуйте, SergH, Вы писали:

SH>Ну тогда сделать длинную арифметику хотя бы на 128 битов. По производительности, если очень захотеть, кажется, 128 бит можно даже в SSE засунуть. Но тут я совсем не знаю деталей, могу ошибаться.
Ну пока так, пока длинные числа. Я где-то читал, как можно взять остаток от деления быстро, чтоб всё число не перебирать. Как найду, сделаю... ну или мож ща кто подскажет.
Главное сравнение сделал...

Здравствуйте, ZAMUNDA, Вы писали:

ZAM>Здравствуйте, ZAMUNDA, Вы писали:

ZAM>Пошагово сравниваю результаты цельно численного деления.
ZAM>Взятие остатка, это собсно и есть получение знаменателя дроби [0,1). О чём говорил SergH.
ZAM>Чётность numStep показывает какие дроби сравниваю — перевёрнутые или нет.

ZAM>

ZAM>/*
ZAM>Если Fraction0 > Fraction1, то верну положительное число.
ZAM>Если Fraction0 < Fraction1, то верну отрицательное число.
ZAM>Если Fraction0 = Fraction1, то верну ноль.
ZAM>*/

ZAM>int FractionsCmp(
ZAM>    int numNumerator0_I, 
ZAM>    int numDenominator0_I, 
ZAM>    int numNumerator1_I, 
ZAM>    int numDenominator1_I)
ZAM>{

ZAM>        int numReturn = numResult0 - numResult1;
ZAM>        if (numReturn)
ZAM>            return numReturn ^ -(numStep % 2);  // Стрёмное место (одно из)

ZAM>}
ZAM>

Этому коду явно юнит-тесты не помешают.
Как минимум, надо исправить потенциальные деления на 0 — как в самом начале, так и по ходу алгоритма.
Плюс есть подозрение на более тонкие ошибки (например, в отцитированном выше магическом XOR:
ничто не мешает numReturn оказаться равным -1, тогда при нечётном numStep вместо смены знака получим 0).

В общем, в текущем виде лучше такой функцией деньги не сравнивать

Здравствуйте, vmpire, Вы писали:

V>a/b > c/d эквивалентно ad > bc.
...
V>Поэтому лучше перевести всё в число с большей разрядностью.

Вот именно! Тем более, есть типы а-ля decimal, специально обученные для операций с финансами (28-29 значащих цифр).

Здравствуйте, ZAMUNDA, Вы писали:

А если попробывать делить дроби начиная с верхних регистров всмысле в первой дроби 4 милиарда и т.д делится на 2 милиарда и т.д, а вторая 3 миллиарда и т.д делится на 1 миллиард, тупо проверяем 4/2<3/1 , если сработало останавливаемся, если 42/43 vs 42/44 (т.е. на первом шаге 1) смотрим вторые значения и т.д. Или там разница в "копейках" и сильно глубокий уход будет?

ЗЫ Это так предположение.

Здравствуйте, Ларик, Вы писали:

Л>если 42/43 vs 42/44
Имел ввиду 4 миллиарда 200 миллионов и т.д

Здравствуйте, ZAMUNDA, Вы писали:

ZAM>Привет.

ZAM>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.
Поделить одну дробь на другую и посмотреть, больше или меньше 1 результат. Соответственно и одна дробь больше-меньше другой.

Здравствуйте, LaptevVV, Вы писали:

LVV>Поделить одну дробь на другую и посмотреть, больше или меньше 1 результат. Соответственно и одна дробь больше-меньше другой.

Я собственно это и предлагаю, только "сверху делить" начинать, в порядках. Давно что-то подобное было, но я там не с 1 сравнивал дробь, а с целым числом, потоком шло.

Здравствуйте, ZAMUNDA, Вы писали:

ZAM>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.

Что значит "разность меньше альфа"? Меньше эпсилон, имеется в виду?
Через double не пробовал, там разрядность поболее, чем во float.

Если доступна целочисленная арифметика двойной разрядности, то всё просто

int compare(int a, int b, int c, int d) // a/b <> c/d
{
  if(b==0 && d==0) { b=d=1; } // a/0 <> c/0 - сравниваем две бесконечности, кто из них бесконечнее :))

  // a/b <> c/d
  // ad <> bc

  // сперва исправляем знаки, чтобы направление неравенства не поменялось
  if(b<0) { a=-a; b=-b; }
  if(d<0) { c=-a; d=-d; }

  longint ad = longint(a)*d, bc = longint(b)*d; // тип longint выберите сами, в зависимости от платформы :)
  longint delta = ad-bc;
  if(delta<0) return -1;
  if(delta>0) return +1;
  return 0;
}

Вот если возможности процессора исчерпаны — тогда и придётся изгаляться.

Здравствуйте, andy1618, Вы писали:

A>Этому коду явно юнит-тесты не помешают.
Они ему и не помешали.

A>Как минимум, надо исправить потенциальные деления на 0 — как в самом начале, так и по ходу алгоритма.
Да и ещё надо учесть случаи неопределённости: FractionsCmp(0, 0, n, d), FractionsCmp(n, d, 0, 0), FractionsCmp(0, 0, 0, 0).

A>Плюс есть подозрение на более тонкие ошибки (например, в отцитированном выше магическом XOR:
A>ничто не мешает numReturn оказаться равным -1, тогда при нечётном numStep вместо смены знака получим 0).
Да там вообще высер на тему XOR ненужен, if дёшево надёжно и сердито. Грешен... каюсь...

A>В общем, в текущем виде лучше такой функцией деньги не сравнивать :))
[+Caps Lock] я ж сказал: "родил"![-Caps Lock] Простите поторопился -- хотелось закончить обсуждение. ...ну и понтонуться, кнешн. :)

А вообще спасибо, кривой код выкладывать нехорошо. Вот поправил исходный пример, надеюсь, всё учёл:

class ETermsIsNaN{}; // наследуется, по вкусу, от чего хотите

int FractionsCmp(
    int numNumerator0_I, 
    int numDenominator0_I, 
    int numNumerator1_I, 
    int numDenominator1_I)
{
    {
        int numChk = 0;
        
        if ( !numDenominator0_I ) numChk |= 0x1;
        if ( !numDenominator1_I ) numChk |= 0x2;
        if ( !numNumerator0_I )   numChk |= 0x4;
        if ( !numNumerator1_I )   numChk |= 0x8;

        switch (numChk)
        {
        case 0x1:
            return 1;
        case 0x2:
            return -1;
        case 0x1|0x2:
            return 0;
        case 0x1|0x4:;
        case 0x2|0x8:;
        case 0xf:;
            throw ETermsIsNaN();
        }
    }
    
    if ( numNumerator0_I == numNumerator1_I 
    && numDenominator0_I == numDenominator1_I )
        return 0;
    
    int numResidue0 = numNumerator0_I;
    int numDivider0 = numDenominator0_I;
    int numResidue1 = numNumerator1_I;
    int numDivider1 = numDenominator1_I;

    for (int numStep = 0;;numStep++)
    {
        int numResult0 = numResidue0 / numDivider0;
        int numResult1 = numResidue1 / numDivider1;
        int numReturn
            = numStep % 2 
                ? numResult1 - numResult0 
                : numResult0 - numResult1;

        if (numReturn)
            return numReturn;

        int numDividerNew0 = numResidue0 % numDivider0;
        int numDividerNew1 = numResidue1 % numDivider1;

        int numChk = 0;

        if ( !numDividerNew0 ) numChk |= 0x1;
        if ( !numDividerNew1 ) numChk |= 0x2;

        switch (numChk)
        {
        case 0x1:
            return 1;
        case 0x2:
            return -1;
        case 0x1|0x2:
            return 0;        
        }

        numResidue0 = numDivider0;
        numResidue1 = numDivider1;
        numDivider0 = numDividerNew0;
        numDivider1 = numDividerNew1;

        if ( numResidue0 == numResidue1 
        && numDivider0 == numDivider1 )
            return 0;
    }
}

ZAM>[+Caps Lock] я ж сказал: "родил"![-Caps Lock] Простите поторопился -- хотелось закончить обсуждение

я же раньше тебя rock stable код выложил

Здравствуйте, Кодт, Вы писали:

К>Что значит "разность меньше альфа"? Меньше эпсилон, имеется в виду?
Ага эпсилон. Глючит у меня проц на слова умные. :)

К>Если доступна целочисленная арифметика двойной разрядности, то всё просто
К>

К>int compare(int a, int b, int c, int d) // a/b <> c/d
К>  ...
К>}
К>

Ну эт ты реализовал вариант Ларик'а. Но никак не помножается, там в 64 бита (это ведь двойная?) параметры не лезут. :(
Хотя через него, вопщим, решение и нашлось. Я на каждой итерации алгоритма, который я родил, проверяю можно-ли сравнить промежуточные дроби твоим и Ларик'а алгоритмом, как обе дроби становятся нужного "формата" так всё...
Правда я пока не решил что быстрее: тупо до конца идти без проверок на возможность сравнить перекрестным умножением; или проверки делать, но избавиться от нескольких лишних итераций. Вообще можно посчитать сколько максимум итераций будет, но правда их много выходит, но правда в редких случаях, а обычно остатки от деления уменьшаются очень быстро.

Здравствуйте, dilmah, Вы писали:

ZAM>>[+Caps Lock] я ж сказал: "родил"![-Caps Lock] Простите поторопился -- хотелось закончить обсуждение
D>я же раньше тебя rock stable код выложил:)
А твой от нулей в параметрах валится по DbZ :) ... правда как и мой :(
И у меня в потсе текст с кодом, а у тя тока код: вот я пока писал ты своё и выложил, а код я скопипастил первым! :-P
PHANTOM READ у меня получился, ISOLATION LEVEL видно не тот. :)

От:	ZAMUNDA	для жалоб и предложений
Дата:	10.08.10 15:58
Оценка:

	От:	SergH
	Дата:	10.08.10 16:12
	Оценка:	6 (1)

	От:	vmpire
	Дата:	10.08.10 16:27
	Оценка:	1 (1)

	От:	dilmah
	Дата:	10.08.10 16:50
	Оценка:

От:	ZAMUNDA	для жалоб и предложений
Дата:	10.08.10 16:56
Оценка:

	От:	Ларик
	Дата:	19.08.10 04:27
	Оценка:

	От:	Ларик
	Дата:	19.08.10 04:29
	Оценка:

	От:	LaptevVV
	Дата:	19.08.10 05:08
	Оценка:

	От:	Ларик
	Дата:	19.08.10 06:23
	Оценка:	+1