Fibonacci versions in Erlang. Naively recursive, array and list.

fibs.erl

%%%----------------------------------------------------------------------------
%%% $ erl -noshell -s fibs main 40
%%% TRANSLATED ARRAY:    102334155   0.001755 seconds
%%% TRANSLATED LIST:     102334155   0.000048 seconds
%%% REVERSE ORDER LIST:  102334155   0.000004 seconds
%%% MINIMAL ARITHMETIC:  102334155   0.000001 seconds
%%% NAIVE RECURSIVE:     102334155   8.383385 seconds
%%%----------------------------------------------------------------------------


-module(fibs).
-export([main/1]).


main([Arg|_]) ->
    N = list_to_integer(atom_to_list(Arg)),
    MainPid = self(),
    FibFuns = [
        fun() -> {'NAIVE RECURSIVE',    fib_rec_naive(N)} end,
        fun() -> {'TRANSLATED ARRAY',   fib_arr(N)} end,
        fun() -> {'TRANSLATED LIST',    fib_list_naive(N)} end,
        fun() -> {'REVERSE ORDER LIST', fib_list(N)} end,
        fun() -> {'MINIMAL ARITHMETIC', fib_arith(N)} end
    ],

    lists:foreach(
        fun(FibFun) ->
            spawn(
                fun() ->
                    TBeg = now(),
                    {Type, Fib} = FibFun(),
                    TEnd = now(),
                    TDiff = (timer:now_diff(TEnd, TBeg) / 1000000),
                    IoList = [Type, Fib, TDiff],
                    io:format("~s: \t ~b \t ~f seconds ~n", IoList),
                    MainPid ! done
                end
            )
        end,
        FibFuns
    ),

    wait_n_halt(length(FibFuns)).


%%-----------------------------------------------------------------------------
wait_n_halt(0) -> halt();
wait_n_halt(N) ->
    receive
        done -> wait_n_halt(N - 1)
    end.


%%-----------------------------------------------------------------------------
%% Naive recursive.
%%-----------------------------------------------------------------------------
fib_rec_naive(0) -> 0;
fib_rec_naive(1) -> 1;
fib_rec_naive(N) -> fib_rec_naive(N - 1) + fib_rec_naive(N - 2).


%%-----------------------------------------------------------------------------
%% Naive translation of mutable array-style.
%%-----------------------------------------------------------------------------
fib_arr(0) -> 0;
fib_arr(1) -> 1;
fib_arr(N) ->
    Begin = 0,
    End = N + 1,
    fib_arr(N, End, 2, array:from_list(lists:seq(Begin, End))).

fib_arr(N, End, I, Fibs) when I == End -> array:get(N, Fibs);
fib_arr(N, End, I, Fibs) ->
    Fib = array:get(I-1, Fibs) + array:get(I-2, Fibs),
    fib_arr(N, End, I+1, array:set(I, Fib, Fibs)).


%%-----------------------------------------------------------------------------
%% Naive translation of mutable array-style, but using list structure.
%%-----------------------------------------------------------------------------
fib_list_naive(0) -> 0;
fib_list_naive(1) -> 1;
fib_list_naive(N) ->
    fib_list_naive(N + 2, 3, [0, 1]).

fib_list_naive(End, I, Fibs) when I == End -> lists:last(Fibs);
fib_list_naive(End, I, Fibs) ->
    Fib = lists:nth(I-1, Fibs) + lists:nth(I-2, Fibs),
    fib_list_naive(End, I+1, Fibs++[Fib]).


%%-----------------------------------------------------------------------------
%% Idiomatic use of the list (in reverse order).
%% Credit: yrashk (Yurii Rashkovskii)
%%-----------------------------------------------------------------------------
fib_list(0) -> 0;
fib_list(1) -> 1;
fib_list(N) ->
    fib_list(N + 1, [1,0]).

fib_list(End, [H|_]=L) when length(L) == End -> H;
fib_list(End, [A,B|_]=L) ->
    fib_list(End, [A+B|L]).


%%-----------------------------------------------------------------------------
%% Minimal arithmetic.
%% Credit: richcarl (Richard Carlsson)
%%-----------------------------------------------------------------------------
fib_arith(N) when N > 0 -> fib_arith(N, 0, 1).

fib_arith(0, F1, _F2) -> F1;
fib_arith(N, F1,  F2) -> fib_arith(N - 1, F2, F1 + F2).

Note that in fib_list, it would be much more efficient to keep the list in reverse order. Appending each new Fib to the Fibs list, as you do now, takes time proportional to the size of Fibs, so it adds a quadratic component (N*N) to the execution time. Simply doing [Fib | Fibs] instead takes a very small constant time. Similarly, each call to lists:nth(N, Fibs) takes time proportional to N (and you call it twice). This will blow up for large N.

The fib_arr version will use N*log(N) time, because that is how all the calls to array:set() and array:get() behave (they don't run it constant time since the arrays are nondestructively updated and use a tree structure internally). For small N, the fib_list version is likely to be faster because of the differences in initial overhead, but fib_arr will eventually overtake it and win by a greater margin the larger N gets (probably after N>200 or more).

Still, these two are faster than the naively recursive fib_rec, because if you think about it, the time it takes to run fib_rec(N) is proportional to fibonacci(N) - the run times for each recursive call gets summed up in the same way that the Fibonacci series itself is summed up. This grows very quickly, which is why it gets beaten by even the fib_list version for all but the smallest values of N.

But there is really no reason to keep track of all the Fibs while you loop; just remembering the last 2 is enough. Try this:

fib(N) when N >= 0 -> fib(N, 0, 1).

fib(0, _F1, F2) -> F2;
fib(N,  F1, F2) -> fib(N - 1, F2, F1 + F2).

Thank you so much for your explanation, Richard!

It was, indeed, very silly for me to use the array module - pretty-much a forced translation of a mutable array style... Come to think of it, what IS a good use-case for the array module in favor of dict/gb_trees?

As for the way I used the list, it was a serious brain-fart :), again just a rushed translation from the way I used the array above it. I am, indeed, aware that a linked-list should be used in reverse order, but, alas my brain still isn't fully rewired to think in those terms just yet...

