バイナリGCDアルゴリズム

Question

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

このWikipediaのエントリは非常に不満な意味を持っている：バイナリGCDアルゴリズムは、一度に最大60％、より効率的な標準ユークリッドアルゴリズムよりだったが、通り1998年の後半にKnuthは現代のコンピューターで効率が15％向上したと結論づけました。

さらに15年が経過しました。今日、これらの2つのアルゴリズムは、ハードウェアの進歩によってどのようにスタックしていますか？

バイナリGCDは低レベル言語でユークリッドアルゴリズムの性能を引き続き上回りますが、Javaなどの高水準言語の複雑さのために後退しますか？それとも、現代コンピューティングの違いは何ですか？

なぜ気になるのですか？私は今日、これらの1000億のように処理しなければならないことが起こりました:)コンピューティングの時代（貧弱なユークリッド）に生きるための乾杯です。

Answer 1

答えはもちろん「それは依存する」です。ハードウェア、コンパイラ、具体的な実装、私が忘れてしまったものに依存します。遅い除算を持つマシンでは、バイナリGCDはユークリッドアルゴリズムより優れている傾向があります。数年前にC、Javaなどの言語でPentium4をベンチマークしました。このベンチマークでは、256要素のルックアップテーブルを持つバイナリgcdがEuclideanアルゴリズムを1.6倍から3倍近く上回りました。Euclideanすぐに分割するのではなく、最初に数回の減算が行われたときに、より近くに来ました。私は数字を覚えていませんが、バイナリはまだかなり速かったです。

マシンの分割が速い場合は、ユークリッドアルゴリズムの操作が少なくて済みますので、状況が異なる可能性があります。除算と減算/シフトの間のコストの差が十分に小さい場合、バイナリは遅くなります。どの状況があなたの状況に優れているか、あなたは自分自身をベンチマークすることによって見つけなければなりません。