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).

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.