私は多くの有理数のコレクションを持っており、それぞれの分子と分母は大きな (数百または数千ビット) 符号なし整数として格納されています。a/bセット内の特定の有理数がセット内の他の有理数と等しいかどうかを効率的にテストできるようにしたいと考えてc/dいます。
もちろん、最も簡単な方法は かどうかをテストすることa*d == b*cですが、完全な積を計算するよりも効率的な方法が必要です。
私の特定のユースケースに関するいくつかのメモ：
- 私がテストするペアは、実際に等しい可能性が高いです (私はすでに事前計算を行っており、最初に浮動小数点近似でそれらを比較しているため)、等しくない場合に早期に終了しても、多くの時間を節約することはできません.
- 数値ごとに余分なデータを事前計算しても問題ありませんが、各数値は少数の比較でのみ使用されるため、コストのかかる事前計算 (素因数分解など) はおそらく価値がありません。
- 時折の偽陰性は問題ありませんが、偽陽性はそうではありません。
これは理論的には不可能かもしれないと思いますが、念のため集団精神に投げ出します。