高效检测有理数是否相等

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

最直接的方法是测试a*d == b*c是否当然，但我希望比计算完整产品更有效。

在我的具体使用情况的一些注意事项：

的对，我会测试实际上已经等于（因为我已经预先计算，并通过他们的浮点近似值第一比较它们的可能性很大），所以如果他们不平等，那么早出来并不会节省我很多时间。
我很喜欢为每个数字预先计算额外数据，但每个数字只会用于少数比较，所以昂贵的预计算（例如素因子分解）可能不值得。
偶尔的假阴性会很好，但误报不会。

我想这可能是理论上是不可能的，但为了以防万一把它扔出去的蜂群思维。

来源

2016-11-21 Sneftel

普通的方法是将归一化A/B为（a/GCD（A，B））/（B/GCD（A，B））。为什么它不适合你？ – deniss

@deniss因为计算两个大数字的GCD是相当昂贵的操作。 – Sneftel

什么是您的数据大小和速度要求？ GMP为GCD提供了[一些不错的优化算法]（https://gmplib.org/manual/Subquadratic-GCD.html#Subquadratic-GCD） – deniss

通过比较比特长度，可以筛选出许多不相等的分数对。让升（一个）=地板（LOG2（一个））+ 1所述的一个比特长度。如果一个/b = Ç/d比升（一个）升（d）=升（Ç）升（b）。

只有在长度总和相等的情况下，当您首先比较长度并比较产品时，您可以将其用于加速。

来源

2016-11-28 17:49:11 clemens

正如我所提到的，匹配的可能性很高，因为我已经在做一个近似检查，所以像这样的早期检查并不能节省任何额外的时间。 – Sneftel

但是计算近似值应该比比较长度慢得多。 – clemens

第二次尝试;）如果您必须重复检查新数字以设置包含，则应将相对素数部分存储在有序集合中。该组的比较功能应首先比较计数器，如果计数器相等，则比较分母。该比较可以在线性时间内完成，并且因此找到在有序集与中号项的元素需要ø（Ñ日志中号）步骤。减少零碎成本O（N²）。因此，测试多个用于容纳需要ø（ñ² + Ñ日志中号）步骤，并且计算该组ø（MN²）。

编辑：代替使用排序或树组，则可以使用一个散列集这减少了所需的数目的步骤，用于搜索到ö（Ñ²+ Ñ）= Ô（ñ²）。

来源

2016-11-28 20:16:26 clemens

正如我所提到的，由于前期的GCD成本（很好，实际上是扩展的欧几里德，但相同的差异），减少分数会降低性能。 – Sneftel

对于预先缩减，您不需要_extended_ GCD。更简单的计算不会降低复杂度，但会减少实际运行时间。我会做预计算没有近似值，因为我认为减少会给你更多的灵活性，而不减少你不能找到一个有效的算法来解决你的问题。 – clemens

如果您已经预先计算了浮点近似值，这对您的情况不会有很大的帮助;它仍然可以节省一些时间（或一些近似值）。

您检查a，b，c和d的整数值。

有理数是相同的表示它们描述通过原点的同一条直线。

如果c> a，那么它也必须是d> b，否则我们会在右下角的灰色区域;如果C <一个，相反，它必须是d < B，否则我们将在左上方的灰色角落。灰色区域没有平等的可能性，并且如果该数字是随机的（即，不是浮子近似过滤），我们已经排除其中N/2用N 2 ^BIGINT比较。

剩余的50％中，我们可以通过注意到如果a> b，那么黑线在第一和第三象限的平分线之下并且它必须是c> d，否则C/D将在平分线的另一侧;我们将成为顶级的橙色部门，不可能实现平等。相同的还是一个< b的情况。因此，另外两个bigint比较将检查的数量减少到原来的四分之一;这些可以近似为浮点数，如果它们“几乎相等”，我们就在需要其他技术的微小红色区域。

你也可以通过观察任何k，扩展这个方法，a和k的关系必须与c和k之间的关系相同，对于a/b和c/d是相等的;如果k是2的整数次幂，那么允许几种可能的优化。

（在某些情况下，这当然会超过a*d==b*c测试的成本）。

来源

2016-12-01 00:05:11 LSerni

高效检测有理数是否相等

回答

相关问题