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...
@pragdave so that would be in in the:
It should probably be
Agent.get_and_update
to make it sequential? Like you mentioned it did not affect the result so I didn't notice it.And I must say, I'm enjoying myself immensely with the course, its funny, insightful and great to do. It has taken me quite some time to start, I was intrigued by the language by your talk in Amsterdam, and now finally started working with Elixir, it's great. Thanks for the course! Can't wait to continue tonight 👍