Decision tree regression is a machine learning technique that incorporates a set of if-then rules in a tree data structure to predict a single numeric value. For example, a decision tree regression model prediction might be, “If employee age is greater than 29.0 and age is less than or equal to 32.5 and years-experience is less than or equal to 4.0 and height is greater than 67.0 then bank account balance is $655.17.”

This blog post presents decision tree regression, implemented from scratch with JavaScript, using list storage for tree nodes (no pointers/references), a FIFO stack to build the tree (no recursion), weighted variance minimization for the node split function, and saves associated row indices in each node.

The demo data looks like:

 0.1660,  0.4406, -0.9998, -0.3953, -0.7065,  0.4840
 0.0776, -0.1616,  0.3704, -0.5911,  0.7562,  0.1568
-0.9452,  0.3409, -0.1654,  0.1174, -0.7192,  0.8054
 0.9365, -0.3732,  0.3846,  0.7528,  0.7892,  0.1345
. . .

The first five values on each line are the x predictors. The last value on each line is the target y variable to predict. The data is synthetic and was generated by a 5-10-1 neural network with random weights and bias. Therefore, the data has an underlying structure which can be predicted. There are 200 training items and 40 test items.

The key parts of the output of the demo program are:

JavaScript decision tree regression

Loading synthetic train (200), test (40)
Done

First three train x:
-0.1660   0.4406  -0.9998  -0.3953  -0.7065
 0.0776  -0.1616   0.3704  -0.5911   0.7562
-0.9452   0.3409  -0.1654   0.1174  -0.7192

First three train y:
0.484 0.1568 0.8054

Setting maxDepth = 3
Setting minSamples = 2
Setting minLeaf = 18
Using default numSplitCols = -1

Creating and training tree
Done

ID   0 | col  0 | v -0.2102 | L  1 | R  2 | y 0.3493 | leaf F
ID   1 | col  4 | v  0.1431 | L  3 | R  4 | y 0.5345 | leaf F
ID   2 | col  0 | v  0.3915 | L  5 | R  6 | y 0.2382 | leaf F
ID   3 | col  0 | v -0.6553 | L  7 | R  8 | y 0.6358 | leaf F
ID   4 | col -1 | v  0.0000 | L  9 | R 10 | y 0.4123 | leaf T
ID   5 | col  4 | v -0.2987 | L 11 | R 12 | y 0.3032 | leaf F
ID   6 | col  2 | v  0.3777 | L 13 | R 14 | y 0.1701 | leaf F
ID   7 | col -1 | v  0.0000 | L 15 | R 16 | y 0.6952 | leaf T
ID   8 | col -1 | v  0.0000 | L 17 | R 18 | y 0.5598 | leaf T
ID  11 | col -1 | v  0.0000 | L 23 | R 24 | y 0.4101 | leaf T
ID  12 | col -1 | v  0.0000 | L 25 | R 26 | y 0.2613 | leaf T
ID  13 | col -1 | v  0.0000 | L 27 | R 28 | y 0.1882 | leaf T
ID  14 | col -1 | v  0.0000 | L 29 | R 30 | y 0.1381 | leaf T

Evaluating tree model

Train acc (within 0.10) = 0.3750
Test acc (within 0.10) = 0.4750

Train MSE = 0.0048
Test MSE = 0.0054

Predicting for x =
-0.1660   0.4406  -0.9998  -0.3953  -0.7065
y = 0.4101

IF
column 0  >   -0.2102 AND
column 0  <=   0.3915 AND
column 4  <=  -0.2987 AND
THEN
predicted = 0.4101

End decision tree regression demo

If you compare this output with the visual representation, most of the ideas of decision tree regression will become mostly clear:

The demo decision tree has maxDepth = 3. This creates a tree with 15 nodes (some of which could be empty). In general, if a tree has maxDepth = n, then it has 2^(n+1) - 1 1 nodes. These tree nodes could be stored as JavaScript program-defined Node objects and connected via pointers/references. But the architecture used by the demo decision tree is to create a List collection with size/count = 15, where each item in the List is a Node object.

With this design, if the root node is at index [0], then the left child is at [1] and the right child is at [2]. In general, if a node is at index [i], then the left child is at index [2*i+1] and the right child is at index [2*i+2].

The tree splitting part of constructing a decision tree regression system is perhaps best understood by looking at a concrete example. The root node of the demo decision tree is associated with all 200 rows of the training data. The splitting process selects some of the 200 rows to be assigned to the left child node, and the remaining rows to be assigned to the right child node.

For simplicity, suppose that instead of the demo training data with 200 rows and 5 columns of predictors, a tree node is associated with just 5 rows of data, and the data has just 3 columns of predictors:

     X                    y
[0] 0.97  0.25  0.75     3.0
[1] 0.53  0.41  0.00     9.0
[2] 0.86  0.64  0.86     7.0
[3] 0.14  0.37  0.25     2.0
[4] 0.53  0.86  0.37     6.0
     [0]   [1]   [2]

The split algorithm will select some of the five rows to go to the left child and the remaining rows to go to the right child. The idea is to select the two sets of rows in a way so that their associated y values are close together. The demo implementation does this by finding the split that minimizes the weighted variance of the target y values.

The splitting algorithm examines every possible x value in every row and every column. For each possible candidate split value (also called the threshold), the weighted variance of the y values of the resulting split is computed. For example, for x = 0.37 in column [1], the rows where the values in column [1] are less than or equal to 0.37 are rows [3] and [0] with associated y values (2.0, 3.0). The other rows are [1], [2], [4] with associated y values (9.0, 7.0, 6.0).

The variance of a set of y values is the average of the sum of the squared differences between the values and their mean (average).

