Здравствуйте, ZAMUNDA, Вы писали:
ZAM>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.
Понятно, что можно ограничиться только дробями от 0 до 1, т.к. целая часть считается. Т.е. у нас две дроби
1 1
--- и ---
x y
, где x и y это рациональные числа больше 1. При таких условия
1/x < 1/y равносильно тому, что x > y.
Значит, берём исходные дроби у которых числитель меньше знаменателя, переворачиваем их, и сравниваем "наоборот". Целая часть опять считается, если опять неопределённость, то у нас снова получаются две дроби, только теперь у них знаменатели стали меньше (т.к. исходно числитель меньше знаменателя). И т.п.
Очень похоже на алгоритм Евклида.
Но это так, рассуждение, правильный ответ -- использовать int64
Здравствуйте, 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).
В общем, в текущем виде лучше такой функцией деньги не сравнивать
Здравствуйте, ZAMUNDA, Вы писали:
ZAM>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.
a/b > c/d эквивалентно ad > bc.
Можно отсортировать ad и bc чтобы, для определённости было a<d и d<c, затем скрупулёзно расписать все варианты взаимного расположения a, b, c, d и для каждого расписать, что будет больше, ad или bc...
Но это долго и муторно (хотя, работать потом будет быстро). Поэтому лучше перевести всё в число с большей разрядностью.
Здравствуйте, LaptevVV, Вы писали:
LVV>Поделить одну дробь на другую и посмотреть, больше или меньше 1 результат. Соответственно и одна дробь больше-меньше другой.
Я собственно это и предлагаю, только "сверху делить" начинать, в порядках. Давно что-то подобное было, но я там не с 1 сравнивал дробь, а с целым числом, потоком шло.
Самая большая в мире ложь — "Я прочел и согласен с условиями пользовательского соглашения".
Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
Здравствуйте, 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 :)
В него исходные числители со знаменателями не лезут уже. :)
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
Пошагово сравниваю результаты цельно численного деления.
Взятие остатка, это собсно и есть получение знаменателя дроби [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;
}
}
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
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 засунуть. Но тут я совсем не знаю деталей, могу ошибаться.
Ну пока так, пока длинные числа. Я где-то читал, как можно взять остаток от деления быстро, чтоб всё число не перебирать. Как найду, сделаю... ну или мож ща кто подскажет.
Главное сравнение сделал...
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
А если попробывать делить дроби начиная с верхних регистров всмысле в первой дроби 4 милиарда и т.д делится на 2 милиарда и т.д, а вторая 3 миллиарда и т.д делится на 1 миллиард, тупо проверяем 4/2<3/1 , если сработало останавливаемся, если 42/43 vs 42/44 (т.е. на первом шаге 1) смотрим вторые значения и т.д. Или там разница в "копейках" и сильно глубокий уход будет?
ЗЫ Это так предположение.
Самая большая в мире ложь — "Я прочел и согласен с условиями пользовательского соглашения".
Здравствуйте, ZAMUNDA, Вы писали:
ZAM>Привет.
ZAM>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.
Поделить одну дробь на другую и посмотреть, больше или меньше 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;
}
}
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
Здравствуйте, Кодт, Вы писали:
К>Что значит "разность меньше альфа"? Меньше эпсилон, имеется в виду?
Ага эпсилон. Глючит у меня проц на слова умные. :)
К>Если доступна целочисленная арифметика двойной разрядности, то всё просто К>
К>int compare(int a, int b, int c, int d) // a/b <> c/d
К> ...
К>}
К>
Ну эт ты реализовал вариант Ларик'а. Но никак не помножается, там в 64 бита (это ведь двойная?) параметры не лезут. :(
Хотя через него, вопщим, решение и нашлось. Я на каждой итерации алгоритма, который я родил
, проверяю можно-ли сравнить промежуточные дроби твоим и Ларик'а алгоритмом, как обе дроби становятся нужного "формата" так всё...
Правда я пока не решил что быстрее: тупо до конца идти без проверок на возможность сравнить перекрестным умножением; или проверки делать, но избавиться от нескольких лишних итераций. Вообще можно посчитать сколько максимум итераций будет, но правда их много выходит, но правда в редких случаях, а обычно остатки от деления уменьшаются очень быстро.
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
ZAM>>[+Caps Lock] я ж сказал: "родил"![-Caps Lock] Простите поторопился -- хотелось закончить обсуждение D>я же раньше тебя rock stable код выложил:)
А твой от нулей в параметрах валится по DbZ :) ... правда как и мой :(
И у меня в потсе текст с кодом, а у тя тока код: вот я пока писал ты своё и выложил, а код я скопипастил первым! :-P
PHANTOM READ у меня получился, ISOLATION LEVEL видно не тот. :)
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
Здравствуйте, ZAMUNDA, Вы писали:
ZAM>Ну эт ты реализовал вариант Ларик'а.
Как мне кажется, — нет. Ларик предлагал какую-то химию с уточнением дробей, итерационный алгоритм. (Я не очень вдумывался в него, если честно).
А я предлагаю за один приём.
ZAM> Но никак не помножается, там в 64 бита (это ведь двойная?) параметры не лезут.
То есть, int у тебя 64-битный? Ну возьми 128-битный longint.
Умножение придётся, правда, делать руками (и, скорее всего, на ассемблере). Но это фигня и мелочи.
ZAM>Хотя через него, вопщим, решение и нашлось. Я на каждой итерации алгоритма, который я родил
, проверяю можно-ли сравнить промежуточные дроби твоим и Ларик'а алгоритмом, как обе дроби становятся нужного "формата" так всё... ZAM>Правда я пока не решил что быстрее: тупо до конца идти без проверок на возможность сравнить перекрестным умножением; или проверки делать, но избавиться от нескольких лишних итераций. Вообще можно посчитать сколько максимум итераций будет, но правда их много выходит, но правда в редких случаях, а обычно остатки от деления уменьшаются очень быстро.
Ещё быстрее сделать тупо проверку двух double дробей, и только если их разность слишком подозрительно мала, — начать упражнения.
Кстати, насколько реальна проблема сравнения близких дробей?
Может быть, ты несколько опережаешь события?
Здравствуйте, ZAMUNDA, Вы писали:
ZAM>Надо сравнить две дроби, каждая задана парой целых (ну там бабло вообще, но в копейки переведу для простоты). К общему знаменателю приводить никак, т.к. переполнение случается. Сравнивать через float не всегда сработает, т.к. разность меньше alpha может быть. Нужно только оценку — что больше. Чёт голову ломаю... всё никак. Готового алгоритма не нашёл.
Посмотрите http://en.wikipedia.org/wiki/Continued_fraction
Суть в том, что дроби записываются в виде ряда этих коэффициентов (a0+1/(a1+1/(a2+1/...))) и потом эти коэффициенты просто сравниваются. даже не обязательно раскладывать дроби до конца, можно сравнивать пошагово.
Алгоритм очень простой, пишите если что-то не ясно будет.
Здравствуйте, dilmah, Вы писали:
ZAM>>А твой от нулей в параметрах валится по DbZ :) ... правда как и мой :(
D>ну 0/0 это некорректная дробь, такой не бывает, поэтому можно и не обрабатывать :shuffle:
ну это ж не деление на ноль, а это неопределённость, а валится код с ошибкой 'деление на ноль'. А обманывать нехорошо! К томуже деление на ноль, как ты видишь, там вообще не считается бякой, а просто A/0 > B/C и A/0 = B/0.
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
SP>Посмотрите http://en.wikipedia.org/wiki/Continued_fraction SP>Суть в том, что дроби записываются в виде ряда этих коэффициентов (a0+1/(a1+1/(a2+1/...))) и потом эти коэффициенты просто сравниваются. даже не обязательно раскладывать дроби до конца, можно сравнивать пошагово. SP>Алгоритм очень простой, пишите если что-то не ясно будет.
ну собственно, и самый первый ответ SergH, и ряд приведенных в дальнейшем исходников основаны именно на этом принципе: сравнение целых частей и дальнейшее "переворачивание". Только никто явно не упомянул цепные дроби.
Это здорово вообще, не знаю как для других, но для меня цепные дроби были какой-то эзотерикой, непонятно откуда они брались. Теперь они стали гораздо ближе.
Думаю с педагогической точки зрения было бы очень здорово давать задачу топистартера перед тем как рассказывать о цепных дробях.
Здравствуйте, Кодт, Вы писали:
ZAM>>Ну эт ты реализовал вариант Ларик'а. К>Как мне кажется, — нет. Ларик предлагал какую-то химию с уточнением дробей, итерационный алгоритм. (Я не очень вдумывался в него, если честно).
Извини опечатался, это vmpire предложил.
К>А я предлагаю за один приём. К>То есть, int у тебя 64-битный? Ну возьми 128-битный longint. К>Умножение придётся, правда, делать руками (и, скорее всего, на ассемблере). Но это фигня и мелочи.
Т.е. прощще через класс "большое число" и умножить и сравнить. Подумаю... спасиб.
К>Ещё быстрее сделать тупо проверку двух double дробей, и только если их разность слишком подозрительно мала, — начать упражнения.
Спасибо. Попробую.
К>Кстати, насколько реальна проблема сравнения близких дробей? К>Может быть, ты несколько опережаешь события?
Да, проблема реальна. Я ещё озаботился разложением этим, чтоб в БД засунуть этот алгоритм, чтоб сортировать. Поэтому и думаю над подсчётом количества итераций, когда уж точно DB::FLOAT сработает.
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков