Erlangでフィボナッチ数列求めるやつを書いてみた。

1週間ぶりくらいの更新になります。

Orisanoです。最近Erlangと戦っています。
Sortを書いてみたの方はちょっと時間かかっちゃって更新できないので、
何気なく書いたフィボナッチ数列を求める記事で間を持たせたいと思います。

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N - 1) + fib(N - 2).

とまあ最初こういう実装をしたらfib(100)ですらまともに帰ってこない。。。。(悲しみ
ま、当然ですよね。O(2^n)くらいになるのかな・・・自信ない。

追記:
ついでに、末尾最適化したコードも書きました

tailfib(0) -> 0;
tailfib(1) -> 1;
tailfib(N) -> tailfib(N, 0, 1).
tailfib(2, P2, P1) -> P2 + P1;
tailfib(N, P2, P1) -> tailfib(N - 1, P1, P2 + P1).

追記終了

なんかこのままじゃ悔しかったので
いろんなサイトを参考にしつつ、

logfib(0) -> 0;
logfib(1) -> 1;
logfib(2) -> 1;
logfib(N) when N rem 2 =:= 0 ->
	Res1 = logfib(N div 2 + 1),
	Res2 = logfib(N div 2),

	Res2 * (Res1 * 2 - Res2);

logfib(N) ->
	Res1 = logfib(N div 2 + 1),
	Res2 = logfib(N div 2),

	Res1 * Res1 + Res2 * Res2.

O(log n)で求めるコードを書いてfib(1000000)まではストレスなく
表示までしてくれるコードになりました。
10000000でも求めてはくれるのだが、表示にものすごい時間がかかる。

一応Erlangのプロセス辞書というものを使ってメモ化的なこともやってみました。

logfib(0) -> 0;
logfib(1) -> 1;
logfib(2) -> 1;
logfib(N) ->
	Memo = get(N),
	if 
		Memo =:= undefined ->
			Res1 = logfib(N div 2 + 1),
			Res2 = logfib(N div 2),
	
			if
				N rem 2 =:= 0 ->
					Res = Res2 * (Res1 * 2 - Res2);
				true ->
					Res = Res1 * Res1 + Res2 * Res2
			end,
			put(N, Res);
		true ->
			Res = Memo
	end,
	Res.

今書いてるのが、プロセスを作って並列化するコードなのですが、
Erlangの強みを生かしたコードが書けるといいなって感じです。

今回はここまでにしたいと思います。
ではでは