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:

1. Introducing recursivity
2. 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:

    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:

    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 !

    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

1. I am using a try/catch for control flow. We don’t use errors for control flow.
2. 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:

1. Don’t use errors for control flow. Just don’t.
2. 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?