Generating Sum of First 100000 / 1 Million Fibonacci terms in elixir

Questions / Help
, ,
1

For a Fibonacci series/sum generation :

defmodule Fib do
	def dofib(0), do: []
	def dofib(n) when is_integer(n), do: dofib(0, 1, n-1)
	def dofib(cur, _, 0), do: [cur]
	def dofib(cur, next, count), do: [cur] ++ dofib(next, cur+next, count-1)
end

# 10000 |> Fib.dofib |> List.foldl(0, &(&1 + &2))

This may work < `100K.

What optimizations or de cluttering is possible here?:

Stream.unfold([1, 0], fn([h|t]=acc)-> {h, [h + List.first(t)|acc]} end) 
|> Stream.take(100000) 
|> Flow.from_enumerable 
|> Flow.partition(stages: 100) 
|> Flow.reduce(fn -> 0 end, fn(n, acc)-> n + acc end) 
|> Flow.departition(fn -> 0 end, &(&1 + &2), &(&1)) 
|> Stream.into(File.stream!("output.txt", [:delayed_write, encoding: :utf8])) 
|> Stream.run

It fails at 200K.

2

The key here is to avoid having a complete list of Fibonacci numbers all in memory all at once. Here’s a stream implementation:

  defmodule StreamFib do
    def normal() do
      Stream.unfold(
        {0, 0},
        fn
          {0, 0} -> {1, {0, 1}}
          {f_n2, f_n1} -> {f_n1 + f_n2, {f_n1, f_n1 + f_n2}}
        end
      )
    end

    def partial_sum() do
      Stream.scan(normal(), 0, &(&1 + &2))
    end
  end

Then:

StreamFib.partial_sum() |> Stream.drop(1000000) |> Stream.take(1) |> Enum.to_list() |> hd()

will generate the millionth partial sum. At this point, the blocker is the speed of arbitrary-precision arithmetic; the millionth partial sum has 208988 digits!

EDIT:

Two other things to think about:

  • be careful with the exact definition of the sequence, and verify that it starts with the numbers you expect. There are a variety of mathematical definitions that disagree very slightly

  • an even cheaper way to compute the partial sum is to rearrange the terms - see Wikipedia for details

5 Likes
3

Actually, we don’t need a stream here at all. Plain old good Enum.reduce/3 would perfectly do.

4

I saw your soln
Do you think stream is an overkill for this kind of linearly dependent problem?

1 Like
5

Stream is really a problem here I think, even though it might take stress from memory and GC, it adds computational overhead and slowlyness.

Thats why I’d prefer a straight approach of a specialised function:

iex(1)> defmodule Fib do
...(1)>   def sum_fib(n), do: sum_fib(0, 1, n-1, 0)
...(1)>   def sum_fib(_, _, 0, sum), do: sum
...(1)>   def sum_fib(cur, next, n, sum), do: sum_fib(next, cur+next, n-1, sum + cur)
...(1)> end
iex(2)> :timer.tc(Fib, :sum_fib, [100_000]) |> elem(0)
304427
iex(3)> :timer.tc(Fib, :sum_fib, [1_000_000]) |> elem(0)
30884469

Since I hacked this together quickly, I might have missed adding the last fibonacci number, but I do not think it would change much about the timing.

And as you can see the sum of the first million is in ~30 seconds on my machine.

1 Like
6

Stream is not an overkill, it’s just an absolutely redundant link is the chain. Enum.reduce/3 does not produce the enormously huge list in the memory and processes the input one by one element.

So what particular problem would solve the stream here?—None.

1 Like