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

http://dev.heartsavior.net/288
=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