Fl4m3Ph03n1x

Fl4m3Ph03n1x

Product of consecutive Fib numbers - how to cache?

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:

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

  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?

Marked As Solved

peerreynders

peerreynders

No it isn’t, that is body recursive:

  • first fibonacci(n-1) is calculated.
  • second fibonacci(n-2) is calculated
  • both values added together once they are available and then finally that value is returned.

This is tail recursive:

defp fibonacci(_, acc, i, n) when i == n,
  do: acc
defp fibonacci(fi_2, fi_1, i, n) when i < n,
  do: fibonacci(fi_1, fi_2 + fi_1, i + 1, n)

def fibonacci(0),
  do: 0
def fibonacci(1),
  do: 1
def fibonacci(n) when n > 1 and is_integer(n),
  do: fibonacci(fibonacci(0), fibonacci(1), 1, n)
  • there is no need to put the values on the stack because it can be simply replaced with the result from the last function call.

Ultimately the proposed solution looks very similar to this.

Also Liked

NobbZ

NobbZ

I’ve read through the exercise again and now realise that my function won’t help you (that) much. Have to do to much in the office right now to solve that one for myself :frowning:

Looks like a fun task…


edit

As everyone went to dinner early and I have an appointement for dinner in an hour, I took the time to solve it.

Using a streamified version of my algorithm from above I finished the task in less than 5 minutes and a handfull of lines.

Sign in | Codewars

NobbZ

NobbZ

No, as I expect the stream of fibonacci numbers potentially infinite. You can’t do this with eagerly evaluated Enum. And always remember, a Stream is just a lazy evaluated Enum.

I could have done this using explicit recursion and propably that would have been more efficient, but hey, it had to fit in the time of a smoking break and I didn’t want to think much :wink: The streaming version was already in my head.

OvermindDL1

OvermindDL1

Instead of caching, why not just make sure that the optimal algorithm is not already fast enough:

defmodule ProductFib do
  def run(n) when n>=0 do
    {a, b} = fib_(n)
    a
  end

  def fib_(0), do: {0, 1}
  def fib_(n) do
    {a, b} = fib_(div(n, 2))
    c = a * (b * 2 - a)
    d = a * a + b * b
    cond do
      rem(n, 2) == 0 -> {c, d}
      true -> {d, c + d}
    end
  end
end

Getting the value of 1 million takes:

iex(2)> :timer.tc(ProductFib, :run, [1000000])|>elem(0)
618248

0.618 seconds on my slow desktop here. It’s not memoized but it also skips the great majority of values that need to be calculated too. But how well does that one work when used in the context of your prod stuff question? If you want you could even thread a map through to memoize ‘future’ operations as well, though it gains you nothing in a single call.

Where Next?

Popular in Questions Top

sen
Hi All, I set a environment variables in dev.exs , like below code. when i start server, how can i set the ${enable} value? thanks. d...
New
aadeshere1
I have a another noob question about loop. Since elixir is immutable, while loop is not directly possible. total = 10 while total != 0 ...
New
9mm
I am constructing a JSON object (map) and I need to conditionally set a field. I’m trying to write proper elixir-way code… and I’m at a l...
New
skosch
To my knowledge, put_in, Map.update etc. all have the one limitation of not automatically creating intermediate keys when needed (for exa...
New
electic
Hi, I am new to Elixir. I am trying to use the DateTime component to insert a date into MySQL however the there seems to be no way to fo...
New
ovidiubadita
Hey all, I discovered Elixir and I love it. I always wanted to learn a functional programming and I intended to go for Haskell, but afte...
New
Fl4m3Ph03n1x
About me? ( if you have nothing better to do than reading about some random guy in the internet :stuck_out_tongue: ) Hello all, this is ...
New
shijith.k
I am trying to start a new phoenix project with elixir 1.9, but mix phx.new does not work. It says that ** (Mix) The task "phx.new" could...
New
yawaramin
In the Dialyzer docs ( dialyzer — OTP 29.0.2 (dialyzer 6.0.1) ), there is a way to turn off a specific warning for a function: -dialyzer...
New
svb
Hi! Currently I want to submit a form by pressing the Enter key. However, since my input field is of type “textarea” this is just adds a...
New

Other popular topics Top

Darmani72
If I have a post route which an argument: post /my_post_route/:my_param1, MyController.my_post_handler How would get the post params ...
New
mcarvalho
What is the difference between System.get_env and Application.get_env? For example, what are best practices to use one versus another.
New
stefanchrobot
What’s the safe way to decode a JSON string into a struct? I want to avoid calling String.to_atom. Jason.decode can give me a map with st...
New
aalberti333
As the title describes, I’m trying to run Enum.map() over a list of key/value pairs, where the value is a map. My data looks like this: ...
New
RisingFromAshes
I’ve read in another post that it may be possible with a router helper - but I couldn’t find an appropriate one, and tbh, I’m still just ...
New
sergio_101
I am VERY much an elixir newbie. I have taken one elixir course and one phoenix course on Udemy. During that course, I saw the instructor...
New
dblack
I’ve got an issue with an app and I’ve no idea of how to troubleshoot it. I’m hoping someone here might have seen something similar. I p...
New
AstonJ
We’ve put together this wiki for Phoenix LiveView - please feel free to add any info you feel is worth including. What is Phoenix LiveV...
New
hariharasudhan94
I would like to know what is the best IDE for elixir development?
New
PeterCarter
There are pre-rolled solutions for other frameworks that do work. However, Phoenix does not seem to have these. Have people had good expe...
New

We're in Beta

About us Mission Statement