I revised the code to include your (WAY FASTER) fib function as well as Yurii's suggested revision to the usage of the list (https://gist.github.com/aafded15a61bc081fcd1). I just had to make a minor change: returning F1 instead of F2.

Again, thank you so much!

Glad to help out. (I made a note about the use of length(L) in Yurii's example that you should also read.) It takes a little while to learn to program in a functional style, so don't worry if you're not writing perfect code from day one. But the lessons tend to make you a better programmer also in more traditional languages, so they are well worth the time and effort.

The array module is good whenever you store something using integers as keys. They are more efficient than dict or gb_trees, since they don't actually need to store each key, and the access times are faster, even though the complexity is still logarithmic. If you don't have many entries (less than 100 or so), the simplicity of lists generally beats the smarter implementation in the dict and gb_trees modules. However, if you have thousands of entries, random access in lists is no longer a good alternative, so if you expect to have to scale up, start with a suitable data structure right away.

You might want to try to benchmark these functions for some large values of N, to see at what point fib_list_naive starts to perform worse than fib_arr.

Looks like around 150 is where array starts to get ahead, and it is clear at 200:

$ for N in `seq 100 25 200`; do echo $N; erl -noshell -s fibs main $N; echo; done
100
REVERSE ORDER LIST:    0.000033 seconds
MINIMAL ARITHMETIC:    0.000005 seconds
TRANSLATED LIST:       0.000589 seconds
TRANSLATED ARRAY:      0.002527 seconds

125
REVERSE ORDER LIST:    0.000026 seconds
MINIMAL ARITHMETIC:    0.000004 seconds
TRANSLATED LIST:       0.000553 seconds
TRANSLATED ARRAY:      0.001852 seconds

150
REVERSE ORDER LIST:    0.000037 seconds
MINIMAL ARITHMETIC:    0.000005 seconds
TRANSLATED ARRAY:      0.001944 seconds
TRANSLATED LIST:       0.001977 seconds

175
REVERSE ORDER LIST:    0.000047 seconds
MINIMAL ARITHMETIC:    0.000008 seconds
TRANSLATED ARRAY:      0.002247 seconds
TRANSLATED LIST:       0.002550 seconds

200
REVERSE ORDER LIST:    0.000057 seconds
TRANSLATED ARRAY:      0.002178 seconds
MINIMAL ARITHMETIC:    0.000008 seconds
TRANSLATED LIST:       0.003183 seconds

Note, for sanity, I removed the actual fib number and the naive recursive version... :)

More testing with larger N's returned some pretty weird results:

$ for N in `seq 1000 1000 10000`; do echo $N; erl -noshell -s fibs main $N; echo; done
1000
REVERSE ORDER LIST:    0.001472 seconds
MINIMAL ARITHMETIC:    0.000067 seconds
TRANSLATED ARRAY:      0.009506 seconds
TRANSLATED LIST:       0.036698 seconds

...

10000
REVERSE ORDER LIST:    0.504411 seconds
MINIMAL ARITHMETIC:    0.271899 seconds
TRANSLATED ARRAY:      0.532638 seconds
TRANSLATED LIST:       3.118408 seconds

OK, now it's really clear just how bad the translated list version is. Let's
make it really, really clear:

$ for N in `seq 50000 50000 100000`; do echo $N; erl -noshell -s fibs main $N; echo; done
50000
TRANSLATED ARRAY:      0.786733 seconds
MINIMAL ARITHMETIC:    2.445060 seconds
REVERSE ORDER LIST:    21.529261 seconds
TRANSLATED LIST:       66.472364 seconds

100000
TRANSLATED ARRAY:      2.114121 seconds
MINIMAL ARITHMETIC:    4.714604 seconds
REVERSE ORDER LIST:    222.662831 seconds
TRANSLATED LIST:       281.607757 seconds

Wait, WHAT?! Array now beats the minimal arithmetic? How about even larger N:

$ erl -noshell -s fibs main 1000000
MINIMAL ARITHMETIC:    15.846427 seconds
^C

After a few minutes of tapped-out system ram, I killed it... Very
interesting...

Naive implementation, which shows memoization technique. May be useful when fib is called multiple times with comparable numbers as argument.

fib(N) ->
  case ets:info(fib) of
    undefined ->
      ets:new(fib, [named_table]),
      ets:insert_new(fib, {0,0}),
      ets:insert_new(fib, {1,1});
    _ -> ok
  end,
  fib_int(N).

fib_int(N) ->
  case ets:lookup(fib, N) of
    [] ->
      F = (fib_int(N-1)+fib_int(N-2)),
      ets:insert_new(fib, {N, F}),
      F;
    [{N, F}] ->
      F
  end.

function fib_rec_naive does not tail-recursive as mentioned in comment

@cystbear: yes, i think so. It's tree recursion.