Допустим, у нас имеется рациональное число, заданное дробью, причем не десятичной, а простой, с числителем и знаменателем (чтоб я еще помнил, как это называется). Предположим, что дробь уже приведена к несократимому виду.
Далее. Пусть эта дробь у нас очень "кривая", т.е., числитель и знаменатель выражаются очень большими числами. Допустим, 35740237 / 679064484.
Задача. При условии, что задан некий верхний предел для знаменателя, подобрать дробь, максимально близкую к исходной, но со знаменателем, не превышающим этого предела.
Поясню. Это СОВСЕМ не то же самое, что десятичное округление. Так, для вышеприведенного примера, если мы зададим верхним пределом, скажем, 1000, то рациональным округлением будет число 1 / 19 (при этом погрешность по модулю составит 1 / 679064484). Десятичным же округлением будет 0,053, что примерно на 250180 / 679064484 дальше от исходной дроби, нежели рациональное 1/19.
Собственно, вопрос. Существует какой-то алгоритм решения такой задачи?
UPD: нет, в моем случае это никак с работой шифровального отдела не связано.
UPD: брютфорсинг не хочется - для очень больших чисел может быть дорого, да и пищи для ума в нем нет.
Похоже,
ответ.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
dedm.livejournal.com
