二進制GCD算法對歐幾里德的算法在現代計算機

http://en.wikipedia.org/wiki/Binary_GCD_algorithm 二進制GCD算法對歐幾里德的算法在現代計算機

此維基百科條目有一個非常不滿意的含義：二進制GCD算法是在同一時間高達60％，比標準的Euclid算法更高效，但作爲遲到1998年，Knuth得出結論，他的現代計算機的效率只有15％的提高。

那又過了15年......這兩種算法今天如何在硬件方面取得進步？

是否二進制GCD繼續優於歐氏算法低級語言但憔悴的背後原因是它在高級語言如Java的複雜性？或者在現代計算中有什麼不同？

爲什麼我關心你可能會問？我恰好需要今天處理1000億個這樣的東西:)這是一個生活在計算時代（可憐的歐幾里得）的乾杯。

來源

2011-11-19 jkschneider

你可以有一個規範標準測試他們，就像在一個for循環（對於1000例如大小）創建隨機數的列表，然後對所有對數的計算二進制，而在另一個循環計算歐幾里得最大公約數，什麼是問題？國際海事組織，仍然在現代計算機二進制應該是更快的數字更大。 –

我可以，而且這對於特定OS上的特定處理器上的特定語言來說是相當有代表性的。這是一種常見的數字操作，我更加普遍地好奇今天在高性能應用中首選的解決方案。 – jkschneider

如果你今天做100十億，任何時間花在辯論最有效的解決辦法是要花費你更多的時間損失比簡單地執行一個或另一個會一直。 –

答案當然是「看情況」。這取決於硬件，編譯器，具體實現，不管我忘了。在劃分較慢的機器上，二進制GCD的性能優於歐幾里得算法。我在基準幾年前基準它在C，Java和其他一些語言的Pentium4，總體而言，有256元的查找表二進制GCD 1.6和近3之間的歐幾里德的因素擊敗歐幾里德算法靠近而不是立即分開時，首先進行了幾輪減法。我不記得數字，但二進制仍然快得多。

如果機器有快速除法，事情可能會有所不同，因爲歐幾里德算法需要更少的操作。如果劃分和減法/移位之間的成本差異足夠小，二進制將會變慢。在你的情況下哪一個更好，你必須通過標杆來找出自己。

來源

2011-11-19 13:02:23

二進制GCD算法對歐幾里德的算法在現代計算機

回答

相關問題