弱小PHPerの憂鬱

http://d.hatena.ne.jp/satosystems/20121228/1356655565
こちらのサイト、多種の言語でフィボナッチ数F38を求めています。
PHPは85.417秒と、残念ながらかなり遅い方です。
これを最適化してみましょう。

<?php
	
	// by satosystems
	// http://d.hatena.ne.jp/satosystems/20121228/1356655565
	function fib1($n){
		if ($n < 2){ return $n; }
		return fib1($n - 2) + fib1($n - 1);
	}
	
	// by Dan Kogai
	// http://blog.livedoor.jp/dankogai/archives/50958771.html
	function fib2($n){
		if($n < 2){return $n;}
		return fib2_sub(1, 1, $n);
	}
	function fib2_sub($a, $b, $c){
		if ($c <= 2){ return $a; }
		return fib2_sub($a+$b, $a, $c-1);
	}
	
	// by NurseAngel
	function fib3($n){
		$fib0 = 0;
		$fib1 = 1;
		$ret = 0;
		for($i=0; $i<$n; $i++){
			$ret = $fib1;
			$fib1 = $fib0 + $fib1;
			$fib0 = $ret;
		}
		return $ret;
	}
	
	// by C言語による最新アルゴリズム事典
	function fib4($n){
		return floor( pow((1+sqrt(5))/2, $n) / sqrt(5) + 1/2 );
	}

関数	処理時間	F(38)の値
fib1()	34.29149秒	39088169
fib2()	0.00005秒	39088169
fib3()	0.00002秒	39088169
fib4()	0.00002秒	39088169

fib1はフィボナッチ数列の定義そのものです。
何も考えずに実装したらこうなることでしょう。
しかしこちらは、計算時に自分自身を2回呼び出します。
つまり引数が1増えるにつれ、fib1()を呼び出す回数がおよそ2倍になります。
計算量はO(2ⁿ)となり、効率の非常に悪いオーダーです。
もうfib1(100)なんて求めようとすると、反応がなくなってしまいます。


fib2は少々わかりにくいですが、上から順ではなく下から計算しています。
fib2_sub()の1回目に与えている1,1という引数は、順にF2、F1の計算結果です。
あとはfib2_sub()の再帰呼び出しで計算します。
fib2_sub()の2回目の引数はF2+F1つまりF3、F2、数値の37です。
fib2_sub()の3回目の引数はF3+F2つまりF4、F3、数値の36です。
…と順に下っていき、最後のfib2_sub()の引数はF38、F37、数値の2となります。

これによって引数が1増えても、fib2()の呼び出しは1回しか増えません。
計算量はO(n)となり、劇的に改善どころかとんでもない速度になりました。
というかこの時点で早すぎてfib2(38)では計算する意味がないレベル。
fib2(1000)でも余裕で計算可能です。


正直既にこの時点で終わりでいいんじゃね、という気もしますが、よく見てみたらfib2_sub()の再帰って実は計算には全く使わず、ループ回数をカウントしてるだけです。
カウントしてるだけならfor()でいいだろう、ということでfib3()です。
こちらも単純に下から足してるだけで、やってることはfib2()とほぼ同じです。
ただ再帰の関数呼び出しが無くなったせいか、速度もさらに上がっています。

ぱっと見ループを1回削れそうな気がしますが、削ろうとするとfib3(0)あたりの計算がうまくいかないのであえてこうしています。
ifで分岐すると却って遅くなるようでした。


さて、実は再帰もループも使わずにフィボナッチ数を一発で求める公式が存在します。

Fn = ( φⁿ - (-φ)^-n ) / sqrt(5) = [φⁿ / sqrt(5) + 1/2 ]
ただしφは黄金比

といってもn乗とかの計算は出てきますけどね。
ルートとか割り算とか入ってるくせに計算すると必ず自然数になるとか意味がわからない。
計算量はO(1)でいいのかな、これ？

早すぎてfib3()と違いが分かりませんが、F2000とかを求めようとするとfib4()のほうが早くなるようです。
どちらにしろ0.1秒以下なので実用上はほとんど変わらないレベルですが。
まあともかく、結論としては、フィボナッチ数を求めるアルゴリズムでfib1()だけを書いてるサイトは投げ捨ててしまえ、ってことでいいですかね。