If you're up for a challenge…
The classic Fibonacci implementation is
def fib(0), 0
def fib(1), 1
def fib(n), fib(n-1) + fib(n-2)
This has a worst case performance of \( O( 1.6^{n+1} ) \). For large \( n \), this is a big number (20 digits or so long for \( n = 100 \)). This means it is slow, and it burns through stack space at an alarming rate.
However, you can make the function perform in linear time by
implementing a simple cache. An Elixir map is a good data structure
for this. Initialize it with %{ 0 => 0, 1 => 1 }
, and add new values
to it as you discover them.
Write a module that implements the cache. It should use an agent, and that agent's state should be the map.
Then write a Fibonacci module that uses this cache.
Try calculating fib(100)
. If it comes back without crashing your
machine, and before the sun has expanded to consume the Earth, then
your cache worked...
My first solution used an externally exposed PID. After stealing the
run(body)
portion of @pragdave's solution that hides the PID, here's where I arrived:fibonacci.ex
:cache.ex
:I find this a lot more readable, albeit with the use of
cond
.