はじめに
巷では、フィボナッチ数の計算がお手軽なベンチマークとして扱われているようです。フィボナッチ数の計算方法を調べると、とても遅いアルゴリズムが多数ヒットしてしまいます。
このままでは、フィボナッチ数を高速に計算したい人が途方にくれたり、この程度の計算量だと勘違いするかも知れません。なので、フィボナッチ数を高速に計算するアルゴリズムを紹介することにしました。
ビネの公式
フィボナッチ数とは、フィボナッチ数列のn項目の数$F_n$を指し、一般項は以下の式で表すことができます。
$$F_n = \frac{\phi^n - \bar{\phi}^n}{\sqrt{5}} \tag{1} $$$$
\phi = \frac{1 + \sqrt{5}}{2}, \bar{\phi} = \frac{1 - \sqrt{5}}{2} \tag{2}$$
上記の式はビネの公式と呼ばれています。
気が早い人は、下記のように式をそのままプログラミングに突っ込んでしまうかも知れませんね。
def fib(n)
sqr5 = Math.sqrt(5)
phi = (1 + sqr5) / 2
phi_conj = (1 - sqr5) / 2
(phi**n - phi_conj**n) / sqr5
end
実は$n\geq0$ならば$\bar{\phi}$はいらなくて、以下のように書けます。
def fib(n)
sqr5 = Math.sqrt(5)
phi = (1 + sqr5) / 2
(phi**n / sqr5).round
end
細かい誤差を気にしないのであれば上のプログラムが最速かも知れません。ところが、double型の精度は約15桁程度しかないため、nが大きくなると誤差が発生してしまいます。
例えば、$F_{100} = 354224848179261915075$ですが、このプログラムだと$354224848179263111168$となって上位14桁しか合っていません。
誤差なく高速に計算するためには、ひと工夫が必要というわけです。
同伴フィボナッチ数列と漸化式
ビネの公式に登場した$\phi,\bar{\phi}$ですが、2つの整数$F_n,L_n$を用いて以下のように書けます。
$$2\phi^n = L_n + F_n\sqrt{5} \tag{3} $$$$
2\bar{\phi}^n = L_n - F_n\sqrt{5} \tag{4}$$
ここで、$F_n$はおなじみのフィボナッチ数列、$L_n$はフィボナッチ数列の同伴数列です。
$L_n$をリュカ数と呼ぶこともありますが、リュカ数列と紛らわしいので、ここでは同伴フィボナッチ数列と呼びましょう。
今まで得られた式をごちゃごちゃ式変形することで、6個の漸化式が得られます。
式変形
(3)より
$$ 2(L_{2n} + F_{2n}\sqrt{5}) = L_n^2 + 5F_n^2 + 2L_nF_n\sqrt{5} \tag{5} $$$$
2L_{2n} = L_n^2 + 5F_n^2 \tag{6} $$$$
F_{2n} = L_nF_n \tag{7} $$
(2)より
$$ \phi\bar{\phi} = -1 \tag{8} $$
(3)(4)より
$$ L_n^2 - 5F_n^2 = 4\phi^n\bar{\phi}^n = 4(-1)^n \tag{9} $$
(6)(9)より
$$ L_{2n} = L_n^2 - 2(-1)^n \tag{10} $$
(2)(3)(8)より
$$ L_{n + 1} + F_{n + 1}\sqrt{5} = \frac{L_n + 5F_n + (L_n + F_n)\sqrt{5}}{2} \tag{11} $$$$
L_{n - 1} + F_{n - 1}\sqrt{5} = -\frac{L_n - 5F_n + (-L_n + F_n)\sqrt{5}}{2} \tag{12} $$$$
L_{n + 1} = \frac{L_n + 5F_n}{2} \tag{13} $$$$
F_{n + 1} = \frac{L_n + F_n}{2} \tag{14} $$$$
L_{n - 1} = \frac{-L_n + 5F_n}{2} \tag{15} $$$$
F_{n - 1} = \frac{L_n - F_n}{2} \tag{16} $$
(7)(10)(14)より
$$ F_{2n + 1} = L_nF_{n + 1} - (-1)^n \tag{17} $$
(14)より
$$ L_{n + 1} = 2F_{n + 2} - F_{n + 1} \tag{18} $$
(15)(18)より
$$ F_{n + 2} = -L_n + 3F_{n + 1} \tag{19} $$
(14)より
$$ F_n = -L_n + 2F_{n + 1} \tag{20} $$
(19)より
$$ L_{n - 1} = 3F_n - F_{n + 1} \tag{21} $$
くぅ〜疲れましたw
$$ L_{2n} = L_n^2 - 2(-1)^n \tag{10}$$$$
F_{2n + 1} = L_nF_{n + 1} - (-1)^n \tag{17} $$$$
F_{n + 2} = -L_n + 3F_{n + 1} \tag{19} $$$$
L_{n + 1} = 2F_{n + 2} - F_{n + 1} \tag{18} $$$$
F_n = -L_n + 2F_{n + 1} \tag{20} $$$$
L_{n - 1} = 3F_n - F_{n + 1} \tag{21} $$
フィボナッチ数を高速に計算する
後は以下の様に漸化式を使い分けるだけです。
def fib(n)
fib_intr(n - 1)[0]
end
def fib_intr(n)
return 1, 2 if n.zero?
if n.even?
n_half = n / 2
f, l = fib_intr(n_half)
pow_m1 = (-1)**n_half
l2 = l*l - 2 * pow_m1
f2 = f * l - pow_m1
elsif (n % 8) == 7
f, l = fib_intr(n + 1)
f2 = 2 * f - l
l2 = 3 * f2 - f
else
f, l = fib_intr(n - 1)
f2 = 3 * f - l
l2 = 2 * f2 - f
end
[f2, l2]
end
計算量
浮動小数点を使用した誤差のあるプログラムの計算量は$O(1)$になると思います。検証はしてない。
整数演算のプログラムは、乗算の計算量を$O(n\log^2(n))$と仮定して$O(n\log^3(n))$くらいになると思います。
最速のケースでは、nが２のべき乗+1のとき$\log_2(n)$あたり大きな数の乗算が2回、小さい定数の加算が2回です。
平均的なケースでは、大きな数の乗算が2回、小さい定数の乗算が0.7回、大きな数の加算が0.7回、小さい定数の加算が2回くらいになるんじゃないでしょうか?
測定とかはしません。だって結果を表示する時間$O(n)$の方が長い気がする…。
まとめ
フィボナッチ数列を高速に計算するプログラムをRubyで作成しました。多分このアルゴリズムが一番速いと思います(適当
参考