Matrix encoding growth

July 12, 2008

Limitation on computer integer representation put a limit on the size of a tree that Nested intervals/Matrix method can accommodate. For example it is reasonable to ask if the method would be able to deal with a tree with 200 levels with 2000 children at each node. It is easy to see that it can’t. Each node corresponds to some unique 2×2 matrix. Assuming 64 bit integers these matrices can’t possibly represent more than (2^64)^4 nodes. This value is significantly less than 2000^200. On the other hand, no practical tree can possibly have 2000 children at each node. Therefore,for making any realistic size estimation it is important to know the shape of the tree.

Here is an interesting finding related to the tree size estimation. Let scope problem to less ambitious goal of watching the encoding growth of the sequence of the nodes: 1, 1.1, 1.1.1, 1.1.1.1,… It is easy to see that for atomic matrices of the kind

```[n 1] [1 0] ```
we just have to look into matrix powers

```[1 1] [1 0] ```
```[1 1][1 1] [1 0][1 0] ```
```[1 1][1 1][1 1] [1 0][1 0][1 0]```

which have elements growing as a Fibonacci sequence. This sequence grows as fast as powers of golden ratio or approximately 1.6. This is one of the features that make Matrix/Farey encoding more attractive than dyadic fractions (which grew as powers of 2 at each level, and moving to the older siblings).

Given that matrix encoding of the various kind have so many in common, I assumed that the growth rate of power 1.6 applies universally. It was surprising to see this is not the case! Consider powers of

```[2 -1] [1 0] ```
(this is the encoding studied in “SQL design patterns” book). They grow linearly! Fairly quickly (at level 6) we have:
``` [1 1]^6 [13 8] [1 0] = [8 5] ```
compared to
``` [2 -1]^6 [7 -6] [1 0] = [6 -5] ```

2 Responses to “Matrix encoding growth”

1. Yuriy Fuksenko Says:

If we use 64 bit integers, only a11 and a21 are unique, that gives us (2^64)^2. Because we have to use multiplication, in becames just 2^64. Sign takes away 1 bit, so it is 2^63.
Now, if you look at node selected as root in the book,(a11=2;a21=1;a12=1;a22=0); you will see that it only covers interval from 1 to 2, and that will give you a very small subset of 2^63 posibilities.
If instead you create a root that covers everything from 0 to infinity, it will look like a11=1;a21=0;a12=1;a22=-1;
First level children than will look like (a11=n;a12=1;a21=1;a22=0),where n > 0. That makes the root described in the book just one of the children. Each child covers an interval of 1, with boundaries n-1,n.
now, what I am worried about, is that it seems like for each next sibling you can have smaller amount of children.
for example, if you take the last possible first level child [N,1,1,0], where N is Max possible number, you will not be able to add children to it.

2. Yuriy Fuksenko Says:

So, the biggest limitation at this point from my point of view is that as you going down the hierarchy and/or to the right through siblings, you can have less and less children.
Here is an example:
If you have a tree such that root has 2 children, and then second child has 3 children, and that 3rd child has 4 children, and 4th child has 5 children, and so on bottom right child on level 20 will not be able to get any children.