アルゴリズム論特論（塩田）第4回 (4)　フィボナッチ数列
前へ / 戻る / 次へ

フィボナッチ数列

　「フィボナッチ数」をユークリッドのアルゴリズムに入力すると面白いことが起こります。
Def.9　漸化式
$f_0 = f_1 = 1$, $f_{n+2} = f_{n+1} + f_n$ ( $n =0, 1, \cdots$ )
で定まる数列 $\{\,f_n\,\}$ をフィボナッチ数列という。
　最初の数項は
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
で与えられ、ひまわりの種の個数、アンモナイトの模様、など自然界の至る所に現れることが知られています。
参考：

フィボナッチ数列と黄金比

　フィボナッチ数列の一般項は「黄金比」で書き表すことができます。
Def.10　$\displaystyle{\phi = \frac{1 +\sqrt{5}}{2}} = 1.618\cdots$ を黄金比という。
　人間が一番美しいと思う長方形の縦横比が黄金比であると言われ、 また、正五角形や正十二面体にも関わっています。
参考：
Th.11　フィボナッチ数列の一般項は
$f_n = \frac{1}{\sqrt{5}}\left\{ \phi^{n+1} - (\bar{\phi})^{n+1} \right\} = \frac{1}{\sqrt{5}}\left\{ \left(\frac{1 + \sqrt{5}}{2}\right)^{n + 1} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n + 1} \,\right\}$
代数学用語で $\bar{\phi} = \frac{1 - \sqrt{5}}{2}$ は $\phi$ の「共役」と呼ばれる数です。
Cor.12　(1)　$n$ が十分大きいとき　$f_n \mbox{ ≒ } \frac{1}{\sqrt{5}} \phi^{n+1}$
(2)　$\displaystyle{\lim_{n \rightarrow \infty}\frac{f_{n+1}}{f_n} = \phi}$.
∵　$\bar\phi = -0.618\cdots$ は絶対値が 1 より小さいので。(証明終)

フィボナッチ数列と拡張ユークリッドアルゴリズム

Prop.13　フィボナッチ数列の隣接する 2 項を ( 大きい方から ) ユークリッドのアルゴリズムの初期値とする：
$a = r_0 = f_N$ , $\quad b = r_1 = f_{N-1}$ .
すると $r_n$ ( $n \lt N$ ) はフィボナッチ数列を逆順に並べたものになる：
$r_n = f_{N-n}$ .
また $x_n$ ( $n \geqq 2$ ), $y_n$ ( $n \geqq 1$ ) はフィボナッチ数列の番号をずらして $\pm$ を付けたものになる：
$x_{n+2} = (-1)^n \times f_n$ , $\quad y_{n+1} = (-1)^n \times f_n$ .
実行例　 
フィボナッチ数列を拡張ユークリッドアルゴリズムに入力します。
N = 10
r[0] = f[10] = 89
r[1] = f[9] = 55
(r[ 0], x[ 0], y[ 0]) = (  89,    1,    0)
(r[ 1], x[ 1], y[ 1]) = (  55,    0,    1)
(r[ 2], x[ 2], y[ 2]) = (  34,    1,   -1)
(r[ 3], x[ 3], y[ 3]) = (  21,   -1,    2)
(r[ 4], x[ 4], y[ 4]) = (  13,    2,   -3)
(r[ 5], x[ 5], y[ 5]) = (   8,   -3,    5)
(r[ 6], x[ 6], y[ 6]) = (   5,    5,   -8)
(r[ 7], x[ 7], y[ 7]) = (   3,   -8,   13)
(r[ 8], x[ 8], y[ 8]) = (   2,   13,  -21)
(r[ 9], x[ 9], y[ 9]) = (   1,  -21,   34)
(r[10], x[10], y[10]) = (   0,   55,  -89)
(89) * (-21) + (55) * (34) = 1

N = 11
r[0] = f[11] = 144
r[1] = f[10] = 89
(r[ 0], x[ 0], y[ 0]) = ( 144,    1,    0)
(r[ 1], x[ 1], y[ 1]) = (  89,    0,    1)
(r[ 2], x[ 2], y[ 2]) = (  55,    1,   -1)
(r[ 3], x[ 3], y[ 3]) = (  34,   -1,    2)
(r[ 4], x[ 4], y[ 4]) = (  21,    2,   -3)
(r[ 5], x[ 5], y[ 5]) = (  13,   -3,    5)
(r[ 6], x[ 6], y[ 6]) = (   8,    5,   -8)
(r[ 7], x[ 7], y[ 7]) = (   5,   -8,   13)
(r[ 8], x[ 8], y[ 8]) = (   3,   13,  -21)
(r[ 9], x[ 9], y[ 9]) = (   2,  -21,   34)
(r[10], x[10], y[10]) = (   1,   34,  -55)
(r[11], x[11], y[11]) = (   0,  -89,  144)
(144) * (34) + (89) * (-55) = 1
Rem.14　Prop.13 の状況ではループ回数は $N \mbox{ ≒ } \log_\phi a =O(\log a)$.
∵　Cor.12 (1)
Cor.15　ユークリッドのアルゴリズムの計算量の評価 $O(\log^2 a)$ は best-possible である。
　best-possible は「可能な限り最良」という意味です。 計算量の評価は、Th.4 が Th.5 に改良できたように、 まだ改良の余地があることもあるのですが、 ユークリッドのアルゴリズムは入力がフィボナッチ数列だと本当に計算量が $O(\log^2 a)$ になりますので、 これが最良ということになります。

前へ / 戻る / 次へ