For this proposed split, the variance of y values (2.0, 3.0) is computed as 0.25. The mean of (2.0, 3.0) = (2.0 + 3.0) / 2 = 2.5 and so the variance is ((2.0 - 2.5)^2 + (3.0 - 2.5)^2) / 2 = 0.25.

The mean of y values (9.0, 7.0, 6.0) = (9.0 + 7.0 + 6.0) / 3 = 7.33 and the variance is ((9.0 - 7.33)^2 + (7.0 -7.33)^2 + (6.0 - 7.33)^2) / 3 = 2.33.

Because the proposed split has different numbers of rows (two rows for the left child and three rows for the right child), the weighted variance of the proposed split is used and is ((2 * 0.25) + (3 * 2.33)) / 5 = 1.50.

This process is repeated for every x value in the training data. The x threshold value and its column that generate the smallest weighted variance define the split. In practice it's common to keep track of which values in a given column have already been checked, to avoid unnecessary work computing weighted variance.

After a best split is found, the predicted y value for a leaf node (no further splits) is the average of the y values associated with the node. The demo program computes predicted y values for internal, non-leaf nodes, but those predicted values are not used.

The demo does not use recursion to build the tree. Instead, the demo uses a stack data structure. In high-level pseudo-code:

create empty stack
push (root, depth)
while stack not empty
  pop (currNode, currDepth)
  if at maxDepth or not enough data then
    node is a leaf, predicted = avg of associated Y values
  compute split value and split column using the
  associated rows stored in currNode
  if unable to split then
    node is a leaf, predicted = avg of associated Y values
  compute left-rows, right-rows
  create and push (leftNode, currDepth+1)
  create and push (rightNode, currDepth+1)   
end-while

The build-tree algorithm is short but very tricky. The stack holds a tree node and its associated rows of the training data, and the current depth of the tree. The current depth of the tree is maintained so that the algorithm knows when maxDepth has been reached.

My love of math, computer science, and machine learning can probably be traced back to the games I loved to play as a young man: poker, Yahtzee, blackjack, and many others.

Right: The card drawn was a 3, so the player has a total of 13. If you want to stand with that total, you pull the "House" lever to reveal the House hand. Here is it 20, so the player loses.

Demo code. Replace "lt" (less than), "gt", "lte", "gte" with Boolean operator symbols (my blog editor chokes on symbols).

// decision_tree_regression.js
// node.js v22.16.0

let FS = require('fs');  // file load

class DecisionTreeRegressor
{
  // --------------------------------------------------------

  constructor(maxDepth, minSamples,
    minLeaf, numSplitCols, seed)
  {
    // if maxDepth = n, list has 2^(n+1) - 1 nodes
    this.maxDepth = maxDepth;
    this.minSamples = minSamples;
    this.minLeaf = minLeaf;
    this.numSplitCols = numSplitCols; // for random forest

    // create full tree
    this.tree = [];  // a list of Node objects
    let numNodes = Math.pow(2, (maxDepth + 1)) - 1;
    for (let i = 0; i "lt" numNodes; ++i) {
      let n = new this.Node(i, -1, 0.0, -1,
        -1, 0.0, false, []);
      this.tree[i] = n; // dummy nodes
    }

    this.seed = seed + 0.5;  // quasi random
    this.trainX = null;  // supplied in train()
    this.trainY = null;  
  }

  // --------------------------------------------------------

    Node = function(id, colIdx, thresh, left, right, value,
      isLeaf, rows) // call:  n = new this.Node(0, . .);
    {
      this.id = id; this.colIdx = colIdx;
      this.thresh = thresh; this.left = left;
      this.right = right; this.value = value;
      this.isLeaf = isLeaf;
      this.rows = rows; // a list
    }

    StackInfo = function(node, depth)
    {
      this.node = node;
      this.depth = depth;
    }

  // --------------------------------------------------------

  // core methods: 
  // train(), predict(), explain(), accuracy(),
  //   mse(), display()

  // --------------------------------------------------------

  train(trainX, trainY)
  {
    this.trainX = trainX;  // by ref
    this.trainY = trainY;
    this.makeTree();
  }

  // --------------------------------------------------------

  predict(x)
  {
    let p = 0;
    let currNode = this.tree[p];
    while (currNode.isLeaf == false &&
    p "lt" this.tree.length) {
      if (x[currNode.colIdx] "lte" currNode.thresh)
        p = currNode.left;
      else
        p = currNode.right;
      currNode = this.tree[p];
    }
    return this.tree[p].value;
  }

  // --------------------------------------------------------

  explain(x)
  {
    let p = 0;
    console.log("\nIF ");
    let currNode = this.tree[p];
    while (currNode.isLeaf == false) {
      process.stdout.write("column ");
      process.stdout.write(currNode.colIdx + " ");
      if (x[currNode.colIdx] "lte" currNode.thresh) {
        process.stdout.write(" "lte" ");
        console.log(currNode.thresh.toFixed(4).
        toString().padStart(8) + " AND ");
        p = currNode.left;
        currNode = this.tree[p];
      }
      else {
        process.stdout.write(" "gt"  ");
        console.log(currNode.thresh.toFixed(4).
        toString().padStart(8) + " AND ");
        p = currNode.right;
        currNode = this.tree[p];
      }
    }
    console.log("THEN \npredicted = " +
      currNode.value.toFixed(4).toString());
  }

  // --------------------------------------------------------

  accuracy(dataX, dataY, pctClose)
  {
    let nCorrect = 0; let nWrong = 0;
    for (let i = 0; i "lt" dataX.length; ++i) {
      let x = dataX[i];
      let actualY = dataY[i];
      let predY = this.predict(x);
      if (Math.abs(predY - actualY) "lt" 
        Math.abs(pctClose * actualY)) {
        ++nCorrect;
      }
      else {
        ++nWrong;
      }
    }
    return (nCorrect * 1.0) / (nCorrect + nWrong);
  }

