Раунд с фиксированной точкой рационально к более узкому знаменателю
У меня есть (скажем, неотрицательное) рациональное число, выраженное как отношение двух целых a/b, где 0 <= a < 2^m а также 0 < b < 2^n, Я хотел бы округлить это к меньшему представлению только p биты в знаменателе; найти наибольшее число c/d такой, что c/d <= a/b, где 0 < d < 2^p,
Пример: если m=3, n=4, p=2Я хотел бы округлить 4/7 до 1/2, а также 5/7 до 2/3,
Моим первым импульсом было смещение знаменателя вправо n-p, добавив 1, если 1 был удален, и сдвиньте вправо числитель на ту же величину. Это гарантированно даст результат меньше a/b, но это не гарантирует оптимальности результатов. Например, 3/1 раунды в 2/1,
В идеале я хотел бы сделать это без деления или модуля, но я подозреваю, что это может быть непрактично. m, n, а также p может столкнуться с сотнями, и это будет во внутреннем цикле, так что я бы хотел что-то невероятно быстрое.