計算量が減らない!?（フィボナッチ数列の公式の変形）
フィボナッチ数列の公式は下記のようなものだと言う。
で、これを、無理数、ありていに言えばを使わず、整数を扱うだけで計算できるか試みた*1。
その結果、このように変形できた。
(
)
(
)
(
)
1〜3までを計算すれば、フィボナッチ数列が出ると言うことなんだが、1〜3のどれもがナイーブに実装すると計算量問題に引っかかるような式になっている。こんなことするくらいなら、フィボナッチ数列自体をナイーブに実装してメモイゼーションした方が3倍ほどマシであろうに。なんともはや。
1〜3をさらに公式化できればオーケーなんだろうけど、えーと、もう高校数学なんか忘れたなあ。どうやってやるんだっけ？
http://d.hatena.ne.jp/maehara/20071201/1196497753
こちらでも指摘されているが。
追記：乗算回数も同じくらい．従って上と計算量はやはり変わらない．
結局、公式を使ったとしても乗算が含まれるので、そこで計算量問題に引っかかると言うのは（現時点で）正しいらしい。
これをどうにかしない限りは、計算量は減らせないっぽい。3番の式なんかはってやってしまえば、最適化された組込関数が使える分早くなるだろうけど、たかが知れてるだろうしなあ。
なんかいいアイデアはないのか。