  // --------------------------------------------------------

  mse(dataX, dataY)
  {
    let n = dataX.length;
    let sum = 0.0;
    for (let i = 0; i "lt" n; ++i) {
      let x = dataX[i];
      let actualY = dataY[i];
      let predY = this.predict(x);
      sum += (actualY - predY) * (actualY - predY);
    }
    return sum / n;
  }

  // --------------------------------------------------------

  display(showRows)
  {
    let size = this.tree.length;
    for (let i = 0; i "lt" size; ++i) { // each node
      let n = this.tree[i]; // covenience
      if (n == null) continue;
      if (n.colIdx == -1 && n.isLeaf == false) continue;

      let s = "";
      s += "ID " + n.id.toString().padStart(3) + " ";
      s += "| col " + n.colIdx.toString().padStart(2) + " ";
      s += "| v " + n.thresh.toFixed(4).
        toString().padStart(8) + " ";
      s += "| L " + n.left.toString().padStart(2) + " ";
      s += "| R " + n.right.toString().padStart(2) + " ";
      s += "| y " + n.value.toFixed(4).toString() + " ";
      let tf = n.isLeaf == true ? "T" : "F";
      s += "| leaf " + tf;

      if (showRows == true) {
        s += "\nrows: ";
        for (let k = 0; k "lt" n.rows.length; ++k) {
          if (k "gt" 0 && k % 20 == 0)
              s += "\n";
          s += n.rows[k].toString() + " ";
        }
      }
      console.log(s);
      if (showRows == true) console.log("");
    }
  } // display()

  // --------------------------------------------------------

  // helpers for train(): makeTree(), bestSplit(), next(),
  //   nextInt(), shuffle(), treeTargetMean(),
  //   treeTargetVariance()

  // --------------------------------------------------------

  makeTree()
  {
    if (this.numSplitCols == -1)
      this.numSplitCols = this.trainX[0].length;

    let allRows = [];
    for (let i = 0; i "lt" this.trainX.length; ++i)
      allRows.push(i);
    let grandMean = this.treeTargetMean(allRows);

    let root = new this.Node(0, -1, 0.0, 1, 2,
        grandMean, false, allRows);
      
    let stack = [];  // first-in, first-out
    stack.push(new this.StackInfo(root, 0));
    while (stack.length "gt" 0) {
      let info = stack.pop();
      let currNode = info.node;
      this.tree[currNode.id] = currNode;

      let currRows = info.node.rows;
      let currDepth = info.depth;

      if (currDepth == this.maxDepth ||
        currRows.length "lt" this.minSamples) {
        currNode.value = this.treeTargetMean(currRows);
        currNode.isLeaf = true;
        continue;
      }

      let splitInfo = this.bestSplit(currRows);
      let colIdx = Math.trunc(splitInfo[0]);
      let thresh = splitInfo[1];

      if (colIdx == -1) {  // unable to split
        currNode.value = this.treeTargetMean(currRows);
        currNode.isLeaf = true;
        continue;
      }

      // good split so at internal, non-leaf node
      currNode.colIdx = colIdx;
      currNode.thresh = thresh;

      // make the data splits for children
      // find left rows and right rows
      let leftIdxs = [];
      let rightIdxs = [];

      for (let k = 0; k "lt" currRows.length; ++k) {
        let r = currRows[k];
        if (this.trainX[r][colIdx] "lte" thresh)
          leftIdxs.push(r);
        else
          rightIdxs.push(r);
      }

      let leftID = currNode.id * 2 + 1;
      let currNodeLeft = new this.Node(leftID, -1, 0.0,
        2 * leftID + 1, 2 * leftID + 2,
        this.treeTargetMean(leftIdxs), false, leftIdxs);
      stack.push(new this.StackInfo(currNodeLeft,
        currDepth + 1));

      let rightID = currNode.id * 2 + 2;
      let currNodeRight = new this.Node(rightID, -1, 0.0,
        2*rightID + 1, 2 * rightID + 2,
        this.treeTargetMean(rightIdxs), false, rightIdxs);
      stack.push(new this.StackInfo(currNodeRight,
        currDepth + 1));

    } // while
  } // makeTree()

  // --------------------------------------------------------

  bestSplit(rows)
  {
    // result[0] = best col idx (as double)
    // result[1] = best split value

    let bestColIdx = -1;  // indicates bad split
    let bestThresh = 0.0;
    let bestVar = Number.MAX_VALUE;  // smaller is better

    let nRows = rows.length;
    let nCols = this.trainX[0].length;

    if (nRows == 0)
      console.log("FATAL: empty data in bestSplit()");

    // process cols in scrambled order
    let colIndices = [];
    for (let k = 0; k "lt" nCols; ++k)
      colIndices[k] = k;
    this.shuffle(colIndices);

    // each column of trainX
    for (let j = 0; j "lt" this.numSplitCols; ++j) {
      let colIdx = colIndices[j];
      let examineds = [];

      for (let i = 0; i "lt" nRows; ++i) {  // each row
        // if curr thresh been seen, skip it
        let thresh = this.trainX[rows[i]][colIdx];
        if (examineds.includes(thresh)) continue;
        examineds.push(thresh);

        // get row idxs where x is lte, gt thresh
        let leftIdxs = [];
        let rightIdxs = [];
        for (let k = 0; k "lt" nRows; ++k) {
          if (this.trainX[rows[k]][colIdx] "lte" thresh)
            leftIdxs.push(rows[k]);
          else
            rightIdxs.push(rows[k]);
        }

        // Check if proposed split has too few values
        if (leftIdxs.length "lt" this.minLeaf || 
        rightIdxs.length "lt" this.minLeaf) 
          continue;  // to next row

        let leftVar = this.treeTargetVariance(leftIdxs);
        let rightVar = this.treeTargetVariance(rightIdxs);
        let weightedVar = (leftIdxs.length * leftVar +
          rightIdxs.length * rightVar) / nRows;

        if (weightedVar "lt" bestVar) {
          bestColIdx = colIdx;
          bestThresh = thresh;
          bestVar = weightedVar;
        }
      } // each row
    } // j each col

    let result = [-1, -1];
    result[0] = bestColIdx;
    result[1] = bestThresh;
    return result;
  } // bestSplit()

