fib_logarithmic.rb

def multiply(f, m)
  x = f[0][0]*m[0][0] + f[0][1]*m[1][0]
  y = f[0][0]*m[0][1] + f[0][1]*m[1][1]
  z = f[1][0]*m[0][0] + f[1][1]*m[1][0]
  w = f[1][0]*m[0][1] + f[1][1]*m[1][1]

  [[x,y],[z,w]]
end

FIB_BASE = [[1,1],[1,0]]

def fib_rec(n, f)
  return f if n == 0 || n == 1
  
  f = fib_rec(n / 2, f)
  f = multiply(f, f)
  
  return multiply(f, FIB_BASE) if n.odd?
  return f
end

def superfib(n)
  return 0 if n == 0
  f = FIB_BASE
  return fib_rec(n-1, f)[0][0]
end

def fib(n)
  return 0 if n == 0
  return 1 if n == -1
  return superfib(n) if n > 100
  base = [1,1]
  until base.length >= n.abs
    base << base.last(2).reduce(:+)
  end
  if (n > 0 || n.odd?)
    base.last
  else
    -base.last
  end
end