require 'matrix'

# fib1: Fast algorithm using the Golden Ratio

$sqrt5 = Math.sqrt 5
$phi = (1 + $sqrt5) / 2
def fib1 n
  (($phi**n - (1-$phi)**n) / $sqrt5).to_int
end

# fib2: Naïve recursive algorithm

def fib2 n
  if n < 3
    1
  else
    fib2(n-1) + fib2(n-2)
  end
end

# fib3: Memoized recursive algorithm

$fibs = [0,1]
def fib3 n
  $fibs.push($fibs[-1] + $fibs[-2]) until $fibs[n]
  $fibs[n]
end

# fib4: Matrix multiplication shortcut

def fib4 n
  (Matrix[[1,1],[1,0]] ** n)[1,0]
end

[1,2,3,4].each do |i|
  puts eval "fib#{i} 30"
end