  // --------------------------------------------------------

  next()
  {
    // return sort-of-random in [0.0, 1.0)
    let x = Math.sin(this.seed) * 1000;
    let result = x - Math.floor(x);  // [0.0,1.0)
    this.seed = result;  // for next call
    return result;
  }

  // --------------------------------------------------------

  nextInt(lo, hi)
  {
    let x = this.next();
    return Math.trunc((hi - lo) * x + lo);
  }

  // --------------------------------------------------------

  shuffle(indices)
  {
    // Fisher-Yates
    for (let i = 0; i "lt" indices.length; ++i) {
      let ri = this.nextInt(i, indices.length);
      let tmp = indices[ri];
      indices[ri] = indices[i];
      indices[i] = tmp;
    }
  }

  // -------------------------------------------------------- 

  treeTargetMean(rows)
  {
    let sum = 0.0;
    for (let i = 0; i "lt" rows.length; ++i) {
      let r = rows[i];
      sum += this.trainY[r];
    }
    return sum / rows.length;
  }

  // ------------------------------------------------------

  treeTargetVariance(rows)
  {
    let mean = this.treeTargetMean(rows);
    let sum = 0.0;
    for (let i = 0; i "lt" rows.length; ++i) {
      let r = rows[i];
      sum += (this.trainY[r] - mean) *
        (this.trainY[r] - mean);
    }
    return sum / rows.length;
  }

} // class DecisionTreeRegressor

// ----------------------------------------------------------
// helper functions for main(): loadTxt(), vecShow()
// ----------------------------------------------------------

function loadTxt(fn, delimit, usecols, comment) {
  // load numeric matrix from text file
  let all = FS.readFileSync(fn, "utf8");  // giant string
  all = all.trim();  // strip final crlf in file
  let lines = all.split("\n");  // array of lines

  // count number non-comment lines
  let nRows = 0;
  for (let i = 0; i "lt" lines.length; ++i) {
    if (!lines[i].startsWith(comment))
      ++nRows;
  }
  nCols = usecols.length;
  //let result = matMake(nRows, nCols, 0.0);
  let result = [];
  for (let i = 0; i "lt" nRows; ++i) {
    result[i] = [];
    for (let j = 0; j "lt" nCols; ++j) {
      result[i][j] = 0.0;
    }
  }
 
  let r = 0;  // into lines
  let i = 0;  // into result[][]
  while (r "lt" lines.length) {
    if (lines[r].startsWith(comment)) {
      ++r;  // next row
    }
    else {
      let tokens = lines[r].split(delimit);
      for (let j = 0; j "lt" nCols; ++j) {
        result[i][j] = parseFloat(tokens[usecols[j]]);
      }
      ++r;
      ++i;
    }
  }

  if (usecols.length "gt" 1)
    return result;

  // if length of usecols is just 1, convert matrix to vector
  // the curr matrix is shape nRows x 1
  if (usecols.length == 1) {
    let vec = [];
    for (let i = 0; i "lt" nRows; ++i)
      vec[i] = result[i][0];
    return vec;
  }
}

// ----------------------------------------------------------

function vecShow(v, dec, len)
{
  for (let i = 0; i "lt" v.length; ++i) {
    if (i != 0 && i % len == 0) {
      process.stdout.write("\n");
    }
    if (v[i] "gte" 0.0) {
      process.stdout.write(" ");  // + or - space
    }
    process.stdout.write(v[i].toFixed(dec));
    process.stdout.write("  ");
  }
  process.stdout.write("\n");
}

// ----------------------------------------------------------

function main()
{
  console.log("\nJavaScript decision tree regression ");

  // 1. load data
  console.log("\nLoading synthetic train (200), test (40)");
  let trainFile = ".\\Data\\synthetic_train_200.txt";
  let testFile = ".\\Data\\synthetic_test_40.txt";

  let trainX = loadTxt(trainFile, ",", [0,1,2,3,4], "#");
  let trainY = loadTxt(trainFile, ",", [5], "#");
  let testX = loadTxt(testFile, ",", [0,1,2,3,4], "#");
  let testY = loadTxt(testFile, ",", [5], "#");
  console.log("Done ");

  console.log("\nFirst three train x: ");
  for (let i = 0; i "lt" 3; ++i)
    vecShow(trainX[i], 4, 8);  // 4 decimals 8 wide
  console.log("\nFirst three train y: ");
  for (let i = 0; i "lt" 3; ++i)
    process.stdout.write(trainY[i].toString() + " ");
  console.log("");

  // 2. create and train tree
  let maxDepth = 3;
  let minSamples = 2;
  let minLeaf = 18;  // 18
  let numSplitCols = -1;  // all columns
  let seed = 0;
  console.log("\nSetting maxDepth = " +
    maxDepth.toString());
  console.log("Setting minSamples = " +
    minSamples.toString());
  console.log("Setting minLeaf = " +
    minLeaf.toString());
  console.log("Using default numSplitCols = -1 ");

  console.log("\nCreating and training tree ");
  let dtr = 
    new DecisionTreeRegressor(maxDepth, minSamples,
      minLeaf, numSplitCols, seed);

  dtr.train(trainX, trainY);
  console.log("Done \n");
  dtr.display(false); // show rows

  // 3. evaluate tree
  console.log("\nEvaluating tree model ");
  let trainAcc = dtr.accuracy(trainX, trainY, 0.10);
  let testAcc = dtr.accuracy(testX, testY, 0.10);
  console.log("\nTrain acc (within 0.10) = " +
    trainAcc.toFixed(4).toString());
  console.log("Test acc (within 0.10) = " +
    testAcc.toFixed(4).toString());

  let trainMSE = dtr.mse(trainX, trainY);
  let testMSE = dtr.mse(testX, testY);
  console.log("\nTrain MSE = " +
    trainMSE.toFixed(4).toString());
  console.log("Test MSE = " +
    testMSE.toFixed(4).toString());

  // 4. use tree to make prediction
  let x = trainX[0];
  console.log("\nPredicting for x = ");
  vecShow(x, 4, 9);
  let predY = dtr.predict(x);
  console.log("y = " + predY.toFixed(4).toString());

  dtr.explain(x);

  console.log("\nEnd decision tree regression demo ");
}

