4 ms·
Elixir can be made much faster via tail call optimization. Something like: def fibonacci(n) when n >= 0, do: fib(0, 1, n) defp fib(a, b, n) do case n
by acangiano 8y ago
Elixir can be made much faster via tail call optimization.
Something like:
def fibonacci(n) when n >= 0, do: fib(0, 1, n)
defp fib(a, b, n) do
case n do
0 ->
a
_ ->
fib(b, a + b, n - 1)
end
end
- brightball 8y agoThere's a PR there to do just that. I don't follow the reasoning that it's not been accepted. It's also using Elixir script instead of precompiled Elixir. https://github.com/drujensen/fib/pull/33 https://github.com/drujensen/fib/pull/33
- acangiano 8y agoYeah, I don't think this breaks any of the rules. We are still using recursion. Just leveraging what the language has to offer.
- alangpierce 8y agoThe algorithm being benchmarked is the naive double-recursive fibonacci algorithm, which ends up performing over a billion addition operations in this case. The tail-recursive function above is the iterative bottom-up fibonacci algorithm that does it in about 50 addition operations. It's true that both use recursion, but the second is definitely not the tail-recursive version of the first. It is possible to do a form of tail call optimization for the double-recursive algorithm, described here: https://news.ycombinator.com/item?id=18096804 https://news.ycombinator.com/item?id=18096804 This reduces the number of total function calls but not the number of additions (since it's not changing the algorithm, just the way the function invocation strategy when running the algorithm).
- pmontra 8y agoAgreed. Everybody uses TCO in Elixir. It's the standard way to write servers and store state. So it makes sense to use it the benchmark or it will be very un-Elixir.
- avip 8y agoYou could do that in python as well: def fib(a, b, n): return a if n == 0 else fib(b, a+b, n-1) You'll get x300 speed. The test cases are much more revealing without such constructions.