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.....