main();

Training data:

# synthetic_train_200.txt
#
-0.1660,  0.4406, -0.9998, -0.3953, -0.7065,  0.4840
 0.0776, -0.1616,  0.3704, -0.5911,  0.7562,  0.1568
-0.9452,  0.3409, -0.1654,  0.1174, -0.7192,  0.8054
 0.9365, -0.3732,  0.3846,  0.7528,  0.7892,  0.1345
-0.8299, -0.9219, -0.6603,  0.7563, -0.8033,  0.7955
 0.0663,  0.3838, -0.3690,  0.3730,  0.6693,  0.3206
-0.9634,  0.5003,  0.9777,  0.4963, -0.4391,  0.7377
-0.1042,  0.8172, -0.4128, -0.4244, -0.7399,  0.4801
-0.9613,  0.3577, -0.5767, -0.4689, -0.0169,  0.6861
-0.7065,  0.1786,  0.3995, -0.7953, -0.1719,  0.5569
 0.3888, -0.1716, -0.9001,  0.0718,  0.3276,  0.2500
 0.1731,  0.8068, -0.7251, -0.7214,  0.6148,  0.3297
-0.2046, -0.6693,  0.8550, -0.3045,  0.5016,  0.2129
 0.2473,  0.5019, -0.3022, -0.4601,  0.7918,  0.2613
-0.1438,  0.9297,  0.3269,  0.2434, -0.7705,  0.5171
 0.1568, -0.1837, -0.5259,  0.8068,  0.1474,  0.3307
-0.9943,  0.2343, -0.3467,  0.0541,  0.7719,  0.5581
 0.2467, -0.9684,  0.8589,  0.3818,  0.9946,  0.1092
-0.6553, -0.7257,  0.8652,  0.3936, -0.8680,  0.7018
 0.8460,  0.4230, -0.7515, -0.9602, -0.9476,  0.1996
-0.9434, -0.5076,  0.7201,  0.0777,  0.1056,  0.5664
 0.9392,  0.1221, -0.9627,  0.6013, -0.5341,  0.1533
 0.6142, -0.2243,  0.7271,  0.4942,  0.1125,  0.1661
 0.4260,  0.1194, -0.9749, -0.8561,  0.9346,  0.2230
 0.1362, -0.5934, -0.4953,  0.4877, -0.6091,  0.3810
 0.6937, -0.5203, -0.0125,  0.2399,  0.6580,  0.1460
-0.6864, -0.9628, -0.8600, -0.0273,  0.2127,  0.5387
 0.9772,  0.1595, -0.2397,  0.1019,  0.4907,  0.1611
 0.3385, -0.4702, -0.8673, -0.2598,  0.2594,  0.2270
-0.8669, -0.4794,  0.6095, -0.6131,  0.2789,  0.4700
 0.0493,  0.8496, -0.4734, -0.8681,  0.4701,  0.3516
 0.8639, -0.9721, -0.5313,  0.2336,  0.8980,  0.1412
 0.9004,  0.1133,  0.8312,  0.2831, -0.2200,  0.1782
 0.0991,  0.8524,  0.8375, -0.2102,  0.9265,  0.2150
-0.6521, -0.7473, -0.7298,  0.0113, -0.9570,  0.7422
 0.6190, -0.3105,  0.8802,  0.1640,  0.7577,  0.1056
 0.6895,  0.8108, -0.0802,  0.0927,  0.5972,  0.2214
 0.1982, -0.9689,  0.1870, -0.1326,  0.6147,  0.1310
-0.3695,  0.7858,  0.1557, -0.6320,  0.5759,  0.3773
-0.1596,  0.3581,  0.8372, -0.9992,  0.9535,  0.2071
-0.2468,  0.9476,  0.2094,  0.6577,  0.1494,  0.4132
 0.1737,  0.5000,  0.7166,  0.5102,  0.3961,  0.2611
 0.7290, -0.3546,  0.3416, -0.0983, -0.2358,  0.1332
-0.3652,  0.2438, -0.1395,  0.9476,  0.3556,  0.4170
-0.6029, -0.1466, -0.3133,  0.5953,  0.7600,  0.4334
-0.4596, -0.4953,  0.7098,  0.0554,  0.6043,  0.2775
 0.1450,  0.4663,  0.0380,  0.5418,  0.1377,  0.2931
-0.8636, -0.2442, -0.8407,  0.9656, -0.6368,  0.7429
 0.6237,  0.7499,  0.3768,  0.1390, -0.6781,  0.2185
