[erlang-questions] speeding up 3N+1

[Vance Shipley]

June,

OK, I took more than thirty seconds this time. :)

On Sat, Apr 07, 2007 at 11:54:24PM +0900, June Kim wrote:
}  My version using dict, which is also included in my original posting(I
}  don't think you have seen it yet), is tail-recursive and functional,
}  but slow.

It's more functional than your friend's but not purely functional.
Here's a completely functional solution to the problem:

-module(threeNplus1).
-export([max/2]).

do(1, Acc) ->
    Acc + 1;
do(N, Acc) when N rem 2 /= 0 ->
    do(3 * N + 1, Acc + 1);
do(N, Acc) ->
    do(N div 2, Acc + 1).

max(I, J) ->
    io:fwrite("~b ~b ", [I, J]),
    max(I, J, 0).
max(I, J, Max) when I > J ->
    io:fwrite("~b~n", [Max]);
max(I, J, Max) ->
    Count = do(I, 0),
    if
        Count > Max ->
            max(I + 1, J, Count);
        true ->
            max(I + 1, J, Max)
    end.

1> threeNplus1:max(1, 10).
1 10 20
ok
2> threeNplus1:max(100, 200).
100 200 125
ok
3> threeNplus1:max(201, 210).
201 210 89
ok
4> threeNplus1:max(900, 1000).
900 1000 174
ok

}  Could you help me improving the speed of these codes with FP approach?

5> timer:tc(threeNplus1, max, [1, 1000000]).
1 1000000 525
{9860100,ok}

The reference you gave didn't mention any performance objectives.
For my money under ten seconds is good enough for this exercise.
One of the tenants in the Erlang community is "optimize last".
Quoting from the original Erlang book "The primary concern must
always be of correctness, and to this aim we encourage the development
of small and beautiful algorithms which are `obviously' correct."

    -Vance