require 'matrix'
def fib(n)
return 0 if n == 0
m = Matrix[[1, 1], [1, 0]]
mul([m] * n)[0, 1]
end
def mul(matrices)
return matrices[0] if matrices.size == 1
mid = matrices.size / 2
return mul(matrices[0, mid]) * mul(matrices[mid..-1])
end
puts fib(1000000)