binarytrees.sgs

// 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)));