benchmarks_game/binary_trees.fz
# https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html#binarytrees
# based on the c program by Jeremy Zerfas
binary_trees is
Node(left Node|unit, right Node|unit) ref is
create_tree(depth i32) Node is
if(depth > 0) then
Node create_tree(depth - 1) create_tree( depth - 1)
else
Node Node(unit, unit) unit
checksum(n Node) i32 is
match n.left
unit => 1
l Node =>
match n.right
unit => 1
r Node => (checksum(l) + checksum(r) + 1)
min_depth := 4
max_depth := 21
stretch_tree := create_tree(max_depth+1)
checksum := checksum(stretch_tree)
say "stretch tree of depth {max_depth+1}\t check: $checksum"
long_lived_tree := create_tree(max_depth)
for depth in (min_depth..max_depth).filter(x -> x % 2 = 0) do
iterations := (u64 1) << (max_depth - depth + min_depth).as_u64
total_trees_checksum := mut 0
for _ in ((u64 1)..iterations) do
tree := create_tree(depth)
total_trees_checksum <- total_trees_checksum.get + checksum(tree)
say "$iterations\t trees of depth {depth}\t check: {total_trees_checksum.get}"
say "long lived tree of depth $max_depth\t check: {checksum(long_lived_tree)}"
last changed: 2023-11-14