O(logn) Fibonacci calculation

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)