竹内関数をメモ化とか遅延で高速化してみた ref: http://qiita.com/items/b3f9ab63c63e9e6399e6

file10.txt

$ node tak.js simple 13 7 0

file2.txt

benchmark : simple tak(13,7,0) : 10 times
1 : 0.848564657 seconds
2 : 0.84946041 seconds
3 : 0.846620912 seconds
4 : 0.850074494 seconds
5 : 0.849625192 seconds
6 : 0.847950572 seconds
7 : 0.848873124 seconds
8 : 0.845893361 seconds
9 : 0.847051968 seconds
10 : 0.847635833 seconds
average : 0.8481750523 seconds

file3.txt

benchmark : simple tak(15,5,0) : 10 times
1 : 27.27188912132 seconds
2 : 27.27261219555 seconds
3 : 27.2710481851 seconds
4 : 27.27377410339 seconds
5 : 27.27219512001 seconds
6 : 27.27109614298 seconds
7 : 27.27095988127 seconds
8 : 27.27129093939 seconds
9 : 27.27283837469 seconds
10 : 27.27099590527 seconds
average : 27.271869996897 seconds

file5.txt

benchmark : cached tak(13,7,0) : 10 times
1 : 0.004029464 seconds
2 : 0.001785805 seconds
3 : 0.002380503 seconds
4 : 0.001236721 seconds
5 : 0.00123387 seconds
6 : 0.001223036 seconds
7 : 0.001720235 seconds
8 : 0.001174002 seconds
9 : 0.001174571 seconds
10 : 0.001252116 seconds
average : 0.001721032 seconds

file6.txt

benchmark : cached tak(15,5,0) : 10 times
1 : 0.004467934 seconds
2 : 0.00357218 seconds
3 : 0.001740761 seconds
4 : 0.001696287 seconds
5 : 0.002223133 seconds
6 : 0.001609049 seconds
7 : 0.001605058 seconds
8 : 0.001717383 seconds
9 : 0.001610759 seconds
10 : 0.001676901 seconds
average : 0.002191945 seconds

file8.txt

benchmark : lazy tak(13,7,0) : 10 times
1 : 0.000188729 seconds
2 : 0.000034211 seconds
3 : 0.000025088 seconds
4 : 0.001525802 seconds
5 : 0.000013684 seconds
6 : 0.000014825 seconds
7 : 0.000013684 seconds
8 : 0.000013684 seconds
9 : 0.000012544 seconds
10 : 0.000013115 seconds
average : 0.000185537 seconds

file9.txt

benchmark : lazy tak(15,5,0) : 10 times
1 : 0.00019044 seconds
2 : 0.00003193 seconds
3 : 0.001436285 seconds
4 : 0.000018246 seconds
5 : 0.000014254 seconds
6 : 0.000013684 seconds
7 : 0.000013684 seconds
8 : 0.000012544 seconds
9 : 0.000013685 seconds
10 : 0.000011973 seconds
average : 0.000175673 seconds

tak-lazy.js

/**
 * 遅延版竹内関数
 */
function lazyTak(x, y, z) {
  var
  lazy = function(fn) {
    var
    result,
    forced = false;
    //暗黙の型変換を利用するのでvalueOfを持ったオブジェクトを返す。
    return {
      valueOf: function() {
        if(!forced) {
          result = fn();
          forced = true;
        }
        return result;
      },
    };
  },
  tak = function(x, y, z) {
    if(x <= y) return +y;
    return tak(
      tak(x - 1, y, z),
      tak(y - 1, z, x),
      lazy(function(){return tak(z - 1, x, y);}));
  };
  return tak(x, y, z);
}

tak-memo.js

/**
 * 結果をメモ化した竹内関数
 */
function memoTak(x, y, z) {
  var
  memo = {},
  tak = function(x, y, z) {
    if([x, y, z] in memo) return memo[[x, y, z]];
    return memo[[x, y, z]] = x <= y ? y :
          tak(tak(x - 1, y, z),
              tak(y - 1, z, x),
              tak(z - 1, x, y));
  }
  return tak(x, y, z);
}

tak-simple.js

/**
 * 定義通りの竹内関数
 **/
function simpleTak(x, y, z) {
  return x <= y ? y :
    simpleTak(simpleTak(x - 1, y, z),
              simpleTak(y - 1, z, x),
              simpleTak(z - 1, x, y));
}

tak-util.js

/**
 * ベンチマーク用関数
 * @param {Number} n 実行する回数
 * @param {Function} fun 測定する関数
 * @return {Object} averageに平均が、resultsに各結果が入ったオブジェクト
 **/
function bench(n, fun) {
  var
  i,
  start, finish, average,
  results = [];
  for(i = 1; i <= n; i++) {
    console.log('start : %d', i);
    //process.hrtimeでナノ秒を取得できる
    start = process.hrtime();
    fun();
    //process.hrtimeに引数を渡すとその差を返す
    finish = process.hrtime(start);
    console.log('finish : %d', i);
    //[秒, ナノ秒]という形式の配列なのでナノ秒に変換
    results.push(finish[0] * 1e9 + finish[1]);
  }
  average = results.reduce(function(a,b) {
    return a + b;
  }) / n;
  return {
    results: results,
    average: average,
  };
}