luah 1.1.0

Unofficial lua impl by HydroRoll-Team.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

-- The Computer Language Benchmarks Game
-- http://benchmarksgame.alioth.debian.org/
-- contributed by Mike Pall

local function BottomUpTree(item, depth)
    if depth > 0 then
      local i = item + item
      depth = depth - 1
      local left, right = BottomUpTree(i-1, depth), BottomUpTree(i, depth)
      return { item, left, right }
    else
      return { item }
    end
  end
  
  local function ItemCheck(tree)
    if tree[2] then
      return tree[1] + ItemCheck(tree[2]) - ItemCheck(tree[3])
    else
      return tree[1]
    end
  end
  
  local N = 10 -- input argument
  local mindepth = 4
  local maxdepth = mindepth + 2
  if maxdepth < N then maxdepth = N end
  
  do
    local stretchdepth = maxdepth + 1
    local stretchtree = BottomUpTree(0, stretchdepth)
    print("stretch tree of depth", stretchdepth, "check: ", ItemCheck(stretchtree))
  end
  
  local longlivedtree = BottomUpTree(0, maxdepth)
  
  for depth=mindepth,maxdepth,2 do
    local iterations = 2 ^ (maxdepth - depth + mindepth)
    local check = 0
    for i=1,iterations do
      check = check + ItemCheck(BottomUpTree(1, depth)) +
              ItemCheck(BottomUpTree(-1, depth))
    end
    print(iterations*2, "trees of depth", depth, "check: ", check)
  end
  
  print("long lived tree of depth", maxdepth, "check:", ItemCheck(longlivedtree))