数列として得るフィボナッチ数

記事について

関数型記述なんやらの記事を見て触発されてfizzbuzzなんかを考えたりした流れで、昔フィボナッチ数列のコードで同僚と盛り上がってたなーと思ってフィボナッチ数列のコードについて再考してみたのの記録。
(本稿自体は関数型云々に言及する内容ではないです)

普通に実装

$n$ 番目のフィボナッチ数を得る再帰関数。($n = 10$ の例)

fibonacci = lambda n: n if n<2 else fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10))

同僚は数列として結果を得たかったようなので、数列を得るなら print(list(map(fibonacci, range(1, 11)))) のように引数列のrangeオブジェクトをmapでfibonacciに食わせたり、forでループ回したりすることになる。

しかし、数列の上位からトップダウンで計算していくこの実装の場合、下位のフィボナッチ数を何度も計算するため計算リソースがなんかもったいない気がする。
実際、$n=40$ くらいになると実行完了がだいぶ遅くなる。

当時はググって得た結論がメモ化再帰かなーとか思ってたものの、グローバル配列を用意しておかなければならないのは関数機能としての独立性とかのことを考えると抵抗感もあった。(FPの参照透明性ってこういうことだろうか)

ボトムアップ式

トップダウンが駄目ならボトムアップにすればいいじゃないということで、今回はすんなり別解が浮かんだ。
(大したパラダイムシフトでもないので、当時も発想自体はあったと思うのだけど、多分引数と返却値の取り回しを上手く再帰構造に組み込めなかったのだと思う)

fibonacci = lambda n, v=[0,1]: fibonacci(n-1, v+[v[-1]+v[-2]]) if n > 1 else v[1:]
print(fibonacci(10))

この場合、生の返却値がListオブジェクトで表現される数列なので、フィボナッチ数が欲しければ print(fibonacci(10)[-1]) とする。

Reducerとして書いた方がスッキリするかも？って思ったけど、イテレートアイテムと返却値の型の不一致がそもそもなためあまり変わらなかった。

fibonacci = lambda v, n: v+[v[-1]+v[-2]] if len(v) > 1 else v+[1]
print(reduce(fibonacci, range(1,11), []))

公式による導出

計算量について調べているとフィボナッチ数の公式があるらしく、以下の $F_n$ について解けば $n$ 番目のフィボナッチ数が得られるとのこと。

$$
F_n = \frac{1}{\sqrt{5}}\biggl(;
\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^n - \Bigl(\frac{1-\sqrt{5}}{2}\Bigr)^n
\biggr)
$$

実装すると以下。($n$乗根 = $n$の逆数の累乗)

fibonacci = lambda n: int((((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n)/(5**0.5))
print(fibonacci(10))

これなら時間計算量 $O(1)$ になるということらしい。¹
最初と同じく、数列の解が欲しいならrangeオブジェクトをmapでfibonacciに食わせる。

でも、$n=72$ あたりから誤差が…

$ ./fibonacci-bottomup.py 72   # ボトムアップ式実装
498454011879264
$ ./fibonacci-fomula.py 72     # 公式実装
498454011879265

そもそもこの公式、数学的には整数解が得られるらしく、キャストしなきゃいけない時点で実装間違ってるのか。

時間計算量について

フィボナッチ数列の時間計算量について自力で求めるのが数学力の無い自分には出来なかったので簡単にググった感じ、数列として言及された記事は見当たらなかったが、$n$ 番目のフィボナッチ数を導出する時間計算量は、

$$
O_n\Biggl(\quad
\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^{n-1}
\Biggr)
$$

ということらしいので²、数列版の時間計算量は以下ということ？

$$
O_n\Biggl(\quad
\sum_{i=1}^{n}{\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^{i-1}}
;\Biggr)
$$

実数でみたいなーと思ったので、$n$ をコマンドライン引数で受け取って $O_n$ を得るスクリプトを作成。

fibonacci-sequence-order.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

n = int(sys.argv[1])

order = lambda x: ((1+5**0.5)/2)**(x-1)
print(round(sum(list(map(order, range(1,n+1)))),3))

$1 \leqq n \leqq 10$ までの各々の $O_n$ を導出。

$ seq 1 10 | xargs -L 1 ./fibonacci-sequence-order.py
1.0
2.618
5.236
9.472
16.326
27.416
45.361
74.395
121.374
197.387

参考

http://www.aoni.waseda.jp/ichiji/2012/java-01/java-14-3.html
http://d.hatena.ne.jp/shunsuk/20090220/1235135606

1. 過去これに対して疑問視されたようで、$O(n)$ 説もあったが $O(1)$ で決着したっぽい…？ (参考リンク下段) ↩

2. 簡易的?には $O(2^n)$ ということらしい ↩