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...
This is kind of a simple solution. First thing I came up with; I need to look over some of the other solutions to see what I missed.
[NB] Guess I missed the point about having a separate module for the cache...
iex(7)> Fib.find 100
354224848179261915075
iex(8)> Fib.find 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
iex(9)> Fib.find 10000
336447648764317832666216120051075433103021484606800639065647699746800814421666623681555955136337340255820... . . .
642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
iex(110)>