## Background

In my never ending quest to learn Elixir I am now doing another Codewars exercise. The description is as follows:

Given a number, say prod (for product), we search two Fibonacci numbers F(n) and F(n+1) verifying

`F(n) * F(n+1) = prod.`

## The real challenge

This is one of my favorites, taking me back to the University days. As any seasoned developer knows, Fibonnaci exercises are mainly used for two things:

- Introducing recursivity
- Forcing you to think about code optimization

In this specific case, it is the second. The code is supposed to pass tests with the following parameters:

```
ProdFib.product_fib(2563195080744681828)
```

## Naive implementation

The first, and most naive, way to solve this exercise is to simply do it without a cache:

## Spoiler

```
defmodule ProdFib do
def product_fib(n) do
product_fib(0, 1, n)
end
defp product_fib(f1, f2, prod) do
fib_1 = fibonacci(f1)
fib_2 = fibonacci(f2)
cond do
fib_1 * fib_2 == prod -> [fib_1, fib_2, true]
fib_1 * fib_2 > prod -> [fib_1, fib_2, false]
true -> product_fib(f1+1, f2+1, prod)
end
end
defp fibonacci(0), do: 0
defp fibonacci(1), do: 1
defp fibonacci(n) do
fibonacci(n-1) + fibonacci(n-2)
end
end
```

Now this code works. But you will eventually start to have timeouts because you are repeating a lot of computations you donāt need.

## How to improve it?

We add a cache !

## The Bad cache

So my first approach was to use module attributes to save a map which would work as a cache:

## Spoiler

```
defmodule ProdFib do
@fib_table %{}
def product_fib(n) do
product_fib(0, 1, n)
end
defp product_fib(f1, f2, prod) do
fib_1 = fibonacci(f1)
fib_2 = fibonacci(f2)
cond do
fib_1 * fib_2 == prod -> [fib_1, fib_2, true]
fib_1 * fib_2 > prod -> [fib_1, fib_2, false]
true -> product_fib(f1+1, f2+1, prod)
end
end
defp fibonacci(0), do: 0
defp fibonacci(1), do: 1
defp fibonacci(n) do
case Map.get(@fib_table, n) do
nil ->
val = fibonacci(n-1) + fibonacci(n-2)
Map.put(@fib_table, n, val)
val
res -> res
end
end
end
```

**This does NOT work**. After checking the documentation for module attributes I understand that module attributes are defined at compile time, and thus cannot not mutate at runtime:

However, I still needed a cacheā¦

## The Ugly cache

So I have been reading about ETS and I thought that since I need a global cache for this exercise, and since one of ETSās main uses is to cache things, that it would fit perfectly !

## Spoiler

```
defmodule ProdFib do
def product_fib(n) do
try do
:ets.new(:fibo_cache, [:protected, :named_table, :set])
product_fib(0, 1, n)
catch
_, _ -> product_fib(0, 1, n)
end
end
defp product_fib(f1, f2, prod) do
fib_1 = fibonacci(f1)
fib_2 = fibonacci(f2)
cond do
fib_1 * fib_2 == prod -> [fib_1, fib_2, true]
fib_1 * fib_2 > prod -> [fib_1, fib_2, false]
true -> product_fib(f1+1, f2+1, prod)
end
end
defp fibonacci(0), do: 0
defp fibonacci(1), do: 1
defp fibonacci(n) do
case :ets.lookup(:fibo_cache, n) do
[] ->
val = fibonacci(n-1) + fibonacci(n-2)
:ets.insert(:fibo_cache, {n, val})
val
[{_key, val}] -> val
end
end
end
```

So, this code *works*. It passes all tests and never times out. But it is really ugly.

## Problems with Ugly cache

- I am using a
`try/catch`

for control flow. We donāt use errors for control flow. - This example is not
*really*testable. I am using a global ETS table as a cache. Globals are evil. Adding to this point, there is a chance that some of you may think ETS to be overkill for this. And to be honest I wouldnāt have any arguments to prove you wrong.

## I need a Good cache

So, the solution to the previous problem would be:

- Donāt use errors for control flow. Just donāt.
- Instead of relying in a global table for cache, one could create an empty map, and pass it around as state. The problem with this approach is that I failed miserably with it. Hence, the usage of ETS.

## This works and all but ā¦

But I was wondering if my example could be improved?

I am pretty much sure someone here will have ideas on how to solve issue 1 ( remove control flow via errors ) and as far as issue 2 goes perhaps there is a different approach I am not yet familiar with.

Any ideas?