おしえて　おしえて　セジウィック　さん

C++ algorithm

大昔に買ったはいいものの，全然読んでいなかったSegiwickのAlgorithm in Cをぱらぱら見てて思ったんですが，
日本語第1巻で，ユークリッドの互除法に触れてますよね．


ユークリッドの互除法って，gcd(a, b)なら

n_0 = a mod b
n_1 = b mod n_0
n_2 = n_0 mod n_1
...

とやって，n_xが0になるまで続け，n_(x-1)が最大公約数だっていうアルゴリズムだったと思います．とすると，

unsigned long long int gcd(unsigned long long int u, unsigned long long int v)
{
	if(u<v){swap(u, v); }

	while(v>0)
	{
		u%=v;
		swap(u, v);
	}
	return u;
}

というコードが自然だと思います．


ところがSegiwick本では

unsigned long long int gcd2(unsigned long long int u, unsigned long long int v)
{

	while(u>0)
	{
		if(u<v){swap(u, v); }
		u-=v;
	}

	return v;
}

というように，引き算を使っています．
gcd(a, b)において，a = 3 * b + nであるなら，

n = a-b-b-b
n = a mod b

どちらも同じことなので，結局は同様の操作をしていることになりますが，
ループ回数のカウント，Cのclock関数で性能を比べてみると，

gcd(123456789012345678, 987654321098765432)

Natural (?) way:
STEP: 14
Clock: 0
gcd: 2

Segiwick's way:
STEP: 13720420
Clock: 125
gcd: 2


というわけで前者の圧勝です．一体なぜSegiwickさんはこのような方式を取ったのか？


いや，全然分からないんですけどね．
昔は除算と剰余が非常に遅く，PentiumIIIで35倍くらいの開きがあったとかなかったとかどこかで目にした覚えがあります．
それが理由でしょうか？それにしたってループのステップ数違いすぎな気もします．

もう少し調べてから加筆するかもしれません．