-0.5499,  0.1850, -0.3755,  0.8326,  0.8193,  0.4399
-0.4858, -0.7782, -0.6141, -0.0008,  0.4572,  0.4197
 0.7033, -0.1683,  0.2334, -0.5327, -0.7961,  0.1776
 0.0317, -0.0457, -0.6947,  0.2436,  0.0880,  0.3345
 0.5031, -0.5559,  0.0387,  0.5706, -0.9553,  0.3107
-0.3513,  0.7458,  0.6894,  0.0769,  0.7332,  0.3170
 0.2205,  0.5992, -0.9309,  0.5405,  0.4635,  0.3532
-0.4806, -0.4859,  0.2646, -0.3094,  0.5932,  0.3202
 0.9809, -0.3995, -0.7140,  0.8026,  0.0831,  0.1600
 0.9495,  0.2732,  0.9878,  0.0921,  0.0529,  0.1289
-0.9476, -0.6792,  0.4913, -0.9392, -0.2669,  0.5966
 0.7247,  0.3854,  0.3819, -0.6227, -0.1162,  0.1550
-0.5922, -0.5045, -0.4757,  0.5003, -0.0860,  0.5863
-0.8861,  0.0170, -0.5761,  0.5972, -0.4053,  0.7301
 0.6877, -0.2380,  0.4997,  0.0223,  0.0819,  0.1404
 0.9189,  0.6079, -0.9354,  0.4188, -0.0700,  0.1907
-0.1428, -0.7820,  0.2676,  0.6059,  0.3936,  0.2790
 0.5324, -0.3151,  0.6917, -0.1425,  0.6480,  0.1071
-0.8432, -0.9633, -0.8666, -0.0828, -0.7733,  0.7784
-0.9444,  0.5097, -0.2103,  0.4939, -0.0952,  0.6787
-0.0520,  0.6063, -0.1952,  0.8094, -0.9259,  0.4836
 0.5477, -0.7487,  0.2370, -0.9793,  0.0773,  0.1241
 0.2450,  0.8116,  0.9799,  0.4222,  0.4636,  0.2355
 0.8186, -0.1983, -0.5003, -0.6531, -0.7611,  0.1511
-0.4714,  0.6382, -0.3788,  0.9648, -0.4667,  0.5950
 0.0673, -0.3711,  0.8215, -0.2669, -0.1328,  0.2677
-0.9381,  0.4338,  0.7820, -0.9454,  0.0441,  0.5518
-0.3480,  0.7190,  0.1170,  0.3805, -0.0943,  0.4724
-0.9813,  0.1535, -0.3771,  0.0345,  0.8328,  0.5438
-0.1471, -0.5052, -0.2574,  0.8637,  0.8737,  0.3042
-0.5454, -0.3712, -0.6505,  0.2142, -0.1728,  0.5783
 0.6327, -0.6297,  0.4038, -0.5193,  0.1484,  0.1153
-0.5424,  0.3282, -0.0055,  0.0380, -0.6506,  0.6613
 0.1414,  0.9935,  0.6337,  0.1887,  0.9520,  0.2540
-0.9351, -0.8128, -0.8693, -0.0965, -0.2491,  0.7353
 0.9507, -0.6640,  0.9456,  0.5349,  0.6485,  0.1059
-0.0462, -0.9737, -0.2940, -0.0159,  0.4602,  0.2606
-0.0627, -0.0852, -0.7247, -0.9782,  0.5166,  0.2977
 0.0478,  0.5098, -0.0723, -0.7504, -0.3750,  0.3335
 0.0090,  0.3477,  0.5403, -0.7393, -0.9542,  0.4415
-0.9748,  0.3449,  0.3736, -0.1015,  0.8296,  0.4358
 0.2887, -0.9895, -0.0311,  0.7186,  0.6608,  0.2057
 0.1570, -0.4518,  0.1211,  0.3435, -0.2951,  0.3244
 0.7117, -0.6099,  0.4946, -0.4208,  0.5476,  0.1096
-0.2929, -0.5726,  0.5346, -0.3827,  0.4665,  0.2465
 0.4889, -0.5572, -0.5718, -0.6021, -0.7150,  0.2163
-0.7782,  0.3491,  0.5996, -0.8389, -0.5366,  0.6516
-0.5847,  0.8347,  0.4226,  0.1078, -0.3910,  0.6134
 0.8469,  0.4121, -0.0439, -0.7476,  0.9521,  0.1571
-0.6803, -0.5948, -0.1376, -0.1916, -0.7065,  0.7156
 0.2878,  0.5086, -0.5785,  0.2019,  0.4979,  0.2980
 0.2764,  0.1943, -0.4090,  0.4632,  0.8906,  0.2960
-0.8877,  0.6705, -0.6155, -0.2098, -0.3998,  0.7107
-0.8398,  0.8093, -0.2597,  0.0614, -0.0118,  0.6502
-0.8476,  0.0158, -0.4769, -0.2859, -0.7839,  0.7715
 0.5751, -0.7868,  0.9714, -0.6457,  0.1448,  0.1175
 0.4802, -0.7001,  0.1022, -0.5668,  0.5184,  0.1090
 0.4458, -0.6469,  0.7239, -0.9604,  0.7205,  0.0779
 0.5175,  0.4339,  0.9747, -0.4438, -0.9924,  0.2879
 0.8678,  0.7158,  0.4577,  0.0334,  0.4139,  0.1678
 0.5406,  0.5012,  0.2264, -0.1963,  0.3946,  0.2088
