Apply dynamic programing for calculating Fibonacci number with Elixir

Khanh Nguyen — Sat, 16 Apr 2022 09:02:32 +0000

What is dynamic programing?

Dynamic programing (DP) is an optimization solution for recursion. When using a recursive function, it may be call and processed with an input value multiple times. To prevent this problem, we may store all calculated results in a table (the DP table). By this way, we just find the result of an input value by accessing an item in DP table and don't need to re-calculate it.

Using DP to calculate the x-th Fibonacci number

The x-th fibonacci number is calculated by this formula:

f(0) = 1
f(1) = 1
f(x) = f(x - 1) + f(x - 2)

Implementation with recursion

Python

def fibonacci(x: int) -> int:
    if x < 0:
        raise 'Cannot calculate'

    if x == 0:
        return 1

    if x == 1:
        return 1

    return fibonacci(x - 1) + fibonacci(x - 2)

Elixir

defmodule Fibonacci do
  def perform(x) when x < 0, do: {:error, "Cannot calculate"}

  def perform(x) do
    {:ok, calculate(x)}
  end

  def calculate(x) do
    IO.inspect("Calculating #{x}")

    case x do
      0 ->
        1

      1 ->
        1

      x ->
        calculate(x - 1) + calculate(x - 2)
    end
  end
end

Let's run with x is 5:

iex(3)> Fibonacci.perform(5)
"Calculating 5"
"Calculating 4"
"Calculating 3"
"Calculating 2"
"Calculating 1"
"Calculating 0"
"Calculating 1"
"Calculating 2"
"Calculating 1"
"Calculating 0"
"Calculating 3"
"Calculating 2"
"Calculating 1"
"Calculating 0"
"Calculating 1"
{:ok, 8}

As we can see, we take 15 steps to get the final result, and a lot of input values are re-calculated multiple times. This table explains number of calculating times of each input value:

input value	calculating times
0	3
1	5
2	3

Implementation with DP table

To solve re-calculation problem, we can apply DP by using DP table.

Python

def fibonacci(x: int) -> int:
    if x < 0:
        raise 'Cannot calculate'

    if x == 0:
        return 1

    if x == 1:
        return 1

    dp_table = [0 for _ in range(x + 1)]
    dp_table[0] = 1
    dp_table[1] = 1

    i = 2
    while i <= x:
        dp_table[i] = dp_table[i - 1] + dp_table[i - 2]
        i += 1

    return dp_table[x]

Or we can use a dict to build the DP table:

def fibonacci(x: int) -> int:
    if x < 0:
        raise 'Cannot calculate'

    if x == 0:
        return 1

    if x == 1:
        return 1

    dp_table = {0: 1, 1: 1}

    i = 2
    while i <= x:
        dp_table[i] = dp_table[i - 1] + dp_table[i - 2]
        i += 1

    return dp_table[x]

Elixir

defmodule Fibonacci do
  def perform(x) when x < 0, do: {:error, "Cannot calculate"}

  def perform(x) do
    {:ok, calculate(x, 0)}
  end

  defp calculate(x, index, table \\ %{}) do
    IO.inspect("Calculating #{index}")

    fibonacci_value =
      case index do
        0 ->
          1

        1 ->
          1

        index ->
          table[index - 1] + table[index - 2]
      end

    if index == x do
      fibonacci_value
    else
      table = Map.put(table, index, fibonacci_value)
      calculate(x, index + 1, table)
    end
  end
end

Let's run with x is 5:

iex(3)> Fibonacci.perform(5)
"Calculating 0"
"Calculating 1"
"Calculating 2"
"Calculating 3"
"Calculating 4"
"Calculating 5"
{:ok, 8}

As we can see, all input values for calculating are visited once, and we take only 5 steps to get the final result.

We also have an approach with Enum.reduce/3 function:

defmodule Fibonacci do
  def perform(x) when x < 0, do: {:error, "Cannot calculate"}

  def perform(0), do: {:ok, 1}

  def perform(1), do: {:ok, 1}

  def perform(x) do
    dp_table =
      Enum.reduce(2..x, %{0 => 1, 1 => 1}, fn index, acc ->
        Map.put(acc, index, acc[index - 1] + acc[index - 2])
      end)

    {:ok, dp_table[x]}
  end
end

Implementation with only 2 variables

In some case, we don't need to store all calculated Fibonacci numbers. In fact, we just care the (x - 1)-th and (x - 2)-th numbers. To reduce space for DP table, we can use only 2 variables to cache calculated values:

c_2: represent the (x - 2)-th Fibonacci number.
c_1: represent the (x - 1)-th Fibonacci number.

defmodule Fibonacci do
  def perform(x) when x < 0, do: {:error, "Cannot calculate"}

  def perform(0), do: {:ok, 1}

  def perform(1), do: {:ok, 1}

  def perform(x) do
    {:ok, calculate(x, 2, 1, 1)}
  end

  defp calculate(x, index, c_1, c_2) do
    fibonacci_value = c_1 + c_2

    if index == x do
      fibonacci_value
    else
      calculate(x, index + 1, fibonacci_value, c_1)
    end
  end
end

Conclusion

This article introduces approaches to calculate x-th Fibonacci number using DP. With DP, we can make the application running faster by saving calculating times with DP table. In next articles, I will introduce approaches to solve other DP problems with Elixir.