Рациональное округление (или как это еще назвать)

[allegecityrat.livejournal.com]

Допустим, у нас имеется рациональное число, заданное дробью, причем не десятичной, а простой, с числителем и знаменателем (чтоб я еще помнил, как это называется). Предположим, что дробь уже приведена к несократимому виду.
Далее. Пусть эта дробь у нас очень "кривая", т.е., числитель и знаменатель выражаются очень большими числами. Допустим, 35740237 / 679064484.
Задача. При условии, что задан некий верхний предел для знаменателя, подобрать дробь, максимально близкую к исходной, но со знаменателем, не превышающим этого предела.
Поясню. Это СОВСЕМ не то же самое, что десятичное округление. Так, для вышеприведенного примера, если мы зададим верхним пределом, скажем, 1000, то рациональным округлением будет число 1 / 19 (при этом погрешность по модулю составит 1 / 679064484). Десятичным же округлением будет 0,053, что примерно на 250180 / 679064484 дальше от исходной дроби, нежели рациональное 1/19.
Собственно, вопрос. Существует какой-то алгоритм решения такой задачи?

UPD: нет, в моем случае это никак с работой шифровального отдела не связано.
UPD: брютфорсинг не хочется - для очень больших чисел может быть дорого, да и пищи для ума в нем нет.

Похоже, ответ.

Comments

[antropovalexey.livejournal.com]

алгоритм можнонаписать - тупой перебор например.

а разве дробь - это рациональное число?

[allegecityrat.livejournal.com]

По определению, рациональное число - это число, представимое в виде дроби, числитель которой является целым числом, знаменатель - натуральным (сиречь, целым положительным).
Тупой перебор в случае чисел такого размера может быть несколько медленным :).
Хочется чего-то более умненького, типа как алгоритм поиска наибольшего общего делителя, например. Если для этого случая такое есть, конечно.

[spamsink.livejournal.com]

Да, существует. Идея алгоритма исходит из того, что для любых дробей a/b и c/d
значение дроби (a+c)/(b+d) будет находиться между значениями двух исходных.
Пусть число, для которого мы ищем приближение - Х.
Берем в качестве двух первых приближений дроби a/b = 0/1 и c/d = 1/0 (бесконечность).
Далее, пока не надоест, сужаем границы вокруг Х:
- вычисляем NEW = (a+c)/(b+d)
- если NEW > X, то c = a+c, d = b+d
- иначе если NEW < X, то a = a+c, b = b+d
- критерий надоедания по вкусу.

[allegecityrat.livejournal.com]

Во, спасибо, это, похоже, то, что надо! Респект!