Fibonacci in Ruby

1 min read

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 simple beauty 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). But 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 now fib(10000000000) stops working.....

Hopefully you already passed the interview at this point...

To be continued.

You may also find something called Binet's Formula, which is

def fib(n)
  n1 = ((1 + Math.sqrt(5)) / 2)**n
  n2 = ((1 - Math.sqrt(5)) / 2)**n

  ((n1 - n2) / Math.sqrt(5)).round
end

But Binet's formula can only go up to fib(1474) because the result will be larger than the maximum number Ruby can represent Float::MAX.

You could rewrite Math.sqrt(5) by Rational to go further:

def fib(n)
  # 629397181890197/281474976710656
  sqrt5 = Rational(Math.sqrt(5))
  n1 = ((1 + sqrt5) / 2)**n
  n2 = ((1 - sqrt5) / 2)**n

  ((n1 - n2) / sqrt5).round
end

But it significantly slows down the calculation and I could not get my computer to compute fib(50000).