Friday, March 23, 2012

Intervals vs integers and why computers can't count

It struck me the other day that computers don't count that well and that there is a probably better form of binary.
Above shows the points where each bit flips as we count upwards from zero, giving our well known 0000 0001 0010 0011 0100 etc.
For an arbitrary length number this isn't a great system because many bits have to be flipped on the same clock tick. In fact the number of bit flips is unbounded, so to simply add 1 to 65535 for example we have to flip 16 bits. The worst case comes when going from -1 to 0, where every single bit must be flipped, an infinite task on an unbounded integer.

Instead computers could use a symmetrical system that flips the bits like so:

There are fewer bit flips and to count upwards you only need to flip one bit each time, giving 0000 0001 0011 0010 0110 0111 0101 0100 1100 etc.

Counting is a transition each tick, which takes you from one state to another. Therefore the states represent the period between the transitions, they are a set of intervals, just like a year or an age is an interval. If I say I am 25 then I am talking about a year-long interval. The set of intervals are different than the set of integers, unlike integers, intervals don't have a multiply since the result wouldn't be in the set of unit long intervals.
Given that our binary strings represent intervals, we can see how much cleaner it is to represent them this new way:
or as bit strings:
As you can see, the bit string is symmetrical around 0, so the top bit is effectively just a sign bit.

With the existing form of binary there is a choice of how to represent negative numbers, you can either have a sign bit, or you can use the result of extending the subtraction algorithm beyond zero (called the two's complement method). Whereas with this new binary system you don't have to choose as they are one and the same, negatives are a natural extension.

As I said, counting is switching between values each tick, so the values naturally represent the interval. If you want to store an integer rather than an interval then that is a trickier problem, currently computers simply consider the integer as the floor of the interval value, and we can do so in this case as well. The + and - will work as it did on the intervals, you just need to be careful in implementing the multiply function.
If we weren't worried about memory it is cleaner to make a new symbol 'c' meaning 'changing between 0 and 1', then you can see the integers are also symmetric:

Counting naturally operates on the set of intervals ..-2,-1,-0,0,1,2,..
'Symmetric binary' more naturally represents these intervals, and is faster for counting.
The integers (..-2,-1,0,1,2,..) are usually represented as the floor of the interval value, so are a derived representation.

The integer above any interval 1000... occurs at 2^n

Beyond binary
This symmetric system works best in binary since each digit changes at a regular pace, perhaps this is why we haven't used a symmetric system for decimal, and perhaps why we didn't consider this symmetric system when moving from our decimal into a binary form for computers. But we can do a decimal version, in it we can write the years up to and after the year 2000 change over:
1003 1002 1001 1000 2000 2001 2002 2003 2005 2005 2006 2007 2008 2009 2019 2018...

I could also imagine a long lost tribe somewhere using this system base 6 as you can count it on your fingers:
0 1 2 3 4 5 15 14 13 12 11 10 20 21 22 23 24 25 35 34 33 ..

Wednesday, March 14, 2012

Implementing fractal automata

Assuming you have a knowledge of how Conway's life or other cellular automata are implemented, here is a summary for making fractal automata.

Data structure
Your data structure needs to be a set of grids like so, doubling in their resolution each layer.
so the resolution of layer n is 1 << n by 1 << n. Each square just holds a boolean value. 1 or 0.

The new value at each square is a function f of its neighbours values (including its own present value), for example here are the neighbours of the red square:
You might say that the orange squares are its siblings, the yellows are its children and parent. I also sometimes include the grey squares as neighbours of the red square.

Each square is then updated independently according to function f. Like other cellular automata, you need to have a separate copy of the grid hierarchy so you can 'double buffer' and the change in one cell doesn't affect the others on that frame.

Layer order
The layers must be updated in a specific order, which appears like so:
So on frame 1 you update layer 3 based on its siblings and its parent(s). Since there is no layer below you can treat the layer below as being zeros, just as we do for the neighbours outside of the edges of the grid. On the next frame, update layer 2, then the next frame update layer 3 and so on.

Despite appearances the order is quite easy to calculate. Take the frame number in binary and find the position of the first 1 in it-
In our example we have four layers, so our depth is 4. If p is the position of the first 1, then:
layerToUpdate = depth - 1 - p.
To prevent overflow, add:
if layerToUpdate < 0
frame = 1;
layerToUpdate = depth-1;

The function f
The function f is the set of rules determining whether the centre square 'lives or dies', or you can call it the mapping from the neighbour values to 0,1. The number of mappings is so large that it helps to try out different simpler rule sets. For example a mapping based on the number of 'on' neighbours without worrying about where they are placed.