检查两个给定数字是否互反的最快方法是什么？

有没有更快的方法？

2009-09-27 Lazer

欧几里得算法（计算gcd）非常快。当从[1, n]随机统一绘制两个数字时，计算其gcd的平均步数为O(log n)。每个步骤所需的平均计算时间是数字的二次方。

还有一些替代品的性能稍好些（即每个步骤在数字位数上都是次级的），但它们只对非常大的整数有效。例如参见On Schönhage's algorithm and subquadratic integer gcd computation。

2009-09-27 11:54:36 jason

我想评论一下，测算算术算法的复杂性时不考虑算术运算的成本，这有点粗糙。 – 2009-09-27 12:03:11

当两个数字是斐波那契数列中的连续条目时，最差步数＃也是O（log n）。 – 2009-09-27 13:26:31

@Pavel Shved：我确实考虑了成本。比照“每个步骤所需的平均计算时间是数字的二次方”。 – jason 2009-09-27 19:16:15

如果您使用的分部/余料明显比班次更贵，请考虑使用binary GCD。

2009-09-27 13:31:48

谢谢，有趣的阅读 – 2009-09-27 13:39:48

是的，那里有一篇很好的文章。 – Lazer 2009-10-07 09:54:12

刚刚在f＃中实现了它，它的速度比传统Euclid的GCD快了一倍以上，所以无法给出确切的数字，因为有其他代码会影响我的测量结果，但其速度> 2倍。很好找Jason。 – gatapia 2011-08-04 02:33:32

回答