数学ガールを読むぞぉ 6 - フィボナッチ数列の一般項

前回,フィボナッチ数列の母関数の一般項を求めることが出来たので、

後は、フィボナッチ数列の一般項に向けてゴニョゴニョやるだけっす。

写経中・・・

出来た！！フィボナッチ数列の一般項を手に入れた！！

が・・・Schemeでやると誤差が出てしまう。四捨五入して整数に。という方法もあるけど、

「誤差無しで解く方法がある」

そう。数式処理！！

ということで、今回はCommon Lispで書かれた数式処理ソフトMaxima使います。ハイ。

% maxima
(%i19) F(n):=(1 / sqrt(5)) *
             ((((1 + sqrt(5))/2)^n) -
              (((1 - sqrt(5))/2)^n));
                          1      1 + sqrt(5) n    1 - sqrt(5) n
(%o19)         F(n) := ------- ((-----------)  - (-----------) )
                       sqrt(5)        2                2

(%i23) expand(F(10));
(%o23)                                55

sqrt(5)^3すると、5 * sqrt(5)と分解してくれちゃうので、誤差無しでデカいフィッボナッチ数も求められる。

いやぁ数式処理って凄いっす。記号処理バンザイ。

と思ったけど、

100万以上は辛い。結局2n回の展開作業が必要となってしまうので、反復版と変わらない。

「一般項を求めたって速くなるとは限らない」

ということがわかった。

Schemeでやると浮動小数点の関係で桁落ちが発生してしまうので誤差どころの話ではない事もわかった。√5の計算をずっと後で計算するための案を練らなくては。

まだまだ課題が残るなぁ。