有效地检测有理数是相等的

Question

我有许多有理数的集合,每个有的分子和分母存储为一个大的(数百或数千位)无符号整数.我希望能够有效地测试a/b集合中任何给定的有理数是否等于集合中的任何其他有理数c/d.

a*d == b*c当然,最直接的方法是测试是否比计算完整产品更有效.

关于我的特定用例的一些注释:

• 我将测试的对很可能实际上是相等的(因为我已经预先计算并首先通过它们的浮点近似来比较它们),所以如果它们不相等的早期外出将不会为我节省很多时间.
• 我很好地预先计​​算了每个数字的额外数据,但每个数字只会用于少数比较,因此昂贵的预计算(例如素数因子分解)可能不值得.
• 偶尔的假阴性会很好,但误报不是.

我认为这在理论上可能是不可能的,但为了以防万一,将它扔到蜂巢头脑中.

Answer 1

您可以通过比较位长度来过滤掉许多不相等的分数对。令l ( a ) = Floor(log2( a )) + 1 为a的位长度。如果a / b = c / d则l ( a ) + l ( d ) = l ( c ) + l ( b ) 。

当您第一次比较长度和比较产品时，仅当长度之和相等时，才可以使用它来加速。