http://en.wikipedia.org/wiki/Binary_GCD_algorithm
このウィキペディアのエントリには、非常に不満足な含意があります。バイナリ GCD アルゴリズムは、標準のユークリッド アルゴリズムよりも 60% も効率的でした。コンピュータ。
さて、さらに 15 年が経過しました... これらの 2 つのアルゴリズムは、今日のハードウェアの進歩とどのように重なり合っているのでしょうか?
バイナリ GCD は、低レベル言語では引き続きユークリッド アルゴリズムよりも優れていますが、Java などの高レベル言語ではその複雑さのために遅れをとっていますか? それとも、現代のコンピューティングではその違いは意味がありませんか?
なぜ私はあなたが尋ねるかもしれないことを気にしますか？今日、たまたま 1,000 億個の処理をしなければなりません :) コンピューティングの時代 (かわいそうな Euclid) に乾杯します。
答えはもちろん「場合による」です。ハードウェア、コンパイラ、特定の実装など、私が忘れていたものに依存します。除算が遅いマシンでは、バイナリ GCD がユークリッド アルゴリズムよりも優れている傾向があります。数年前に Pentium4 で C、Java、およびその他のいくつかの言語のベンチマークを行ったところ、そのベンチマーク全体で、256 要素のルックアップ テーブルを使用したバイナリ gcd は、ユークリッド アルゴリズムを 1.6 倍から 3 倍近く上回っていました。すぐに除算する代わりに、最初に数ラウンドの減算が実行されたときに、より近づきました。数値は覚えていませんが、それでもバイナリはかなり高速でした。
マシンの除算が高速である場合、ユークリッド アルゴリズムは必要な操作が少ないため、状況が異なる可能性があります。除算と減算/シフトのコストの差が十分に小さい場合、バイナリは遅くなります。自分の状況でどちらが優れているかは、自分自身をベンチマークして調べる必要があります。