[erlang-questions] speeding up 3N+1

[Kostis Sagonas]

ok wrote:
> On 8 Apr 2007, at 1:18 am, June Kim wrote:
>> Please have a look at this famous problem. http://acm.uva.es/p/ 
>> v1/100.html
> 
> cycle_length(N) when is_integer(N), N >= 1 ->
>      cycle_length(N, 1).
> 
> cycle_length(1, L) -> L;
> cycle_length(N, L) ->
>      cycle_length(case N band 1 of 1 -> 3*N+1; 0 -> N div 2 end, L+1).
> 
> The conditions of the problem ensure that this will not in fact involve
> any cycle at all; "cycle length" is an astoundingly bad name for the
> quantity to be computed.
> 
> max_cycle_length(I, J) when is_integer(I), is_integer(J), I =< J ->
>      max_cycle_length(I+1, J, cycle_length(I)).
> 
> max_cycle_length(I, J, M) when I > J -> M;
> max_cycle_length(I, J, M) ->
>      max_cycle_length(I+1, J, max(L, cycle_length(J)).

This last function cannot possibly be correct.
There is a parenthesis missing and L and M are singleton variables.
Moreover, even if the L gets substituted with M, this implements a
different algorithm.

The correct function should read:

max_cycle_length(I, J, M) when I > J -> M;
max_cycle_length(I, J, M) ->
     max_cycle_length(I+1, J, max(M, cycle_length(I))).

and then the algorithm is that which is required by the 3N+1 problem.


I also wonder why nobody has suggested compilation to native code for 
speeding up execution in this case.  On my system (which has some extra 
optimizations, not yet present in R11B-4) I get:

1> c(threeNplus1_ok).
{ok,threeNplus1_ok}
2> timer:tc(threeNplus1_ok, max_cycle_length, [1,1000000]).
{29245755,525}
3> hipe:c(threeNplus1_ok).
{ok,threeNplus1_ok}
4> timer:tc(threeNplus1_ok, max_cycle_length, [1,1000000]).
{2517352,525}

I.e. more than 10 times faster.  The native code compiler in R11B-4 
should give something like 3-4 times speedup compared with BEAM.

Kostis