フィボナッチ数の性質と計算方法 (1) フィボナッチ数
この連載について
フィボナッチ数、リュカ数、そしてそれらを一般化した数列の基本的な性質と、コンピューターにおける計算方法について記述します。
本文
今回は、フィボナッチ数 (Fibonacci numbers) の基本的な性質と、コンピューターにおける計算方法について記述します。
定義
漸化式
$$
~~ a_0=0, a_1=1, \\
~~ a_{n+2}-a_{n+1}-a_n=0 ~~ (n \geq 0)
$$
で定義される数列を、フィボナッチ数列 (Fibonacci sequence) と呼ぶ。
また、フィボナッチ数列に現れる数をフィボナッチ数 (Fibonacci number) と呼ぶ。
なお、添字$n$を負数まで拡張すると、この数列は
$$ \cdots , -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, \cdots $$
となるため、$a_1=0$ ではなく $a_0=0$ と定義しておくとよいです。
また、リュカ数列およびリュカ数という用語との兼ね合いから、フィボナッチ数 (Fibonacci numbers; 複数形) がフィボナッチ数列を表すこともあるようです。
cf.
Lucas sequence - Wikipedia
一般項
フィボナッチ数列の一般項を求めます。
大学受験のときに求め方を習得した人も多いのではないでしょうか。
$$
~~ a_n = \dfrac{1}{\sqrt{5}} (\alpha^n-\beta^n) = \dfrac{1}{\sqrt{5}} (\alpha^n-(-\alpha)^{-n})
$$
ただし、$\alpha=\dfrac{1+\sqrt{5}}{2}, \beta=\dfrac{1-\sqrt{5}}{2}.$
ある実数$\lambda$に対して、数列 $b_n := a_{n+1} - \lambda \, a_n$ を考える。
定義の漸化式において$a_{n+2}, a_{n+1}$を消去して、
$$ ~~ b_{n+1} -(1 - \lambda) b_n + (\lambda^2 - \lambda -1) a_n = 0 $$
$\alpha, \beta$を 2 次方程式 $x^2-x-1 = 0$ の 2 解とすると、$\alpha + \beta = 1, ~ \alpha \beta = -1$ を満たす。
そこで$\lambda = \alpha$と選ぶと、$b_{n+1} = \beta \, b_n$ という形にできる。
このとき$b_n$は等比数列であり、
$$ ~~ b_n = \beta^n \, b_0 = \beta^n $$
さらに$\lambda = \beta$と選んでも同様だから、
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
a_{n+1} - \alpha \, a_n = \beta^n \\
a_{n+1} - \beta \, a_n = \alpha^n
\end{array}
\right.
\end{eqnarray}
$$
したがって、$\alpha:=\dfrac{1+\sqrt{5}}{2}, \beta:=\dfrac{1-\sqrt{5}}{2}$ とすれば、
$$
~~ a_n = \dfrac{\alpha^n-\beta^n}{\alpha-\beta} = \dfrac{1}{\sqrt{5}} (\alpha^n-\beta^n) = \dfrac{1}{\sqrt{5}} (\alpha^n-(-\alpha)^{-n})
$$
$\alpha, \beta$の値はそれぞれ、
$$
~~ \alpha = 1.6180339887 \cdots \\
~~ \beta = -0.6180339887 \cdots
$$
この $\alpha$ は
黄金数 (golden number)
であり、とくに $\varphi:=\dfrac{1+\sqrt{5}}{2}$ で表されることも多いです。
また、$|\alpha|>|\beta|$ より、
$$ ~~ \lim_{n \to \infty} \frac{a_{n+1}}{a_n} = \alpha = \dfrac{1+\sqrt{5}}{2} $$
となります。
比がほぼ$\dfrac{1+\sqrt{5}}{2}$になる整数の組が限りなく連なっているというのは面白い現象です。
フィボナッチ数の計算
上記の一般項は理論上の解ですが、ここではフィボナッチ数をコンピューターで具体的に求める方法をいくつか挙げます。
以下、$n \geq 0$ とします。
一般項から求める
一般項が判明していれば一般項から求める方法が自然に思えますが、コンピューターで計算するとなると事情が異なり、工夫が必要になることがあります。
フィボナッチ数列の一般項には $\sqrt{5}$ が含まれているため、(通常多くの人が使うであろう) 浮動小数点数または 10 進数を利用して計算すると誤差が生じることがあります。
これを整数値に丸めることでフィボナッチ数を得る、という方法がまず考えられます。
しかし、プログラミング言語や $\sqrt{5}$ などの無理数の定数をどのように扱うかにも依存しますが、程度の差はあれ、この方法では$n$が大きくなるにつれて誤差が大きくなり、やがて$0.5$を超えてしまいます。
筆者の実行環境では、$n>70$ で正しくない値となりました。
もし実用化するのであれば、巨大な桁数を扱える数値型を、誤差を評価したうえで利用する必要があります。
なお、二項展開する方法もありそうですが、記述量や計算量でとくに利点がないため、それよりは次の漸化式を使う方法がよいです。
漸化式から求める
フィボナッチ数を整数のまま計算するには、定義の漸化式を用いて順に求めるのが簡単です。
時間計算量は $O(n)$ です。
空間計算量は、途中の値をキャッシュする場合は $O(n)$、キャッシュしない場合は $O(1)$ でできます。
この方法は、プログラミングの練習でよく題材にされます。
C# では次のようなコードでフィボナッチ数列を作れます。
なお、$a_n$の値を符号付き 64 ビット整数で表せる範囲は $n \leq 92$ しかありません。
public static long[] CreateSeq(int nLast = 92)
{
var a = new long[nLast + 1];
a[1] = 1;
for (int i = 2; i <= nLast; i++)
a[i] = a[i - 1] + a[i - 2];
return a;
}
また、再帰関数として実装する練習も頻出ですが、$n$が大きくなるとスタックオーバーフローの原因になるため注意が必要です。
行列の漸化式から求める
行列を利用すると、整数のままで、しかも高速に計算できます。
2 次正方行列$A$を用いて
$$
\begin{eqnarray}
\left(
\begin{array}{c}
a_{n+2} \\
a_{n+1}
\end{array}
\right)
= A
\left(
\begin{array}{c}
a_{n+1} \\
a_n
\end{array}
\right)
\end{eqnarray}
$$
と表すことを考えると、定義の漸化式から
$$
\begin{eqnarray}
A =
\left(
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right)
\end{eqnarray}
$$
とすればよいです。したがって、
$$
\begin{eqnarray}
\left(
\begin{array}{c}
a_{n+1} \\
a_{n}
\end{array}
\right)
= A^n
\left(
\begin{array}{c}
a_1 \\
a_0
\end{array}
\right)
= A^n
\left(
\begin{array}{c}
1 \\
0
\end{array}
\right)
\end{eqnarray}
$$
これで$A^n$を計算すると$a_n$を求めることができ、繰り返し二乗法により、時間計算量は $O(\log n)$ です。
値の桁が大きくなることを無視すれば (例えば、値を剰余群で考える場合)、$n$が 64 ビット整数の最大値であったとしても一瞬で計算できます。
こちらのサイトで、$n<5,000,000$に対してテストできます。
この範囲であれば、漸化式から求める方法でも 2 秒の実行時間制限に収まります：
作成したサンプル コード
次回: (2) リュカ数