[erlang-questions] speeding up 3N+1

[June Kim]

Hello,

First of all, please keep in mind that I am a newbie in Erlang. (sorry
if the codes annoy you)

Please have a look at this famous problem. http://acm.uva.es/p/v1/100.html

The input number can be upto 1,000,000. (let's just suppose 1 million
is included, even though the problem states the maximal input is less
than 1 million) Let's see the worst case(when the start/end pair is
{1, 1000000}) time performance of the program.

Following is a trial at solving this problem:

-module(tnp1_process_dict).
-compile(export_all).

cycle(1) ->
    1;
cycle(N) ->
    case get(N) of
    undefined ->
        SN = if
             N rem 2 =:= 0 ->
             1 + cycle(N div 2);
             true ->
             2 + cycle((3 * N + 1) div 2)
         end,
        put(N, SN),
        SN;
    Cached ->
        Cached
    end.

max(A, B) ->
    lists:max(lists:map(fun cycle/1, lists:seq(A, B))).

Actually, it's from a friend of mine, who is also in the same Erlang
community(we are all just novices though) with me. It's quite
effiecient.

1> timer:tc(tnp1_process_dict,max,[1,1000000]).
{2547000,525}

Less than 3 seconds on my sluggish machine. Good.

However, I didn't quite like the solution. It uses the process
dictionary. From reading Erlang books and manuals, I thought the
process dictionary should be the last resort for this kind of usage. I
thought I could deal the problem without using the process dictionary,
without trading off the speed.

Following is my trial:

-module(tnp1_functional).
-compile(export_all).

newCache()->
    dict:from_list([{1,1}]).
store(K,V,Cache)->
    dict:store(K,V,Cache).
find(K,Cache)->
    dict:find(K,Cache).

nn(N) when N rem 2 =:= 0 ->
    N div 2;
nn(N) ->
    3*N+1.

update([],_,Cache)->
    Cache;
update([H|ToStore],V,Cache)->
    Cache2=store(H,V+1,Cache),
    update(ToStore,V+1,Cache2).

cl(N,Cnt,Cache,ToStore)->
    case find(N,Cache) of
	{ok,V} ->
	    Cache2=update(ToStore,V,Cache),
	    {Cnt+V,Cache2};
 	error  ->
	    cl(nn(N),Cnt+1,Cache,[N|ToStore])
    end.

maxcl(From,To,Cache,Max) when From>To ->
     {Max,Cache};
maxcl(From,To,Cache,Max)->
    {Cl,Cache2}=cl(From,0,Cache,[]),
    maxcl(From+1,To,Cache2,lists:max([Cl,Max])).

maxcl(From,To)->
    Cache=newCache(),
    maxcl(From,To,Cache,1).

max(From,To)->
    {V,_}=maxcl(From,To),
    V.

It's much longer. And much slower; I'd say excruciatingly.

1> timer:tc(tnp1_functional,max,[1,100000]).
{7953000,351}

See? It's 100,000, not one million, even. When I ran it with one
million, it didn't end at least in a couple of minutes.

Maybe my choice of using dict is wrong? Could ets be substantially
better? Or my approach totally wrong? I don't know yet. (I'll
experiment with other data structures and approaches, though)

Okay, that's it. I would appreciate any suggestions for improvement.

June