[erlang-questions] speeding up 3N+1

Vance Shipley vances@REDACTED
Sat Apr 7 16:33:32 CEST 2007


On Sat, Apr 07, 2007 at 10:18:59PM +0900, June Kim wrote:
}  Please have a look at this famous problem. http://acm.uva.es/p/v1/100.html

June,

In functional programming you pass arguments instead of using
global variables.

-module(threeNplus1).
-export([do/1]).

do(1) ->
        io:fwrite(" 1~n");
do(N) when N rem 2 /= 0 ->
        io:fwrite(" ~b", [N]),
        do(3 * N + 1);
do(N) ->
        io:fwrite(" ~b", [N]),
        do(N div 2).

1> threeNplus1:do(22).
 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
ok

}  cycle(1) ->
}      1;
}  cycle(N) ->
}      case get(N) of
}      undefined ->
}          SN = if
}               N rem 2 =:= 0 ->
}               1 + cycle(N div 2);
}               true ->
}               2 + cycle((3 * N + 1) div 2)
}           end,
}          put(N, SN),
}          SN;
}      Cached ->
}          Cached
}      end.

The really big problem above is in tail recursion.  You don't
want to have to wait for the answer to cycle(N div 2) before
knowing the answer to cycle(N).

	-Vance




More information about the erlang-questions mailing list