檢查兩個給定數字是否互反的最快方法是什麼？

有沒有更快的方法？

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

回答