ak備忘録

レガシーブログ

累乗を求めるプログラムの速度計測

今日たまたま累乗の計算をすることがあったので、
ちょっと累乗計算のアルゴリズムについて調べてみた。

そしたら、このような高速な累乗計算のアルゴリズムがあるようだった。

http://d.hatena.ne.jp/kazu-yamamoto/20090223/1235372875

単純な累乗計算より、
この方法の方がO(n)→O(log2(n))になるから速いようだ。

ただ、ちょっと気になる点があった。

最後の美しいアルゴリズムについてのところだが、
これ再帰を使ってないか?

というわけで、早速計測してみることにした。

テストプログラム全文

#include <iostream>
#include <time.h>

using namespace ::std;

//	速度計測用タイマー
class	Timer
{
public:
	Timer()
	{
		m_start_time = clock();
	}

	~Timer()
	{
		clock_t now_time;
		now_time = clock();

		cout << "time = " << now_time - m_start_time << endl;
	}

private:
	clock_t m_start_time;
};

//	超単純	for版
int test_pow1(int _x, int _n)
{
	int ret = _x;
	for(int i=1; i<_n; ++i)
	{
		ret *= _x;
	}
	return ret;
}

//	超単純	再帰版
int test_pow2(int _x, int _n)
{
	if(_n == 1) return _x;
	return _x * test_pow2(_x, _n - 1);
}

//	高速らしい版	再帰版
int test_pow3(int _x, int _n)
{
	if(_n == 0)
	{
		return 1;
	}
	else if((_n % 2) == 0)
	{
		return test_pow3(_x * _x, _n >> 1);
	}
	else
	{
		return _x * test_pow3(_x, _n - 1);
	}
}

//	高速らしい版	for版
int test_pow4(int _x, int _n)
{
	int ret = 1;
	while(0 < _n)
	{
		if((_n % 2) == 0)
		{
			_x *= _x;
			_n >>= 1;
		}
		else
		{
			ret *= _x;
			--_n;
		}
	}
	return ret;
}


int main()
{
	int result = 0;

	cout << "単純forで累積" << endl;
	{
		Timer t;
		for(int i=0; i<100; ++i)
		{
			for(int k=0; k<100000; ++k)
			{
				result = test_pow1(2, 15);
			}
		}
	}
	cout << "result = " << result << endl;

	cout << "単純再帰で累積" << endl;
	{
		Timer t;
		for(int i=0; i<100; ++i)
		{
			for(int k=0; k<100000; ++k)
			{
				result = test_pow2(2, 15);
			}
		}
	}
	cout << "result = " << result << endl;

	cout << "速いらしいアルゴリズムで累積	再帰版" << endl;
	{
		Timer t;
		for(int i=0; i<100; ++i)
		{
			for(int k=0; k<100000; ++k)
			{
				result = test_pow3(2, 15);
			}
		}
	}
	cout << "result = " << result << endl;

	cout << "速いらしいアルゴリズムで累積	for版" << endl;
	{
		Timer t;
		for(int i=0; i<100; ++i)
		{
			for(int k=0; k<100000; ++k)
			{
				result = test_pow4(2, 15);
			}
		}
	}
	cout << "result = " << result << endl;

	return 0;
}

↓↓その結果↓↓

【2の15乗を千万回】

単純forで累積
time = 561
result = 32768
単純再帰で累積
time = 3447
result = 32768
速いらしいアルゴリズムで累積 再帰
time = 1919
result = 32768
速いらしいアルゴリズムで累積 for版
time = 359
result = 32768

timeを見ると、

高速累積for版 > 単純for > 高速累積再帰版 > 単純再帰

の順で速い。
もちろん実行環境によって若干異なるかもしれないので、その辺はご了承ください。

思っていたとおりだが、再帰版は遅い。
プログラムにおいて関数のcallは思っているより重い処理だ。

もし、どうしても高速化したいプログラムなどがある場合は、
関数をインライン化するといった手法をとったりもするが、
それは単純に関数を展開することでcallをなくすためだったりする。

せっかく、こんなに良いアルゴリズムがあるのに
再帰を使ってしまうことで台無しにするのはよくない。

美しいプログラムが必ずしも速いとは限らない、ということは言えると思う。


ちなみに、2の2乗で計測するとこうなった。

【2の2乗を千万回】

単純forで累積
time = 281
result = 4
単純再帰で累積
time = 452
result = 4
速いらしいアルゴリズムで累積 再帰
time = 717
result = 4
速いらしいアルゴリズムで累積 for版
time = 265
result = 4

timeを見ると、

高速累積for版 > 単純for > 単純再帰 > 高速累積再帰

の順番で速い。
高速累積は奇数、偶数判定が入るので乗数が小さいと逆にネックになりえるようだ。


とはいえ、高速累積for版は安定して速い。
使うなら高速累積for版を使うことをここではオススメしようと思います。

P.S.
もっと良いアルゴリズムがあったら教えてください!

----追記!(2013/4/27)----

末尾再帰による最適化というのを初めて知りました!
というわけで、末尾再帰の最適化の形に変更してみることにしました。

kazu-yamamotoさん、ご指摘ありがとうございました!

末尾再帰の最適化バージョン

//	超単純 再帰版
inline int __test_pow2(int _x, int _r, int _n)
{
	if(_n == 0) return _r;

	return __test_pow2(_x, _r * _x, _n - 1);	//末尾再帰最適化
}
inline int test_pow2(int _x, int _n)
{
	return __test_pow2(_x, 1, _n);
}
//	高速らしい版 再帰版
inline int __test_pow3(int _x, int _r, int _n)
{
	if(_n == 0)
	{
		return _r;
	}
	else if((_n % 2) == 0)
	{
		return __test_pow3(_x * _x, _r, _n >> 1);	//末尾再帰最適化
	}
	else
	{
		return __test_pow3(_x, _r * _x, _n - 1);	//末尾再帰最適化
	}
}
inline int test_pow3(int _x, int _n)
{
	return __test_pow3(_x, 1, _n);
}

末尾再帰の最適化のため引数を1つ追加しています。
その引数は必ず1になるのでインライン関数で隠すようにしてみました。

その結果です。
今回はReleaseビルドでコンパイルを行いましたので最適化ありになっています。

ただ、上のプログラムを単にReleaseビルドしただけでは
大量のfor分が最適化されてしまいちゃんと千万回回らないので
result変数にvolatileを指定します。

最適化前(Releaseビルド版)

単純forで累積
time = 15
result = 32768
単純再帰で累積
time = 359
result = 32768
速いらしいアルゴリズムで累積 再帰
time = 203
result = 32768
速いらしいアルゴリズムで累積 for版
time = 0
result = 32768

最適化後(Releaseビルド後)

単純forで累積
time = 15
result = 32768
単純再帰で累積
time = 109
result = 32768
速いらしいアルゴリズムで累積 再帰
time = 156
result = 32768
速いらしいアルゴリズムで累積 for版
time = 0
result = 32768

うおぉ!!再帰が速くなっている!!

再帰って速くする方法があったんですね!
ちょっと驚きでした!

もっとうまいプログラムの書き方などありましたらご指摘ください!