Fibonacci number

fibonacci 数は漸化式の形で与えられているので、逐次的にしか計算できないように見えますが、漸化式を行列で書くと、行列のべき乗を求めることで非逐次的に解くことが可能です。

実行結果

行列法と漸化式を逐次求めたものの結果を比較してみます。当然同じ結果が得られます。 2⁵+2, 2⁵+1 のフィボナッチ数の組

     5702887     3524578
     5702887     3524578
Press any key to continue . . .

ソース・プログラム

    program fibo
      implicit none
      integer :: m(2, 2) = [[1, 1], [1, 0]], f(2) = [1, 1]
      integer :: i, fib(2) = [1, 1]
      do i = 1, 5
        m = matmul(m, m)
      end do
      print *, matmul(m, f)
      !
      do i = 1, 2**5
        fib = [fib(1) + fib(2), fib(1)]  
      end do    
      print *, fib
      stop
    end program fibo