Back to Sinusoid.ca
The Combits Fractal Pattern (short for "Fractal Combinatory Bitset Pattern") is the pattern that can be seen in a binary number (bitset) when observing its number of bits set to one. This pattern (probably) falls within the science of Combinatoric Mathematics, but the name is my own (I couldn't find a name for it after searching for hours).
Further examination of the pattern leads to an interesting relationship between the bitcount of binary numbers and the values of the Pascal Triangle and also the position of the bits can help build all combinations of vertices for the various faces of a simplex.
Some highly related information can be found here: More Variations on a Fibonacci Theme1
| ||||
The Combits pattern is established by analysing an unsigned integer's bitset representation. The first interesting property that we can find, is the number of bits that are set to 1 versus the number set to 0 (this number is called the "nBits" in my examples below). As you can see in the example below, the pattern of "nBits" is simple and repetitive.
The basic pattern is (0, 1, 1, 2). This pattern repeats and If you examine these small pattern blocks, you will notice that the blocks following the first one are themselves arranged in the same kind of pattern.
The first block pattern is (1223, 2334, 2334, 3445). This shows that the pattern is a fractal pattern that "grows in magnitude" at each iterations (first iteration is 4 long (0112), second iteration is 4x4 long (1223, 2334, 2334, 3445) and the third iteration is 4x4x4 long, and so on).
|
1 1 |
|
1 1 |
You will notice that the pattern is not symmetric but the lower half of the pattern can be produced by the 180 degree rotation of the higher half (and vice-versa). This rotation explains the symmetry of the relationship to Pascal's Triangle (below).
The triangle on the left is the tip of Pascal's Triangle. The relationship can be seen as the count of numbers that have C bits set to 1 for a bitset of length R. This count is the value standing in column C and row R of the Pascal Triangle.
For example, a bitset of length 5 has numbers between 0 and 31 inclusively. There is 1 possibility with all bits set to zero. There are 5 numbers with exactly 1 bit set, there are 10 numbers with exactly 2 bits set (and 3 set to zero), there are 10 numbers with exactly 3 bits set (and 2 set to zero) and there are 5 numbers with exactly 4 bits set. In Pascal's Triangle on row 5, the 3rd number is 10 (columns start at zero like rows), therefore there are 10 possible combinations of 3 bits set to 1 in a 5 bit number.
This little research of mine started when I wanted to implement an efficient way of determining the vertices of every simplex face of dimension M in a given simplex of dimension N.
Why? What's a Simplex? Well, I was coding a 3D modelling library and decided to use the n-Simplex as the basic building block. The N-Simplex is the extension of the triangle to the Nth dimension. For example, the 0-Simplex is a point, the 1-Simplex is a Line, the 2-Simplex is a Triangle, the 3-Simplex is a Tetrahedron, and so on... See Simplex at wikipedia for more details and images on the simplex. It just happened that this relationship between points, lines and triangles was what I was looking for.
One of the thing we can do with any given N-Simplex is to get a list of all its constituing sub-simplices (or Faces) of any dimension between 0 and N. For example, the 0-Faces of the Triangle (2-Simplex) is a list of 3 Points or Vertices (0-Simplices), the 1-Faces of the same Triangle (2-Simplex) are 3 Lines or Edges (1-Simplices) and so on...
Now the relationship between the M-Faces of an N-Simplex and the Pascal Triangle is well known (see on the wikipedia page for details). And I coded a quick function to query the Pascal Triangle's rows and columns to find the count of Faces.
But what I needed was to actually build the list of such M-Faces, in fact, I needed to construct each of them using the vertices of my N-Simplex. I could have made a algorythm that uses recursion, which is what most people suggested when I questioned if this problem had been tackled before. But I knew there was a better way.
What I found is simple: The Vertices that are used to construct each of the M-Faces of an N-Simplex are those that have a bit set in the Combits Pattern for every numbers that can be made with a bit length of N+1 and that have exactly M+1 bits set.
What this means is, if I have a Tetrahedra (3-Simplex) and I wish to have the list of all its Lines or Edges (1-Simplex), the Pascal Triangle says there are 6. Let see what my technique says...
| Pascal's Triangle | Combits Pattern (4 bits) | Vertices of the 3-Simplex's M-Faces |
|||
| Row | Col | Value | |||
| 4 | 0 | 1 | Number Bitset nBits 0 . . . . . {0 } | 1x |
(-1)-Faces: (not useful) (-1)-Simplex1 = { } |
| 4 | 1 | 4 | Number Bitset nBits 1 1 . . . . { 1 } 2 . 1 . . . { 1 } 4 . . 1 . . { 1 } 8 . . . 1 . { 1 } | 4x |
0-Faces: Points or Vertices 0-Simplex1 = { V1 } 0-Simplex2 = { V2 } 0-Simplex3 = { V3 } 0-Simplex4 = { V4 } |
| 4 | 2 | 6 | Number Bitset nBits 3 1 1 . . . { 2 } 5 1 . 1 . . { 2 } 6 . 1 1 . . { 2 } 9 1 . . 1 . { 2 } 10 . 1 . 1 . { 2 } 12 . . 1 1 . { 2 } | 6x |
1-Faces: Lines or Edges 1-Simplex1 = { V1 V2 } 1-Simplex2 = { V1 V3 } 1-Simplex3 = { V2 V3 } 1-Simplex4 = { V1 V4 } 1-Simplex5 = { V2 V4 } 1-Simplex6 = { V3 V4 } |
| 4 | 3 | 4 | Number Bitset nBits 7 1 1 1 . . { 3 } 11 1 1 . 1 . { 3 } 13 1 . 1 1 . { 3 } 14 . 1 1 1 . { 3 } | 4x |
2-Faces: Triangles 2-Simplex1 = { V1 V2 V3 } 2-Simplex2 = { V1 V2 V4 } 2-Simplex3 = { V1 V3 V4 } 2-Simplex4 = { V2 V3 V4 } |
| 4 | 4 | 1 | Number Bitset nBits 15 1 1 1 1 . { 4} | 1x |
3-Faces: Cells 3-Simplex1 = { V1 V2 V3 V4 } |
This is a comparison of the row 3 of the Pascal Triangle compared to the numbers in the Combits pattern that have a bit count corresponding to the triangle's column.
This article only highlights a couple relationships that can be used to optimize certain recursive algorythms. For example, the programming library I am working on at the moment of writting this, called Hyperspace, is a n-dimensionnal modelling library (that I like to use in 3D) and since the basic building block of it is the n-Simplex, it follows that the algorythm that I will derive from the contents of this article will be efficient at working with Simplices of any number of dimensions. I will try to update this article with the resulting algorythm when I have it (and compared to the more intuitive recursive method). It will also be possible to see it in action once Hyperspace is ready!
Back to Sinusoid.ca |
|