Pasted

// The Computer Language Benchmarks Game
// http://benchmarksgame.alioth.debian.org/
 
include "string", "math";
 
function BottomUpTree( item, depth )
{
  if( depth > 0 )
  {
    i = item + item;
    depth = depth - 1;
    left = BottomUpTree(i-1, depth);
    right = BottomUpTree(i, depth);
    return [item, left, right];
  }
  else
  {
    return [item];
  }
}
 
function ItemCheck(tree)
{
  if( @tree[1] )
    return tree[0] + ItemCheck(tree[1]) - ItemCheck(tree[2]);
  else
    return tree[0];
}
 
var N = toreal(@argv[1]) ?? 0.0;
var mindepth = 4;
var maxdepth = mindepth + 2;
if( maxdepth < N ) maxdepth = N;
 
{
  var stretchdepth = maxdepth + 1;
  var stretchtree = BottomUpTree(0, stretchdepth);
  print(string_format("stretch tree of depth {1:d}\t check: {2:d}\n",
    stretchdepth, ItemCheck(stretchtree)));
}
 
var longlivedtree = BottomUpTree(0, maxdepth);
 
for( depth=mindepth; depth <= maxdepth; depth += 2 )
{
  var iterations = pow( 2, maxdepth - depth + mindepth);
  var check = 0;
  for( i=1; i <= iterations; ++i)
  {
    check = check + ItemCheck(BottomUpTree(1, depth)) +
            ItemCheck(BottomUpTree(-1, depth));
  }
  print(string_format("{1:d}\t trees of depth {2:d}\t check: {3:d}\n",
    iterations*2, depth, check));
}
 
print(string_format("long lived tree of depth {1:d}\t check: {2:d}\n",
  maxdepth, ItemCheck(longlivedtree)));