I was looking about problems solved in erlang (I’m a newbie to this language) when I found this:

Problem 14 of Project Euler deals with the Collatz conjecture. In particular, how long does it take for a particular integer to be reduced to 1? [...]  This is what I’m calling a “Collatz number”. Problem 14 is to find the number less than a million which has the largest Collatz number.

Here is Jeremy Frens solution in erlang (I modified maximum_collatz_under/1 using list comprehensions) :

collatz(1) -> 1;
collatz(N) ->
    if
	N rem 2 =:= 0 ->
	    1 + collatz(N div 2);
	true ->
	    1 + collatz(3 * N + 1)
    end.

maximum_collatz_under(N) ->
    lists:max([{collatz(X), X} || X<-lists:seq(1, N)]).

This is a brute-force solution but erlang seems to be very fast!!!

Average of 3 attempts: 14988 ms

The collatz(N) function repeats a lot of computations: to compute collatz(32), it would be helpful if I already know collatz(16). And to compute collatz(5), it also helps to known collatz(16). This is where memoization would help

So I tried to implement memoization in erlang (although in this case it’s not necessary).

An example of memoization can be found here. We can use ets to store a calculated value and avoid to recalculate it.

startcollatz()->
    %%checks if the ets table exists and creates one if it doesn't
    case ets:info(collatz) of
	undefined->
	    ets:new(collatz, [public, named_table]),
            %%inserts collatz(1)=1
	    ets:insert(collatz,{1,1});
	_ -> ok
    end.

collatz(M) ->
    %%checks if collatz(M) has already been calculated
    case ets:lookup(collatz, M) of
	[] ->
            %%calculates the value and stores it in the ets table
	    case M rem 2 =:= 0 of
		true ->
		    ets:insert(collatz,{M,Ris=1+collatz(M div 2)}),
		    Ris;
		false->
		    ets:insert(collatz,{M,Ris=1+collatz(3*M+1)}),
		    Ris
	    end;
	[{M, Val}] ->
            %%returns the value already calculated
	    Val
    end.

collatzmax(N)->
    %%create the ets if it doesn't exist
    startcollatz(),
    %%unmodified
    lists:max([{collatz(X), X} || X<-lists:seq(1, N)]).

Now it’s more efficient.

Average of 3 attempts (with the ets empty): 8558 ms
Average of 3 attempts (with the ets full): 1682 ms

The next question is: “How to memoize a generic function without rewriting everything from scratch?”
The answer is: higher-order function! In particular a function that return a fun.

The “memoize” function takes two arguments:the module and the name of the function to be memoized.
First of all it creates an ets table with the name of the function passed.
Then it returns a new fun that calls “calc” passing its arguments. In my code I’ll use this returned fun.

“Calc” does the dirty work. If a value hasn’t already been calculated, it calls apply/3 to execute the original function.

-module(memoize).
-export([memoize/2]).

memoize(Module,Fun) ->
    case ets:info(Fun) of
	undefined->
	    ets:new(Fun, [public, named_table]);
	_ -> ok
    end,
    fun(Args) -> calc(Module,Fun,Args) end.

calc(Module,Fun,Args) ->
    case ets:lookup(Fun, Args) of
        [] ->
            Value = apply(Module,Fun, Args),
            ets:insert(Fun, {Args,Value}),
            Value;
        [{Args, Value}] ->
            Value
    end.

Now I can modify maximum_collatz_under.
I assign the memoized fun to the variable F. When there’s a call to collatz, I have to call F.

Thats’all?
Nope :(. Unluckily collatz is recursive, and if I really want to memoize it I need to make some changes.
As above, I have to call F instead of collatz. So I need to pass F as an argument to collatz.

-module(collatzproblem).
-export([maximum_collatz_under/1,collatz/2]).
-import(memoize,[memoize/2]).

collatz(1,_F) -> 1;
collatz(N,F) ->
    if
	N rem 2 =:= 0 ->
	    1 + F([N div 2,F]);
	true ->
	    1 + F([3 * N + 1,F])
    end.

maximum_collatz_under(N) ->
    F = memoize(?MODULE,collatz),
    lists:max([{F([X,F]), X} || X<-lists:seq(1, N)]).

This version is slower than the second one: I think it’s for the use of apply/3.

Average of 3 attempts (with the ets empty): 12622 ms
Average of 3 attempts (with the ets full): 2488 ms

If you have any suggestions, corrections or comments please let me now.

About these ads