Fibonacci with dynamic programming from imperative language need help

Questions / Help
, ,
1

I know elixir is a functional programming language and this means can’t make a change state in some problems? Do I am missing something?
Can use any techniques to replace for solution dynamic programming Fibonacci? This is my solution in Golang

package main
import "fmt"

func fib(n int) int {
    // make initial array with size (n+1)
    answer := make([]int, n+1)
    
    // set answer[0] and answer[1] with default values
    answer[0] = 0
    answer[1] = 1
    
    // run dynamic programming and memorize steps
    // such that answer[i] = answer[i-1] + answer[i-2]
    // for each  2 <= i <= n
    for i := 2; i <= n; i++ {
        answer[i] = answer[i-1] + answer[i-2]   
    }
    
    // check answer array
    fmt.Println(answer)
    
    // fib(n) is last element of answer array
    return answer[n]
}

func main() {
   // test
   fmt.Println(fib(10))
   // output: [0 1 1 2 3 5 8 13 21 34 55]
   //         55         
}
2

Do you mean this https://gist.github.com/kyanny/2026028
There is a tail call optimised version too.

1 Like
3

This is not possible, because there are no Arrays in Elixir, but linked List

In Elixir, You don’t access list element by index, because it’s expensive.

This is not possible, because i is mutated

Instead, You can have functions that transform input into output.

defmodule Demo do
  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n), do: fib(n - 1) + fib(n - 2)
end

and if You want to cumulate, You can enumerate a range from 0 to 10 and pass the implementation details.

Enum.map(0..10, & Demo.fib(&1))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

This is not efficient, as the result is recalculated. But You can make it better with recursion.

2 Likes
4

If you want to make the shift to functional programming then I strongly recommend that you first read this book:

This is the only book I know that spents a great deal of time educating you how to go from Object Orientated Programming and Procedural Programming to Functional Programming. @pragdave does an excellent job on making it click in our brains, can’t recommend it enough.

If you prefer video form, then he has a video course that does the same:

I have done both and that really helped me to let go away the old way of thinking about coding.

3 Likes
5

A solution using dynamic programming would be:

defmodule FibDynamicProgramming do
  def fib(n) do
    cache = %{0 => 0, 1 => 1}

    cache =
      Enum.reduce(2..n, cache, fn
        i, acc ->
          Map.put(acc, i, acc[i-2] + acc[i-1])
      end)

    cache[n]
  end
end

IO.inspect(FibDynamicProgramming.fib(10))
55

I added another solution using Agent on the gist above (https://gist.github.com/kyanny/2026028#gistcomment-3594302).

6

You will often see fibonnaci written according to its functional definition but as others pointed out, it is not very efficient as you compute the whole chain on every operation:

defmodule Fib do
  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n), do: fib(n - 1) + fib(n - 2)
end

However, you can write a looping version, as in Go in Elixir. In Elixir we don’t have traditional loops, instead we use recursion. The other insight is that, in order to compute fibbonacci, we don’t need the whole array of results, only the last two, so we can implement it like this:

defmodule Fib do
  def fib(n), do: fib(n, {0, 1})

  defp fib(0, {current, _next}), do: current
  defp fib(n, {current, next}), do: fib(n - 1, {next, current + next})
end

It is worth reading more into recursion but one very useful exercise is to see how the execution goes manually. For example, for fib(5), this is what happens:

fib(4)
fib(4, {0, 1})
fib(3, {1, 1})
fib(2, {1, 2})
fib(1, {2, 3})
fib(0, {3, 5})
#=> when we reach 0, we match "defp fib(0, {current, _next}), do: current" and return 3

This is going to have the same perf complexity as the Go one.

This is an advanced topic, so please don’t consider it part of the answer, but there is another cool variant of the algorithm above which is to pack it into a stream. You can think of streams as lazy lists, which are generated on the fly, as needed! Here is a fib stream:

iex(3)> fib =                     
...(3)>   Stream.unfold({0, 1}, fn {current, next} ->
...(3)>     {current, {next, current + next}}
...(3)>   end)
#Function<63.34589589/2 in Stream.unfold/2>
iex(4)> Enum.at(fib, 4)
3
iex(5)> Enum.at(fib, 10)
55
iex(6)> Enum.at(fib, 100)
354224848179261915075

The cool think about the fib stream is that you are totally in control. If you want a single entry, you can have it. If you want a list, you got that too:

iex(7)> Enum.take(fib, 100)      
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733,
 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, ...]
15 Likes
7

I wrote two blog posts about Fibonacci algorithms in Elixir, posts include benchmarks of all the implementations I evaluated:

This pretty well sums up what I found when I benchmarked the implementations I looked at in those blog posts.

2 Likes