Antagons

Introduction

Don't we all dream about creating our own number systems from time to time? Comments like "I'm gonna use a number system based on 7" are rather semi-frequent in some circles, whereas "I'm gonna use PI for a base" are less frequent, but are still heard of. This is ridiculous.

The Antagon System

In the decimal system, each number is built up from digits, where each digit from right to left represents units, tens, hundreds and so on. In the binary system, the digits represent the values 1, 2, 4, 8, 16 etc. Now, suppose we used another number series here. Suppose we used 1, 1, 2, 3, 5, 8, 13 etc. This is the Fibonacci series, in which each number is the sum of the two preceding ones. As digits, we only use zeroes and ones.

In this system, the decimal number 123 could be written as 10100000000. Other ways to write the same number would be 1110101100 and 10010101011 and several more.

89--55--34--21--13---8---5---3---2---1---1

 1   0   1   0   0   0   0   0   0   0   0    89 + 34 = 123

 0   1   1   1   0   1   0   1   1   0   0    55 + 34 + 21 + 8 + 3 + 2 = 123

 1   0   0   1   0   1   0   1   0   1   1    89 + 21 + 8 + 3 + 1 + 1 = 123

I call these binary lookalike numbers antagons. They represent positive integers, and all integers except 0 can be represented by more than one specific antagon.

Optimizing an antagon

The magnitude of every column is the sum of the magnitudes of the two columns to the right of it. Therefore, if we ever find the bit sequence 011 inside a number, we can replace it with 100. Let's have a look at the middle example above (01110101100). The last five digits begin with 011, so here we can perform a substitution without changing the value of the antagon.

01110101100 (Original number)
01110110000 (First substitution)

Now we search the number from right to left. Can we find another magic 011 sequence? Yes we can... we just created one by writing a 1 as the fifth bit from the right.

01111000000 (Second substitution)

Once more, we look for the sequence in the number. This time, it is only present at one place, to the far left of the number. (Obviously, the number 1111000000 is the same as 01111000000.)

10011000000 (Third substitution)

Once more...

10100000000 (Fourth substitution)

Now there are no 011 sequences in the number anymore. This antagon is called the OPTIMIZED antagon of the decimal number 123. It is called optimized because it uses the lowest possible number of ones to express the number.

Note: When optimizing an antagon, all bits are to be moved as far to the left as possible. If an antagon ends in ...001 it will be optimized into ...010. Therefore, an optimized antagon always ends with a 0.

Dextimizing an antagon

If 011 can be substituted by 100, then 100 can of course be substituted by 011. The procedure in which all 100 sequences are replaced by 011 sequences is called DEXTIMIZATION, because it is the opposite of optimization, and it shifts ones towards the right.

10100000000 (123, optimized)
10011000000 (First substitution)
01111000000 (Second substitution)
01110110000 (Third substitution)
01110101100 (Fourth substitution)
01110101011 (Fifth substitution, no 100 sequences left)

The dextimized antagon of the decimal number 123 is 01110101011.

Note: When dextimizing an antagon, all bits are to be moved as far to the right as possible. If an antagon ends in 10 it will be dextimized into 01. Therefore, all dextimized antagons (except 0) will end with a 1.

Basic arithmetic rules

• To check if an antagon is ZERO, we can dextimize it and test the rightmost bit.
• To INCREMENT an antagon, we optimize it and set the rightmost bit.
• To DECREMENT an antagon, we dextimize it and check if the antagon is zero. If it isn't, we reset the rightmost bit.

Simple addition

• 1) Check if B is zero, in which case A is the sum of the antagons.
• 2) Decrement B and increment A.
• 3) Go back to step 1.

Example: perform the addition 6 + 3 = 9.

A = 10001 (=6)  B = 01000 (=3)

B is not zero, so we're not done yet. Decrement B, i.e. dextimize it and
clear the rightmost bit.

B = 00101, B = 00100

Increment A (optimize it and set the rightmost bit).

A = 10010, A = 10011

We keep repeating these steps until B becomes 0.

B = 00011, B = 00010
A = 10100, A = 10101

B = 00001, B = 00000
A = 11000, A = 11001

Now B is zero, and A is 5+3+1 = 9, the result of the addition.

But this is a very cumbersome way to do an addition, especially when B is large. Let's try to find a better method...

Double substitution

The antagon 0020000 is not a real antagon, because it uses other digits than 0 and 1. But for the sake of argument, let's say that it is worth 2 times the value of the position in which the 2 has been written. 2*5 = 10. How can we write 10 as an antagon? Well, the optimized version is 0100100.

