a/bと の 2 つの整数の比として表される (非負0 <= a < 2^mとしましょう) 有理数を取得しました0 < b < 2^n。p分母にビットのみを使用して、それをより小さな表現に丸めたいと思います。つまり、 、どこでのc/dような最大の数を見つけます。c/d <= a/b0 < 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数百に達する可能性があり、これは内側のループになるため、可能な限り非常に高速なものが必要です。