Cálculo de Fibonacci O (logn)

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)