Fibonacci in Ruby

Fibonacci is a common interview question and here let me share some solutions to save you time to do the research.

The obvious solution is recursion from the definition:

def fib(n)
  return 1 if n <= 1

  fib(n-1) + fib(n-2)
end

This quickly stops working for fib(40). But we can introduce cache:

Cache = {}
def fib(n)
  Cache[n] ||= begin
    return 1 if n <= 1

    fib(n-1) + fib(n-2)
  end
end

But this solution does not work for fib(10000). SystemStackError: stack level too deep...There is a limit of how many method calls can be pushed on the stack.

But we could rewrite the recursion into iterator.

def fib(n)
  a, b = 0, 1
  n.times do
    a, b = b, a + b
  end
  a
end

But this stops working when we hit fib(1000000). Then we can use a solution called Matrix Exponentiation.

require "matrix"

def fib(n)
  matrix = Matrix[[1,1], [1,0]]
  (matrix ** n)[0, 0]
end

But this solution does not work for fib(100000000). There is a technique called fast doubling:

def fib(n)
  _fib(n)[0]
end

def _fib(n)
  return [0, 1] if n == 0

  a, b = _fib(n / 2)
  c = a * (b * 2 - a)
  d = a * a + b * b

  if n % 2 == 0
    [c, d]
  else
    [d, c+d]
  end
end

fib(100000000) takes about 1.565 seconds.

But fib(10000000000) stops working.....