Здравствуйте, 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) Козьма Прутков
Перекуём баги на фичи!