-0.9938,  0.5498,  0.7928, -0.5214, -0.7585,  0.7687
 0.7661,  0.0863, -0.4266, -0.7233, -0.4197,  0.1466
 0.2277, -0.3517, -0.0853, -0.1118,  0.6563,  0.1767
 0.3499, -0.5570, -0.0655, -0.3705,  0.2537,  0.1632
 0.7547, -0.1046,  0.5689, -0.0861,  0.3125,  0.1257
 0.8186,  0.2110,  0.5335,  0.0094, -0.0039,  0.1391
 0.6858, -0.8644,  0.1465,  0.8855,  0.0357,  0.1845
-0.4967,  0.4015,  0.0805,  0.8977,  0.2487,  0.4663
 0.6760, -0.9841,  0.9787, -0.8446, -0.3557,  0.1509
-0.1203, -0.4885,  0.6054, -0.0443, -0.7313,  0.4854
 0.8557,  0.7919, -0.0169,  0.7134, -0.1628,  0.2002
 0.0115, -0.6209,  0.9300, -0.4116, -0.7931,  0.4052
-0.7114, -0.9718,  0.4319,  0.1290,  0.5892,  0.3661
 0.3915,  0.5557, -0.1870,  0.2955, -0.6404,  0.2954
-0.3564, -0.6548, -0.1827, -0.5172, -0.1862,  0.4622
 0.2392, -0.4959,  0.5857, -0.1341, -0.2850,  0.2470
-0.3394,  0.3947, -0.4627,  0.6166, -0.4094,  0.5325
 0.7107,  0.7768, -0.6312,  0.1707,  0.7964,  0.2757
-0.1078,  0.8437, -0.4420,  0.2177,  0.3649,  0.4028
-0.3139,  0.5595, -0.6505, -0.3161, -0.7108,  0.5546
 0.4335,  0.3986,  0.3770, -0.4932,  0.3847,  0.1810
-0.2562, -0.2894, -0.8847,  0.2633,  0.4146,  0.4036
 0.2272,  0.2966, -0.6601, -0.7011,  0.0284,  0.2778
-0.0743, -0.1421, -0.0054, -0.6770, -0.3151,  0.3597
-0.4762,  0.6891,  0.6007, -0.1467,  0.2140,  0.4266
-0.4061,  0.7193,  0.3432,  0.2669, -0.7505,  0.6147
-0.0588,  0.9731,  0.8966,  0.2902, -0.6966,  0.4955
-0.0627, -0.1439,  0.1985,  0.6999,  0.5022,  0.3077
 0.1587,  0.8494, -0.8705,  0.9827, -0.8940,  0.4263
-0.7850,  0.2473, -0.9040, -0.4308, -0.8779,  0.7199
 0.4070,  0.3369, -0.2428, -0.6236,  0.4940,  0.2215
-0.0242,  0.0513, -0.9430,  0.2885, -0.2987,  0.3947
-0.5416, -0.1322, -0.2351, -0.0604,  0.9590,  0.3683
 0.1055,  0.7783, -0.2901, -0.5090,  0.8220,  0.2984
-0.9129,  0.9015,  0.1128, -0.2473,  0.9901,  0.4776
-0.9378,  0.1424, -0.6391,  0.2619,  0.9618,  0.5368
 0.7498, -0.0963,  0.4169,  0.5549, -0.0103,  0.1614
-0.2612, -0.7156,  0.4538, -0.0460, -0.1022,  0.3717
 0.7720,  0.0552, -0.1818, -0.4622, -0.8560,  0.1685
-0.4177,  0.0070,  0.9319, -0.7812,  0.3461,  0.3052
-0.0001,  0.5542, -0.7128, -0.8336, -0.2016,  0.3803
 0.5356, -0.4194, -0.5662, -0.9666, -0.2027,  0.1776
-0.2378,  0.3187, -0.8582, -0.6948, -0.9668,  0.5474
-0.1947, -0.3579,  0.1158,  0.9869,  0.6690,  0.2992
 0.3992,  0.8365, -0.9205, -0.8593, -0.0520,  0.3154
-0.0209,  0.0793,  0.7905, -0.1067,  0.7541,  0.1864
-0.4928, -0.4524, -0.3433,  0.0951, -0.5597,  0.6261
-0.8118,  0.7404, -0.5263, -0.2280,  0.1431,  0.6349
 0.0516, -0.8480,  0.7483,  0.9023,  0.6250,  0.1959
-0.3212,  0.1093,  0.9488, -0.3766,  0.3376,  0.2735
-0.3481,  0.5490, -0.3484,  0.7797,  0.5034,  0.4379
-0.5785, -0.9170, -0.3563, -0.9258,  0.3877,  0.4121
 0.3407, -0.1391,  0.5356,  0.0720, -0.9203,  0.3458
-0.3287, -0.8954,  0.2102,  0.0241,  0.2349,  0.3247
-0.1353,  0.6954, -0.0919, -0.9692,  0.7461,  0.3338
 0.9036, -0.8982, -0.5299, -0.8733, -0.1567,  0.1187
 0.7277, -0.8368, -0.0538, -0.7489,  0.5458,  0.0830
 0.9049,  0.8878,  0.2279,  0.9470, -0.3103,  0.2194
 0.7957, -0.1308, -0.5284,  0.8817,  0.3684,  0.2172
 0.4647, -0.4931,  0.2010,  0.6292, -0.8918,  0.3371
-0.7390,  0.6849,  0.2367,  0.0626, -0.5034,  0.7039
-0.1567, -0.8711,  0.7940, -0.5932,  0.6525,  0.1710
 0.7635, -0.0265,  0.1969,  0.0545,  0.2496,  0.1445
 0.7675,  0.1354, -0.7698, -0.5460,  0.1920,  0.1728
-0.5211, -0.7372, -0.6763,  0.6897,  0.2044,  0.5217
 0.1913,  0.1980,  0.2314, -0.8816,  0.5006,  0.1998
 0.8964,  0.0694, -0.6149,  0.5059, -0.9854,  0.1825
 0.1767,  0.7104,  0.2093,  0.6452,  0.7590,  0.2832
