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}] ->
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.

Annunci