再起もメモも行列も使わないで再起より確実に速いフィボナッチ数列の計算方法

今回はフィボナッチ数列です。本当何やってるんでしょうね

まず、 ${x^2 - x - 1 = 0}$ の解の大きい方を ${ \phi}$ とします
この数は $\phi^2 = \phi + 1$ と考えることができます

また、フィボナッチ数列の第 $n$ 項を ${F_n}$ とします

$n = 0$ の時 $\phi^0 = F_0\phi + F_{-1}$ とすると、
${\begin{align} & (F_n\phi + F_{n-1})\phi \\ =& F_n\phi^2 + F_{n-1}\phi \\ =& F_n(\phi + 1) + F_{n-1}\phi \\ =& F_n\phi + F_n + F_{n-1}\phi \\ =& F_{n+1}\phi + F_n \end{align}}$
であるため、 ${ \phi^n = F_n\phi + F_{n-1}}$ であることが数学的帰納法で証明されます

ここから、
${\begin{align} & F_{a+b}\phi + F_{a+b-1} \\ =& \phi^{a+b} \\ =& \phi^a\phi^b \\ =& (F_a\phi + F_{a-1})(F_b\phi + F_{b-1}) \\ =& F_aF_b\phi^2 + F_aF_{b-1}\phi + F_{a-1}F_b\phi + F_{a-1}F_{b-1} \\ =& F_aF_b\phi + F_aF_b + F_aF_{b-1}\phi + F_{a-1}F_b\phi + F_{a-1}F_{b-1} \\ =& (F_aF_b + F_aF_{b-1} + F_{a-1}F_b)\phi + F_aF_b + F_{a-1}F_{b-1} \\ \end{align}}$
となり、
${F_{a+b} = F_aF_b + F_aF_{b-1} + F_{a-1}F_b}$ と ${F_{a+b-1} = F_aF_b + F_{a-1}F_{b-1}}$ が導けます

また、
${\begin{align} & F_{ka}\phi + F_{ka-1} \\ =& \phi^{ka} \\ =& (\phi^a)^k \\ =& (F_a\phi + F_{a-1})^k \\ =& \sum_{l=0}^{k}{}_k C _l (F_a\phi)^l{F_{a-1}}^{k-l} \\ =& \sum_{l=0}^{k}{}_k C _l (F_l\phi+F_{l-1}){F_a}^l{F_{a-1}}^{k-l} \\ =& \phi\sum_{l=0}^{k}{}_k C _lF_l{F_a}^l{F_{a-1}}^{k-l} + \sum_{l=0}^{k}{}_k C _lF_{l-1}{F_a}^l{F_{a-1}}^{k-l} \end{align}}$
から、
$\displaystyle{F_{ka} = \sum_{l=0}^{k}{}_k C _lF_l{F_a}^l{F_{a-1}}^{k-l}}$ と $\displaystyle{F_{ka-1} = \sum_{l=0}^{k}{}_k C _lF_{l-1}{F_a}^l{F_{a-1}}^{k-l}}$ という式も導けますが、今回はあんまり使いません

今回使うのは、先ほどの式 ${F_{a+b}}$ の $a+b$ に $2a$ を代入した ${F_{2a} = {F_a}^2 + 2F_aF_{a-1}}$ と ${F_{2a-1} = {F_a}^2 + {F_{a-1}}^2}$ です

ここからはRubyでフィボナッチ数列を求める関数を書いていきます

通常のフィボナッチ数列の求め方は他に色々再起でやる例が紹介されているし、とても遅いので割愛します

まず、ビネの公式から近似値を求めて切り捨てるやつです

def fib1 n
  (((1+Math.sqrt(5))/2)**n / Math.sqrt(5) + 0.5).floor
end

公式に当てはめてるだけなのでさほど複雑ではありませんね
ボクのマシンでは第71項目で誤差が生じ始め、第2000項程度でオーバーフローを起こしました

一方、こちらは先程の式を使ったものです

def fib3 n
  f = [1, 0] #F(-1) と F(0)
  n.to_s(2).each_char do |c|
    f = [f[0]**2 + f[1]**2, 2*f[0]*f[1] + f[1]**2] #F(2a)を求め、fに入れる
    f = [f[1], f[0] + f[1]] if c == '1' #その位の数が1ならF(a+1)を求め、fに入れる
  end
  f[1]
end

2進数に直し、その後に10進数に直す時の要領で計算しています(2進数の筆算で検索)
もちろん再起は使っていませんし、メモ(一度した計算を保存)もしていません
ただ、ボクのマシンでは誤差が見たところ生じず、第1000000項目が数秒で求まりました

ベンチマークを取りました
fib2には行列で求める式をいれ、第0項目、第10項目……第1000000項目を各10回求めました(http://qiita.com/mathhun/items/4c117d33028a888f6fcf参照)
ビネの公式は早々に10000でへたった(オーバーフローした)ので、測ってません

                           user     system      total        real
fib2: 0 fib            0.000000   0.000000   0.000000 (  0.000000)
fib3: 0 fib            0.000000   0.000000   0.000000 (  0.000000)
                           user     system      total        real
fib2: 10 fib           0.000000   0.000000   0.000000 (  0.000000)
fib3: 10 fib           0.000000   0.000000   0.000000 (  0.000000)
                           user     system      total        real
fib2: 100 fib          0.000000   0.000000   0.000000 (  0.000000)
fib3: 100 fib          0.000000   0.000000   0.000000 (  0.001001)
                           user     system      total        real
fib2: 1000 fib         0.000000   0.000000   0.000000 (  0.001001)
fib3: 1000 fib         0.000000   0.000000   0.000000 (  0.000000)
                           user     system      total        real
fib2: 10000 fib        0.015000   0.000000   0.015000 (  0.010007)
fib3: 10000 fib        0.000000   0.000000   0.000000 (  0.001000)
                           user     system      total        real
fib2: 100000 fib       0.219000   0.000000   0.219000 (  0.229153)
fib3: 100000 fib       0.016000   0.016000   0.032000 (  0.041026)
                           user     system      total        real
fib2: 1000000 fib      5.484000   0.031000   5.515000 (  5.892934)
fib3: 1000000 fib      1.078000   0.000000   1.078000 (  1.409943)

となりました

fib3がボクの式です

行列のほうが綺麗に解けるけどボクはこっちの式のが速いし好きだなあ

Momota.pw別館

Yuki_noeの進捗状況

再起もメモも行列も使わないで再起より確実に速いフィボナッチ数列の計算方法