[erlang-questions] speeding up 3N+1
Kostis Sagonas
kostis@REDACTED
Thu Apr 12 15:30:55 CEST 2007
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
More information about the erlang-questions
mailing list