Fibonacci Sequence

Mix.install([
  {:kino, github: "livebook-dev/kino", override: true},
  {:kino_lab, "~> 0.1.0-dev", github: "jonatanklosko/kino_lab"},
  {:vega_lite, "~> 0.1.4"},
  {:kino_vega_lite, "~> 0.1.1"},
  {:benchee, "~> 0.1"},
  {:ecto, "~> 3.7"},
  {:math, "~> 0.7.0"},
  {:faker, "~> 0.17.0"},
  {:utils, path: "#{__DIR__}/../utils"},
  {:tested_cell, git: "https://github.com/BrooklinJazz/tested_cell"}
])

Navigation

Return Home Report An Issue

Setup

Ensure you type the ea keyboard shortcut to evaluate all Elixir cells before starting. Alternatively you can evaluate the Elixir cells as you read.

Fibonacci Sequence

The Fibonacci Sequence is a series of the following numbers.

flowchart LR
a[0] --> b[1] --> c[1] --> d[2] --> e[3] --> f[5] --> g[8] --> h[13] --> i[21] --> k[34] --> ...

It’s created by taking the sum of the previous to numbers to get the next number.

So $fib(n) = fib(n-1) + fib(n - 2)$

You’ll notice that this is a recursive function.

In the Elixir cell below, implement the Fibonacci.sequence/1 function which should return a Fibonacci Sequence up to the $nth$ element.

Fibonacci.sequence(0)
[0]

Fibonacci.sequence(4)
[0, 1, 1, 2, 3]

defmodule Fibonacci do
  def sequence(n) do
  end
end

Competition

In the Elixir cell below, create a FastFib module. The FastFib module should be the most performant version of the Fibonacci Sequence that you can create.

defmodule FastFib do
  def sequence(n) do
  end
end

Use Benchee to benchmark the performance of FastFib compared to Fibonacci. The student in the class with the fastest FastFib time wins.

Benchee.run(
  %{
    fast_fib: fn n -> FastFib.sequence(n) end
  },
  inputs: %{
    "1: small" => 10,
    "2: medium" => 30
    # Uncomment the following if your solution can handle it!
    # "3: large" => 100
    # "4: xl" => 1000
    # "6: 2xl" => 10000
    # "7: 3xl" => 100000
  }
)

Commit Your Progress

Run the following in your command line from the project folder to track and save your progress in a Git commit.

$ git add .
$ git commit -m "finish fibonacci exercise"