# 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

With these three basic rules, it is possible to add. To add the antagons A and B, we simply:
- 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.

Note: I invented this number system in the year 2000. On 28 Feb 2001 I found this page, on which we learn that someone else, some time ago, got exactly the same wicked idea as I got. Does this mean it's good? =)