Let us have a look at the Fibonacci series again:

89 55 34 21 13  8  5  3  2  1  1

Note how every number, when doubled, equals the sum of the number immediately to the left of it and the number two steps to the right of it. (This is not true for the rightmost 1, though.)

The DOUBLE SUBSTITUTION works when you have an antagon with a 2 in it. You change the 2 into a 0, and at the same time you add 1 to the digit to the left of the 2, and 1 to the digit two steps to the right of the 2.

A better addition method

In some cases, the addition of two antagons is simple. This is when they do not have any ones in the same columns.

Example: Add 00100110 and 01010001. The result is 01110111, because we can simply add or "or" them as if they were two binary numbers.

What happens when we try to add 00100110 to 00101001? They both have a 1 in the 8's position.

00100110
00101001

The trick is this: Optimize the first antagon (let's call it A). A=00101000. Now take each 1 from the other antagon (B), going from left to right, and add it to A. If A has a 0 at that position, simply write a 1 instead. If A has a 1 at that position, write a 2 and do a double substitution.

A = 00101000
B = 00101001, but just care about the leftmost 1 for now.

A = 00201000, so A = 01002000, so A = 01010010.

As you can see, an intermediate step was required here. The number to the left of the original 2 will always be a 0 if A is optimized, because in an optimized antagon there are never any consecutive 1s. But the number that is two steps to the right of the 2 may be a one. In that case, simply write a 2 there and do another double substitution, and continue until A is a real antagon again (i.e. it has no 2s in it).

Now, one of the ones in B has been added. To add the next one using the same algorithm, it is vital to optimize A again! Otherwise there's no guarantee that A will never contain more than a single 2, and that makes programming an antagon addition much more difficult.

Right, so let's carry on with the example.

A = 01010010  (can't be optimized any further)
B = 00101001, but just care about the middle 1.

A = 01011010  (simply change the 0 to a 1, no need to double substitute)

Now we can optimize A a bit

A = 10000010
B = 00101001, but just care about the last 1.

A = 10000011

That was the last bit in B. We've got the sum in A, and may wish to optimize A to get 10000100 as a result.

Negative antagons and subtraction

What should we add to 7 to get 0?

10100 + x = 0 (where x is an antagon)

Obviously, since an antagon is defined as a positive integer, there is no solution to the above equation. But in a computer we're often dealing with a fixed number of bits anyway, and usually we gain more than we lose if we define the highest bit as some kind of negative sign.

Let's try this instead:

00000000000010100 + x = 10000000000000000

These antagons have 17 bits. Suppose the 17th bit will just disappear like a carry bit. Then the equation would be equal to the one above it.

After some trial-and-error we end up with the following:

00000000000010100 + 00111111111101011 + 1 = 10000000000000000

That is, to get the NEGATIVE COMPLEMENT of an antagon, we INVERT the bits in it, EXCEPT the highest one (i.e. the 16th bit, the 17th is just a carry bit and shouldn't be included in the result anyway), and then we ADD 1.

Example: What is 14 + (-5) equal to?

First, we choose a 16-bit representation of antagons.

14 = 0000000001000010
 5 = 0000000000010000
-5 = 0111111111101111 + 1
-5 = 1010101010010100 + 1 (optimizing it)
-5 = 1010101010010101     (since we just optimized it, we can add one
                           by setting the rightmost bit)

14 + -5 = 0000000001000010 + 1010101010010101

0000000001000010
1010101010010101

When adding one bit of -5 at a time, we don't get any 2's to bother about. In other words, we can add by just "or"ing the antagons.

 1010101011010111

Optimize...

10000000000100010

The 17th bit is not part of the answer. The answer is thus 100010, which is 9.

Decrementing zero

All previously stated rules (increment, decrement etc.) still apply to negative antagons, with one amendment: To decrement zero, we have to change it into its carry-bit equivalence, e.g. 10000000000000000 in a 16-bit system. When dextimized, that becomes 01010101010101011. Now it is possible to clear the rightmost bit, and so we get 01010101010101010.

This antagon is optimized. If we increment it, we get 10000000000000000 (zero). Conclusions: In an unsigned system, the antagon 10101010...10 is the highest possible antagon. In a signed system, all positive antagons, when optimized, have their most significant bit cleared. All negative antagons, when optimized, have their most significant bit set. Zero is therefore considered positive.

It doesn't end here

Have you found any new rules, or any other curious behaviour of the antagons, that you perhaps wish to have included in this file? Then hesitate no more; mail me about it!

Linus Akesson.