Fast doubling algorithm to compute Fibonacci numbers. This is faster than matrix exponentiation.

fibonacci_fast_doubling.jl

function fib(n::Integer)
  @assert n ≥ 0
  if iszero(n)
    return zero(n)
  elseif n == 1 || n == 2
    return one(n)
  end
  k = div(n,2)
  if iseven(n)
    return fib(k) * (2fib(k+1) - fib(k))
  else
    return fib(k+1)^2 + fib(k)^2
  end
end