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

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.