[erlang-questions] speeding up 3N+1
Sun Apr 8 01:07:42 CEST 2007
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:
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 ->
max(I, J, Max) ->
Count = do(I, 0),
Count > Max ->
max(I + 1, J, Count);
max(I + 1, J, Max)
1> threeNplus1:max(1, 10).
1 10 20
2> threeNplus1:max(100, 200).
100 200 125
3> threeNplus1:max(201, 210).
201 210 89
4> threeNplus1:max(900, 1000).
900 1000 174
} Could you help me improving the speed of these codes with FP approach?
5> timer:tc(threeNplus1, max, [1, 1000000]).
1 1000000 525
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."
More information about the erlang-questions