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

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.

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

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

Do you think stream is an overkill for this kind of linearly dependent problem?

1 Like

`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

`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