Monday, February 20, 2017

weirdbinary: fun (?) with an alternate binary packing

A friend of mine, Ken Bernstein, caught me at the end of the "Science and Spirituality" reading and discussion group we share and mentioned this idea to me, and was wondering if I could help him figure out if if i was useful or not. It involves binary numbers.

Typical positive binary numbers, the right most place is the "ones", the next one over is the "two's place", next one is "fours" etc. and it goes like this:
0000 = 0  (0*8 + 0*4 + 0*2 + 0*1)
0001 = 1  (0*8 + 0*4 + 0*2 + 1*1)
0010 = 2  (0*8 + 0*4 + 1*2 + 0*1)
0011 = 3  (0*8 + 0*4 + 1*2 + 1*1)
0100 = 4  (0*8 + 1*4 + 0*2 + 0*1)

etc.

But what if every other digit was flipped in value? Right most place is "ones", next one over is NEGATIVE twos, next one over is "fours", next one over is NEGATIVE eights...

First few counting numbers are like this
0000 = 0  (0*-8 + 0*4 + 0*-2 + 0*1)
0001 = 1  (0*-8 + 0*4 + 0*-2 + 1*1)
0110 = 2  (0*-8 + 1*4 + 1*-2 + 0 *1)
0111 = 3  (0*-8 + 1*4 + 1*-2 + 1 *1)
0100 = 4  (0*-8 + 1*4 + 0*-2 + 0 *1)

(At least I think this was the idea Ken was describing to be)

To be frank, I'm not very smart about thinking this kind of stuff through, but I can throw some computer work at, which I've done here: http://kirkdev.alienbill.com/2017/weirdbinary/

That's some extremely loose and crappy code. For one thing I wasn't smart enough to write a "decimal to weirdbinary" converter directly, but I could go the other way, so I start by generating all the decimal values for a lot of binary counting and storing the result, keyed on the decimal value.

Then I could plot the bit ordering, if you're just doing decimal counting, what do the bits look like... and I got this:


The red column on the right is regular binary, the blue is weirdbinary. Regular binary has a nice pattern, once you know what to look for... the ones place toggles every line, the twos place toggles every other line, the fours place toggles every four lines, etc. Weirdbinary... I guess it's about the same, but the rows are kind of offset?

After that, I tried seeing how different translations from weirdbinary to regular binary looked, using regular binary as the "standard" for calculating the y position:


Ok, so for that, the diagonal red line is the trivial case: binary 000001 = 1 pixel up, binary 0000010 = 2 pixels up, 00000011 = 3 pixels up, etc. The blue is where I take the decimal values (1,2,3 etc), get the "weirdbinary" bits for it, and then plot those bits as if they were an ordinary binary number. (So every value there is positive, since I'm not using a regular binary notation that can do negatives)

I then added the green by going the other way around: I take the counting decimal values, convert to binary, then see what those bits represent if we read them as weirdbinary. This forms a complementary pattern, which makes some intuitive sense.

So, getting back to Ken's question, is this useful for anything? Well, it might be kind of nice that you can represent negative numbers without using two's complement (which requires a fixed number of binary digits to work). I don't know if there's an "easy" way to count in weirdbinary, or to do basic addition and subtraction. 

Any thoughts?

FOLLOWUP: I have some smart friends on Facebook!  Jeremy pointed out that this "weirdbinary" system can be explained as being "Base Negative Two"... Wikipedia even mentions a polish computer that used it. I guess the term is "negabinary".

Scott pointed out Gray Code, another binary encoding system which has a lovely property that subsequent numbers only vary by one bit - clearly a win for making signal more robust and less prone to big error. 

No comments:

Post a Comment