Fibonacci in Elixir

fibonacci.ex

defmodule FinalValue do
  def fibonacci(number) do
    [value | _tail] = fibonacci_do(number)
    value
  end

  def fibonacci_do(1), do: [0]
  def fibonacci_do(2), do: [1 | fibonacci_do(1)]

  def fibonacci_do(number) when number > 2 do
    [x, y | _] = fibonacci_do(number - 1)
    [x + y, x]
  end
end

defmodule AllValues do
  def fibonacci(number) do
    Enum.reverse(fibonacci_do(number))
  end

  def fibonacci_do(0), do: [0]
  def fibonacci_do(1), do: [1 | fibonacci_do(0)]

  def fibonacci_do(number) when number > 1 do
    [x, y | _] = all = fibonacci_do(number - 1)
    [x + y | all]
  end
end

defmodule FastDoubling do
  # Fast doubling Fibonacci algorithm
  # https://www.nayuki.io/page/fast-fibonacci-algorithms
  def fibonacci(n) do
    {value, _} = fib(n)
    value
  end

  def fib(0), do: {0, 1}

  # Returns the tuple (F(n), F(n+1)).
  def fib(n) when n > 0 do
    {a, b} = n |> div(2) |> fib()
    c = a * (b * 2 - a)
    d = a * a + b * b
    case Integer.mod(n, 2) do
      0 -> {c, d}
      _ -> {d, c + d}
    end
  end
end

defmodule FibStream do
  def fibonacci(n) do
    fibonacci() |> Enum.at(n)
  end

  def fibonacci() do
    Stream.unfold({0, 1}, fn {current, next} ->
      {current, {next, current + next}}
    end)
  end
end

Impressive results -- when running FinalValue.fibonacci(1_000_000) returned the value in 14220910 microseconds, which is about 14.22 seconds.

The Fast Doubling method from https://www.nayuki.io/page/fast-fibonacci-algorithms interestingly proved to be slower than the FinalValue and AllValues module implementations above.

The winner so far is the FibStream.fibonacci implementation using the Stream.unfold function. It yielded a time of 9493829 microseconds or 9.49 seconds with a value of 1_000_000.