=begin
Divide & Conquer 를 이용하여 n 번째 피보나치 수열의 수를 구하기

우리에게 많이 알려진 재귀함수로 피보나치를 구하면 피보나치 재귀에서 엄청난 중복이 생긴다.
피보나치 수열을 아래와 같이 행렬식으로 변환하면 n번의 제곱으로 수를 구할 수 있다.

n 번째 피보나치 수열의 수를 Fn 이라 할 때,
|F2 F1| = |1 1|
|F1 F0|   |1 0|
이 된다.

이 정사각 행렬을 n 번 제곱하면
|Fn+1 Fn| = |1 1|^n
|Fn Fn-1|   |1 0|
이 된다.
(http://en.wikipedia.org/wiki/Fibonacci_number 의 Matrix form 참조)

이 때, 정사각 행렬 A 에 대해 A^nA^m = A^(n+m), A^nA^n = A^2n 이 성립하므로
이를 이용하면 Divide & Conquer 를 적용하여 log 2 n 번의 제곱으로 수를 구할 수 있다.
=end

class Matrix2x2
  attr_accessor :matrix

  def initialize
    @matrix = []
    @matrix[0] = []
    @matrix[1] = []
  end

  def set_value(row1col1, row1col2, row2col1, row2col2)
    @matrix[0][0] = row1col1
    @matrix[0][1] = row1col2
    @matrix[1][0] = row2col1
    @matrix[1][1] = row2col2

    self
  end

  def multiply(mat)
    mat_ret = Matrix2x2.new.set_value(
      @matrix[0][0] * mat.matrix[0][0] + @matrix[0][1] * mat.matrix[1][0],
      @matrix[0][0] * mat.matrix[0][1] + @matrix[0][1] * mat.matrix[1][1],
      @matrix[1][0] * mat.matrix[0][0] + @matrix[1][1] * mat.matrix[1][0],
      @matrix[1][0] * mat.matrix[0][1] + @matrix[1][1] * mat.matrix[1][1]
    )

    mat_ret
  end

  def power(exp)
    return Matrix2x2.unit if 0 == exp
    return dclone if 1 == exp

    if 1 == exp & 1
      mat_ret = power((exp - 1) / 2)
      mat_ret = mat_ret.multiply( mat_ret ).multiply( self )
    else
      mat_ret = power(exp / 2)
      mat_ret = mat_ret.multiply( mat_ret )
    end

    mat_ret
  end

  def Matrix2x2.unit
    Matrix2x2.new.set_value(1, 0, 0, 1)
  end

  def dclone()
    Matrix2x2.new.set_value(
      @matrix[0][0], @matrix[0][1],
      @matrix[1][0], @matrix[1][1]
    )
  end
  
end

def fibonacci(n)
  mat = Matrix2x2.new.set_value(1, 1, 1, 0)
  
  mat.power(n).matrix[0][1]
end

puts "100th Fibonacci number is " + fibonacci(100).to_s

100th Fibonacci number is 354224848179261915075