[erlang-questions] speeding up 3N+1

June Kim <>
Sat Apr 7 15:18:59 CEST 2007

```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,

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

```