我有许多有理数的集合，每个有理数的分子和分母都存储为一个大（数百或数千位）无符号整数。我希望能够有效地测试a/b集合中的任何给定有理数是否等于集合中的任何其他有理数c/d。
最直接的方法是测试是否a*d == b*c，当然，但我想要比计算完整产品更有效的方法。
关于我的特定用例的一些说明：
我认为这在理论上可能是不可能的，但为了以防万一，把它扔给蜂巢头脑。
第二次尝试；）如果您必须反复检查新数字是否包含集合，则应将相对质数部分存储在有序集合中。集合的比较函数应该首先比较计数器，如果计数器相等，然后再比较分母。比较可以在线性时间内完成，因此在具有M项的有序集中找到一个元素需要O ( N log M ) 步骤。减少一个分数成本O ( N ²)。因此，测试一个数字的包容性需要O ( N ² + N log M ) 步骤，并计算集合O ( MN ²)。
编辑：您可以使用散列集而不是使用排序集或树集，从而将搜索所需的步骤数减少到O ( N ² + N ) = O ( N ²)。
您可以通过比较位长来过滤掉许多不相等的分数对。令l ( a ) = floor(log2( a )) + 1 a的位长。如果a / b = c / d比l ( a ) + l ( d ) = l ( c ) + l ( b )。
当您第一次比较长度和比较产品时，您可以使用它来加快速度，前提是长度之和相等。
如果您已经预先计算了浮点近似值，这对您的情况不会有太大帮助；它可能仍会在管道中节省一些时间（或一些近似值）。
您检查 a、b、c 和 d 的整数值。
有理数相同意味着它们通过原点描述同一条线。
如果c > a，那么它也一定是d > b，否则我们会在右下角的灰色区域；如果 c < a，则相反，它必须是 d < b，否则我们将在左上角的灰色角落。灰色区域没有相等的可能性，如果数字是随机的（即未经过浮点近似过滤），我们将通过 N 2 个bigint 比较排除其中的 N/2 个。
在剩下的 50% 中，我们可以排除一半，注意如果 a > b，那么黑线在第一和第三象限的平分线下方，并且必须是 c > d，否则 C/D 将在平分线的另一边；我们将处于无法平等的顶级橙色部门。相同或 a < b 的情况。所以其他两个 bigint 比较将要检查的数字减少到原来的四分之一；这些可以用浮点数近似，如果它们“几乎相等”，我们就处于需要其他技术的微小红色区域。
您还可以通过观察对于任何 k 来扩展此方法，a 到 k b 的关系必须与 c 和 k d 之间的关系相同，以便 a/b 和 c/d 相等；如果 k 是 2 的整数幂，则允许进行多种可能的优化。
（当然，在某些时候，这样做的成本会超过a*d==b*c测试的成本）。
