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:

https://elixir-lang.org/getting-started/module-attributes.html

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?

3 Likes

With these kinds of problems, it might help to separate the implementation (fibonacci) from the caching (memoization, like using a map) abstraction layers.

Iā€™m unfortunately pressed for time, so I cannot write an example for you right now, but you might like to read this tutorial about the Y-combinator (which uses Lisp-syntax, but hopefully that does not distract too much from the explanation).

1 Like

Instead of caching simply try to implement a more optimized Fibonacci algorithm.

One of the most well known is probably this one (from memory might be slightly off):

def fib(n, curr \\0, next \\ 1)
def fib(0, curr, next), do: {curr, next}
def fib(n, curr, next), do: fib(n-1, next, curr + next)

This does even respect the fact that you need fib(n) and fib(n+1) anyway and returns both in a single tuple. Of course this is still O(n), but you canā€™t make it better than that. Caching or not.

edit

Also please let me remind you, that a cache never replaces a good algorithm but only extends it.

2 Likes

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.

https://www.codewars.com/kata/reviews/5b616a0d37c9bd8c6100012f/groups/5bc9afeed0035713930013fe

3 Likes

How interesting. Of all the people, you are definitely the last one I would expect to see using Streams, after reading some of your advent posts.

Coulndā€™t you have done the same with Enum?

Anyway, the fact your solution does it without cache already amazes me. I have a strong reactive programming feeling when I read it.

Looks like I still have a lot to learn about the Stream module.

1 Like

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.

3 Likes

FYI:


Spoiler
defmodule ProdFib do
  def product_fib(n),
    do: product_fib(n,0,1)

  defp product_fib(n, f_m, f_n) do
    product = f_m * f_n
    cond do
      product < n ->
        product_fib(n, f_n, f_m + f_n)
      product > n ->
        [f_m, f_n, false]
      true ->
        [f_m, f_n, true]
    end
  end
end

IO.inspect ProdFib.product_fib(714) # [21, 34, true]
IO.inspect ProdFib.product_fib(800) # [34, 55, false]
IO.inspect ProdFib.product_fib(4895) # [55, 89, true]
IO.inspect ProdFib.product_fib(5895) # [89, 144, false]
IO.inspect ProdFib.product_fib(74049690) # [6765, 10946, true]
IO.inspect ProdFib.product_fib(2563195080744681828) # [1836311903, 2971215073, false]
1 Like

This requires signup before being able to view anything, by the way.

1 Like

I know. Even more, you need to have solved the kata first.

I remember having mentioned that in the other CW related track, sorry for not mentioning it here.

I do not want to publish the solution here, as I do not want to spoil anyone.

1 Like

I do not want to publish the solution here, as I do not want to spoil anyone.

Given what is going on in the opening post that ā€œhorse has left the barnā€.

1 Like

I did the caching fib not long ago myself, I ended up coming up with 2 seperate solutions

the first one makes use of a map and just passes that around

defmodule Fib do
 
  def fib(num, _, cache) when num < 0 do
 	IO.puts "Invalid Number"
 	main(cache)
  end
 
  def fib(_num, {:ok, val}, cache) do
 	IO.puts(val)
 	main(cache)
  end
 
  def fib(num, _, cache) do
 	  {:ok, max} = Map.fetch(cache, :max)
 	  {:ok, n1} = Map.fetch(cache, max)
 	  {:ok, n2} = Map.fetch(cache, max - 1)
 	  cache = Map.put(cache, max + 1, n1 + n2)
 	  cache = Map.put(cache, :max, max + 1)
 	  fib(num, Map.fetch(cache, num), cache)
  end
 
  def main(cache \\ %{ 0 => 0, 1 => 1, :max => 1}) do
 	input = IO.gets("Calc Fib (q to quit): ") |> String.trim |> String.downcase
 	cond do
 	  input == "q" -> exit(:shutdown)
 	  input =~ ~r/^\d+$/ ->
 		n = input |> String.to_integer
 		fib(n, Map.fetch(cache, n), cache)
 	  true -> IO.puts "Invalid Number"
 	end
 	main(cache)
  end
end
 
Fib.main()

the second version uses an agent

 defmodule Fib do
  def start_link, do: Agent.start_link(fn -> %{ 0 => 0, 1 => 1, :max => 1 } end, name: __MODULE__)
 
  def fib(num) when num < 0, do: IO.puts "Invalid Number"
  def fib(num) do
 	case Agent.get(__MODULE__, &Map.fetch(&1, num)) do
 	  {:ok, val} -> IO.puts(val)
 	  _ ->
 		{:ok, max} = Agent.get(__MODULE__, &Map.fetch(&1, :max))
 		{:ok, n1} = Agent.get(__MODULE__, &Map.fetch(&1, max))
 		{:ok, n2} = Agent.get(__MODULE__, &Map.fetch(&1, max - 1))
 		Agent.update(__MODULE__, &Map.put(&1, max + 1, n1 + n2))
 		Agent.update(__MODULE__, &Map.put(&1, :max, max + 1))
 		fib(num)
 	end
  end
 
  def main do
 	input = IO.gets("Calc Fib (q to quit): ") |> String.trim |> String.downcase
 	cond do
 	  input == "q" -> exit(:shutdown)
 	  input =~ ~r/^\d+$/ -> input |> String.to_integer |> fib
 	  true -> IO.puts "Invalid Number"
 	end
 	main()
  end
end
 
Fib.start_link()
Fib.main()

Not sure if this helps you any or not.

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.

3 Likes

In my judgement the point of the exercise is to sidestep the implementation of a dedicated fibonacci function entirely but instead to take advantage of the nature of the fibonacci sequence (i.e. ā€œleverage the nature of the constraintsā€) - hence my proposed solution.

1 Like

True, I didnā€™t even look at the URL of the question until now, that site took soooo long to load that I canceled it the first timeā€¦ >.>

Yeah, codewars was, and is still awfully slow, even years after I used it for the first time. Thatā€™s what I dislike most thereā€¦

1 Like

Not Elixir, but if you want inspiration for dozens of ways to implement a fibonacci you should have fun reading this: https://www.willamette.edu/~fruehr/haskell/evolution.html

1 Like

Hi, sorry about the experience over the past few years. We didnā€™t have anyone working on the site for a while and itā€™s been embarrassingly slow.
Iā€™m taking over the project and currently planning/evaluating for the next version whenever I have the time. Hopefully, I can post something on #community:showcase-adoption in the future :grin:

3 Likes

As for the stream-based solutions, in my beginning Elixir-days, I wrote the Sequences library, which contains all kinds of numeric sequences including Fibonacci, keeping only track of the numbers the algorithm requires:

Iā€™ll try to find time to write down a memoizing Y-combinator example soon, because it would be a great example to port to Elixir :smile:.

1 Like

All right, here you go:

There are some explanations in the source-code, although I am not yet entirely happy with the code; mostly the memoization-bit. I think the agent is not properly closed afterwards (and a new agent is made during every function call, rather than them being shared for the same function), but I donā€™t know how to properly close the agent after the outern-most function call. Maybe by introducing yet another layer of indirection in the wrapper?

Anyhow, this work was largely based on the paper That about Wraps it Up (see fig 12/13/14, for instance), which implements this stuff in Standard ML (which has some mutable datatypes that Elixir has not).

2 Likes

Other ways to wrap an unsuspecting (single-argument) function with a caching layer would be:

  • ETS tables, as mentioned before.
  • The Process dictionary.
  • A NIF that uses interior mutability (which breaks how we Elixir programmers expect immutable datastructures to work. Lots of fun :angel: ).
1 Like