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