-0.3580, -0.7541,  0.4426, -0.1193, -0.7465,  0.5657
-0.5996,  0.5766, -0.9758, -0.3933, -0.9572,  0.6800
 0.9950,  0.1641, -0.4132,  0.8579,  0.0142,  0.2003
-0.4717, -0.3894, -0.2567, -0.5111,  0.1691,  0.4266
 0.3917, -0.8561,  0.9422,  0.5061,  0.6123,  0.1212
-0.0366, -0.1087,  0.3449, -0.1025,  0.4086,  0.2475
 0.3633,  0.3943,  0.2372, -0.6980,  0.5216,  0.1925
-0.5325, -0.6466, -0.2178, -0.3589,  0.6310,  0.3568
 0.2271,  0.5200, -0.1447, -0.8011, -0.7699,  0.3128
 0.6415,  0.1993,  0.3777, -0.0178, -0.8237,  0.2181
-0.5298, -0.0768, -0.6028, -0.9490,  0.4588,  0.4356
 0.6870, -0.1431,  0.7294,  0.3141,  0.1621,  0.1632
-0.5985,  0.0591,  0.7889, -0.3900,  0.7419,  0.2945
 0.3661,  0.7984, -0.8486,  0.7572, -0.6183,  0.3449
 0.6995,  0.3342, -0.3113, -0.6972,  0.2707,  0.1712
 0.2565,  0.9126,  0.1798, -0.6043, -0.1413,  0.2893
-0.3265,  0.9839, -0.2395,  0.9854,  0.0376,  0.4770
 0.2690, -0.1722,  0.9818,  0.8599, -0.7015,  0.3954
-0.2102, -0.0768,  0.1219,  0.5607, -0.0256,  0.3949
 0.8216, -0.9555,  0.6422, -0.6231,  0.3715,  0.0801
-0.2896,  0.9484, -0.7545, -0.6249,  0.7789,  0.4370
-0.9985, -0.5448, -0.7092, -0.5931,  0.7926,  0.5402

Test data:

# synthetic_test_40.txt
#
 0.7462,  0.4006, -0.0590,  0.6543, -0.0083,  0.1935
 0.8495, -0.2260, -0.0142, -0.4911,  0.7699,  0.1078
-0.2335, -0.4049,  0.4352, -0.6183, -0.7636,  0.5088
 0.1810, -0.5142,  0.2465,  0.2767, -0.3449,  0.3136
-0.8650,  0.7611, -0.0801,  0.5277, -0.4922,  0.7140
-0.2358, -0.7466, -0.5115, -0.8413, -0.3943,  0.4533
 0.4834,  0.2300,  0.3448, -0.9832,  0.3568,  0.1360
-0.6502, -0.6300,  0.6885,  0.9652,  0.8275,  0.3046
-0.3053,  0.5604,  0.0929,  0.6329, -0.0325,  0.4756
-0.7995,  0.0740, -0.2680,  0.2086,  0.9176,  0.4565
-0.2144, -0.2141,  0.5813,  0.2902, -0.2122,  0.4119
-0.7278, -0.0987, -0.3312, -0.5641,  0.8515,  0.4438
 0.3793,  0.1976,  0.4933,  0.0839,  0.4011,  0.1905
-0.8568,  0.9573, -0.5272,  0.3212, -0.8207,  0.7415
-0.5785,  0.0056, -0.7901, -0.2223,  0.0760,  0.5551
 0.0735, -0.2188,  0.3925,  0.3570,  0.3746,  0.2191
 0.1230, -0.2838,  0.2262,  0.8715,  0.1938,  0.2878
 0.4792, -0.9248,  0.5295,  0.0366, -0.9894,  0.3149
-0.4456,  0.0697,  0.5359, -0.8938,  0.0981,  0.3879
 0.8629, -0.8505, -0.4464,  0.8385,  0.5300,  0.1769
 0.1995,  0.6659,  0.7921,  0.9454,  0.9970,  0.2330
-0.0249, -0.3066, -0.2927, -0.4923,  0.8220,  0.2437
 0.4513, -0.9481, -0.0770, -0.4374, -0.9421,  0.2879
-0.3405,  0.5931, -0.3507, -0.3842,  0.8562,  0.3987
 0.9538,  0.0471,  0.9039,  0.7760,  0.0361,  0.1706
-0.0887,  0.2104,  0.9808,  0.5478, -0.3314,  0.4128
-0.8220, -0.6302,  0.0537, -0.1658,  0.6013,  0.4306
-0.4123, -0.2880,  0.9074, -0.0461, -0.4435,  0.5144
 0.0060,  0.2867, -0.7775,  0.5161,  0.7039,  0.3599
-0.7968, -0.5484,  0.9426, -0.4308,  0.8148,  0.2979
 0.7811,  0.8450, -0.6877,  0.7594,  0.2640,  0.2362
-0.6802, -0.1113, -0.8325, -0.6694, -0.6056,  0.6544
 0.3821,  0.1476,  0.7466, -0.5107,  0.2592,  0.1648
 0.7265,  0.9683, -0.9803, -0.4943, -0.5523,  0.2454
-0.9049, -0.9797, -0.0196, -0.9090, -0.4433,  0.6447
-0.4607,  0.1811, -0.2389,  0.4050, -0.0078,  0.5229
 0.2664, -0.2932, -0.4259, -0.7336,  0.8742,  0.1834
-0.4507,  0.1029, -0.6294, -0.1158, -0.6294,  0.6081
 0.8948, -0.0124,  0.9278,  0.2899, -0.0314,  0.1534
-0.1323, -0.8813, -0.0146, -0.0697,  0.6135,  0.2386