Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

行列を使ってフィボナッチ数列

Ruby

これまで何度となくフィボナッチ数列については話題にしてきましたが、 「フィボナッチ数 - Wikipedia」によると、フィボナッチ数列の漸化式は次のように行列表現できるそうです。

\left( \begin{array}{c} F_{n+2} \\ F_{n+1} \\ \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} \right) \left( \begin{array}{c} F_{n+1} \\ F_{n} \\ \end{array} \right)

ゆえに

\left( \begin{array}{cc} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \\ \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} \right)^n

ということで、行列を用いてフィボナッチ数列を計算してみることにしました。

Rubyでは、Matrixクラスを用いると、行列の計算なども簡単に行えますが、今回は繰り返し二乗法の学習も兼ねてということでpow関数を作成しました。

繰り返し二乗法

# 繰り返し二乗法を用いた冪乗の計算
def pow(a, n)
  return 1 if n == 0
  n.even? ? pow(a*a, n/2) : a * pow(a*a, n/2)
end

たとえば、2の10乗を求めるとき、以下のように計算が進んでいきます。

pow(2, 10) = pow(4, 5)
           = 4 * pow(16, 2)
           = 4 * pow(256, 1)
           = 4 * 256 * pow(65536, 0)
           = 4 * 256 * 1
           = 1024

fibonacci.rb

実行結果

$ time ruby fibonacci.rb
39088169

real    0m0.755s
user    0m0.389s
sys     0m0.357s

追記

計算量オーダーlog(n)のpower関数をC言語の繰り返し二乗法を用いて書いた例が掲載されている。