source code
% The Computer Language Benchmarks Game
% https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
%
% contributed by Isaac Gouy (Erlang novice)
% parallelized by Kevin Scaldeferri
-module(binarytrees).
-export([main/1]).
-export([depth/2]).
-define(Min,4).
main([Arg]) ->
N = list_to_integer(Arg),
Max = lists:max([?Min+2,N]),
Stretch = Max + 1,
io:fwrite("stretch tree of depth ~w\t check: ~w~n",
[ Stretch, itemCheck(bottomUp(Stretch)) ]),
LongLivedTree = bottomUp(Max),
depthLoop(?Min,Max),
io:fwrite("long lived tree of depth ~w\t check: ~w~n",
[ Max, itemCheck(LongLivedTree) ]),
halt(0).
depthLoop(D,M) ->
Results = rpc:pmap({?MODULE, depth}, [M], lists:seq(D, M, 2)),
lists:foreach(fun(Result) ->
io:fwrite("~w\t trees of depth ~w\t check: ~w~n", Result)
end,
Results).
depth(D,M) ->
N = 1 bsl (M-D + ?Min),
[ N, D, sumLoop(N,D,0) ].
sumLoop(0,_,Sum) -> Sum;
sumLoop(N,D,Sum) ->
sumLoop(N-1,D, Sum + itemCheck(bottomUp(D))).
bottomUp(0) -> {nil, nil};
bottomUp(D) -> {bottomUp(D-1), bottomUp(D-1)}.
itemCheck(nil) -> 0;
itemCheck({Left,Right}) ->
1 + itemCheck(Left) + itemCheck(Right).
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
Erlang/OTP 26 [erts-14.2.2]
[source] [64-bit] [smp:4:4]
[ds:4:4:10] [async-threads:1] [jit:ns]
Sun, 03 Mar 2024 19:09:31 GMT
MAKE:
mv binarytrees.erlang-2.erlang binarytrees.erl
/opt/src/otp_src_26.2.2/bin/erlc binarytrees.erl
1.64s to complete and log all make actions
COMMAND LINE:
/opt/src/otp_src_26.2.2/bin/erl -smp enable -noshell -run binarytrees main 21
PROGRAM OUTPUT:
stretch tree of depth 22 check: 8388607
2097152 trees of depth 4 check: 65011712
524288 trees of depth 6 check: 66584576
131072 trees of depth 8 check: 66977792
32768 trees of depth 10 check: 67076096
8192 trees of depth 12 check: 67100672
2048 trees of depth 14 check: 67106816
512 trees of depth 16 check: 67108352
128 trees of depth 18 check: 67108736
32 trees of depth 20 check: 67108832
long lived tree of depth 21 check: 4194303