Weird Binary

Imagine you are in charge of humanities search for extra terrestrials program. One day, after scanning the skies, you find a signal. The signal consists of a series of pulses, and after a little bit of work, you discover that they form an image 197×199 in size. The image contains what looks like simple arithmetic. However, no normal number-system seems to work.

Welcome to the world of "weird binary". So what exactly is going on? It turns out that even though a number system can be based on two different symbols, it doesn't have to be the traditional binary system we all know and love. These new binary number systems have differing properties, and come with their own strengths and weaknesses.

So what defines a binary number system? Firstly we require two symbols. Let us use "0" and "1" for simplicity. We also require a place-based number system, which we will assume operates in the normal right-to-left increasing powers of a single base. Note that we could imagine a left-to-right system, but that just corresponds to using the inverse of a right-to-left base, so doesn't add anything new.

Once we have this, we can define a simple multiplication table; anything multiplied by zero is zero, and 1×1=1. Similarly, addition by zero is idempotent. Thus only 1+1=2 needs to be defined, since "2" doesn't fit in our binary system. By choosing different representations of the number 2, we can define different binary number systems. Thus by enumerating these choices we can see which weird binary systems exist.

Before we will proceed, it is nice to define a format for such numbers. Unfortunately, the complexity of the addition operation will be quite large. This is due to the carries being unlike those of normal binary numbers. Thus, to simplify the carry calculation, we will provide an integer per bit. Such a layout would look like the following in C:

The above has the form of the weird binary encoded in the value of the number 2. This specification is stored within the add_spec array, of size add_spec_size. So long as the numbers aren't so large that the carries don't overflow an unsigned integer, the above can be used to add and multiply arbitrary precision weird binary numbers.

To create weird binary numbers, we can use induction. We know the value of one, and can then add it multiple times to obtain any natural number we require.

These C functions assume that the symbolic representation for the number two lies solely to the left of the radix point. This means that carries only propagate to the left. Allowing carries to propagate to the left and right simultaneously makes it rather difficult to construct an addition routine. (In effect it is possible to make a linear cellular automata this way, and such things are subject to the halting problem.) Of course, some cases are solvable. i.e. The case where 1+1=10.1 yields b+1/b=2, and thus b=1. This base-one solution also appears in other situations, see the 1+1=11 case below.

1+1=0

The first possibility results in a rather boring number system. In this system, addition works like the xor operator. Multiplication still mixes number places together. However, no carries take place, so all number positions operate as if they are alone with the "addition" step. This system is somewhat useful in cryptography, and Intel has added the PCLMULQDQ instruction to perform this operation.

1+1=1

This number system is even less interesting, with addition acting like a logical-or. Once you have a 1, you can never remove it. This means that negative numbers cannot exist in this system, since you can never add two non-zero numbers to get zero.

1+1=10

This is the traditional binary number system used in computers. By using twos-complement arithmetic, we can represent negative numbers. All normal mathematical operations work as you would expect in this system, (unlike the previous two systems). However, as you can see, this isn't the end of the story, as several more interesting binary systems exist.

1+1=x1

Any other binary system that defines two as ending with a 1 is problematic. In such systems, you cannot form minus one. (In other words, the equation 1 + y = 0 has no solution.) This severely restricts the usefulness of such systems. However, there is one system which is of note. 1+1=11 describes the "stick counting" system of natural numbers. The more sticks you have, the larger the number. The total number of sticks exactly corresponds to the number you have. Another way of looking at this system, is saying that it is "base 1". Unfortunately, working in base 1 is extremely inefficient, as the exponential savings in symbol compression don't happen. i.e. 999 only requires three symbols to write in decimal... but would require 999 symbols in base 1.

Since all the interesting systems will define two ending with a zero symbol, we can now evaluate what negative numbers are. This can be done by first calculating what minus one is, and then multiplying that by the correct natural number.

1+1=100

Using the above, we have b²=2, where b is the base. Thus, we find that the bases that satisfy this system are ±√2. This system thus can exactly store values proportional to the square root of two. This comes at a cost, numbers written in this form are twice as large as in normal binary. Normal binary can approximate the square root of two by including digits below the radix point. By using enough digits, the error can be made as small as needed. This means that this system is only really useful if exact calculations are required, and isn't really useful.

1+1=110

This system is defined by b²+b=2, and thus b=1, or b=-2. It turns out that the b=1 solution is spurious, leaving the base = -2, or "negabinary" number system. This number system is fairly well known. See Knuth's Art of Computer Programming, Seminumerical Algorithms for a discussion of its properties. Since this case is very similar to normal binary, (it is only the odd positions that vary), there exist some fast algorithms to convert from binary to negabinary and back. There are also fast ways to add, multiply and divide these numbers.

Such numbers are more uniform than normal binary. No twos-complement trick is required to represent negative numbers. Thus there is no longer a difference between signed and unsigned multiplication.

1+1=1000

This system is somewhat similar to the case where 1+1=100. It is a "fat binary" system, where there are multiple representations for the same numbers. In this case, the base is the cubic root of two, instead of the square root. The result is that numbers take three times as much space as normal. Such a system is only useful if you need exact arithmetic with such numbers.

1+1=1010

This case has b³+b=2, and has the following three solutions b=1, b=(-1±i√7)/2. The first base-one case is again spurious, leaving the two bases that are complex conjugates of each other. These bases allow one to calculate complex arithmetic using a single binary string. (The previous case also allowed complex solutions, but symmetry prevented them from being usefully different from the real case.)

Notice how the length of the numbers doesn't increase monotonically as they increase away from zero. This is due to the fact that the boundary of numbers of a given symbol length in this system is a fractal on the complex number plane:

1+1=1100

This case has b³+b²=2, resulting in b = 1, -1±i. Again, the base one solution is spurious. The resulting systems are quite well known, and are often presumed as the only complex binary ones. As can be seen by the previous case, this isn't so. See the book "Hacker's Delight" for a description, and the inverse problem of solving for the number two in these systems.

The symbol lengths for numbers in this system are increasing more rapidly than in the previous case. This is due to the fact that the previous system in effect de-weights imaginary numbers by a factor of the square root of seven. This weighting means that the previous system cannot exactly represent numbers such as the imaginary unit, i. In exchange for the larger verbosity, the current system doesn't suffer this problem.

Again, it turns out that the symbol lengths do not increase monotonically away from zero. The numbers of a given length form a "Dragon Fractal":

1+1=1110

This final case where the number two is represented by four symbols isn't particularly interesting. The cubic equation for the base produces horribly messy solutions. Only when you would like exact arithmetic with such a base would this system be better than others already discussed.

1+1=10000

This is yet another fat-binary case, where the base is the fourth root of two. Other than that, it is uninteresting.

1+1=10010

This yields a quartic equation, which unfortunately produces messy solutions just like the 1+1=1110 case. It isn't useful.

1+1=10100

This gives the equation b⁴+b²=2, having the solution b=±1,±i√2. Ignoring the non-imaginary solutions yields the interesting case of a pure-imaginary base. (Which one of the two we choose doesn't matter due to symmetry under complex conjugates.) This number system is also mentioned in Knuth's Art of Computer Programming, in where he states that its disadvantage over the -1+i system is the fact that the complex unit is represented by an infinitely long non-repeating string. However, if we use floating-point, then the small error introduced is usually ignorable. This is especially true because this system has no trouble exactly representing integers:

This complex number system technically is also fractal, but the system of nested rectangles isn't particularly complicated:

1+1=10110 ... 1+1=100010

These systems are again like 1110 and 10010, except with quartic and quintic equations needing to be solved. The resulting solutions are complex functions containing several nested roots, and as as result do not make very interesting bases.

1+1=101110

This case has b⁵+b³+b²+b=2, which amongst its solutions has b=(1±i√7)/2. Thus this case is very similar to that of 1+1=1010, and has the integer table:

This is the base used by the aliens described in the introduction. Their crazy mathematical statement is simply showing that 2+4=6.

Creating complex numbers in weird binary

As was shown in the beginning, creating natural numbers is easy, induction can be used to create any number once we have the definition of the number two. Integers can be created once we can evaluate what minus one is, which again only depends on the definition of the number two. Unfortunately, complex numbers aren't so simple. There, we need to know which of the possibly many solutions for the base we are using in order to obtain a value for the imaginary unit, i.

It turns out that the last number system described contains the identity i√7=1+b+b², when b = (1+i√7)/2. Thus we can simply divide by the square root of seven, and use induction again to evaluate any pure imaginary integer. There is one other case though, the fact that the base includes the factor of 1/2 means that this system also has half-integer complex numbers. These can be created by adding or subtracting the base, and simplifying the problem into the integer case. A C function which does this is:

For other weird binary bases, such as b=-1+i, the procedure is somewhat different, especially in that case, where i can be represented exactly.

The reverse process, of converting a weird binary number back to binary is relatively simple. We just add the relevant powers of the base. C code that does this is:

Conclusion

Are there any other interesting bases for weird binary? It turns out that no, there aren't. For a base to be interesting, its complex squared norm must be equal to two. A pure imaginary base with this is the b=±i√2, discussed above. Similarly, there is the pure real case b=±√2 also described. This leaves complex cases. Normalizing, we have:

We need 2/n² to be in lowest common terms to be a multiple of 1/n. If this isn't the case, then we can never build a terminating expression that evaluates to be the number two. The denominators will increase without limit as we increase the powers of the base, and no cancellation will occur. To prevent that, n needs to be 1 or 2. If n is one, then we get b = ±1 ±i, and if n is two, we obtain the other pure complex solutions; b = (±1±i√7)/2.

So binary number systems can be quite complicated. However, they unfortunately cannot represent quaternions or ocotonions due to the roots of polynomials being closed under the complex numbers. But still, as can be seen, there are several complex binary number systems, some more well known than others.

Comments

Justin said...

Not to pick nits, but when you say "anything multiplied by zero is zero, and 11=1. Similarly, addition by zero is idempotent", wouldn't it be more useful to say that zero is the additive identity, and that *multiplication* by zero is idempotent?

Both addition and multiplication by zero are idempotent, but idempotence is implied in the case of addition by zero being invariant.

Very interesting post however! Hopefully no aliens read this.

Awana56 said...

Someday I will come back to this page and make myself fully comprehend this.

Warren D. Smith said...

I don't agree with your proof at the end that "there are no other interesting bases for weird binary." You are assuming B has a specific quadratic irrational
form without justification, and indeed earlier you had made assumptions
contradicting that (note your remarks about quartic and quintic equations).

However... despite your proof being bogus, I suspect its conclusion is correct.

The demand that
              sum(k=0..D) B^k * {0 or 1} = 1+1
where B=squareroot(2)*exp(i*q) is a complex number on the circle of radius squareroot(2), is (for any given D-bit string) 2 equations (both the real & imaginary parts) with only one real degree of freedom (q) usable to solve them. So in general we would expect no solutions to exist, hence it is a miracle anytime a solution exists, hence presumably there are only a finite set of solutions.

My computer just did a search for all solutions with D<=10 and it does not agree that your quartic/quintic cases 1+1=10110 and 1+1=100010 and 1+1=10010 are even solutions at all. It claims these 6 are the only solutions:

base=sqrt2*exp(i*q)= 1.414214+0.000000i where q=0.000000(rad)= 0.000000(deg),
1+1=0000000100 note sqrt(2)=1.41421356237309504880
base=sqrt2*exp(i*q)= 0.500000+1.322876i where q=1.209429(rad)= 69.295189(deg), 1+1=0000101110 *
  note sqrt(7)/2=1.32287565553229529525

base=sqrt2*exp(i*q)= 0.000000+1.414214i where q=1.570796(rad)= 90.000000(deg), 1+1=0000010100 *

base=sqrt2*exp(i*q)=-0.500000+1.322876i where q=1.932163(rad)=110.704811(deg), 1+1=0000001010 *

base=sqrt2*exp(i*q)=-1.000000+1.000000i where q=2.356194(rad)=135.000000(deg), 1+1=0000001100 *

base=sqrt2*exp(i*q)=-1.414214+0.000000i where q=3.141593(rad)=180.000000(deg), 1+1=0000000100 *

I was looking at this because I was interested in "halvable objects." A compact connected measurable set in d-dimensional space is "halvable" if it can be cut into two 2^(-1/d) scaled copies of itself.

I proved the only 2D halvable objects are the 45-45-90 right triangle and
parallelograms with sidelength ratio squareroot(2). That is for CONVEX ones.
However... upon seeking nonconvex halvable 2D objects, I discovered the
weird binary examples, where the set in the complex plane is all sums of
   B^(-k) * {0 or 1}
for k=1,2,3...
and B is any base of a (complex) weird binary system. It would be nice to create a picture of all these with one in red, other in blue, showing how the red and blue translated copies (translated by 0 and 1) fit together to make a sqrt(2)-times larger copy of the same shape (rotated). You've already made some pictures that nearly are what I want, but not quite.

I do not currently know if any other 2D halvable objects exist.
--Warren D. Smith
warren.wds AT gmail.com

IBRAHIM said...

Dear sir,
kindly help me to send the answer of THE SQUARE ROOT OF 100100 in base two TO BASE TWO

Email:waleibrahim76@yahoo.com

ishaq umar abdullahi said...

Enter your comments here please kindly assist us with the answer.thanks for your anticipated perusal.

sfuerst said...

Sorry you two, this website isn't particularly helpful when you want others to do your homework. ;-)

Sebine said...

, -, public class RasterSB extends SeekBar { Paint bmpPaint=new Paint () ?bmpPaint , .. , RasterSB - .

101010010101010101001010110101001010101010100101011010100101010101010010101101010010101010101001010110101001010101010100101011010100101010101010010101101010010101010101001010110101001010101010100101011010100101010101010010101101010010101010101001010110101001010101010100101011010100101010101010010101101010010101010101001010110101001010101010100101011010100101010101010010101101010010101010101001010110101001010101010100101011010100101010101010010101 said...

so basically, my name is bob and i went to the store to pick up some marmite. marmite is short for "tea bag", so i think i did the right thing. for example, i bought the marmite specifically for the tin bag usage. the tin bag company is a wonderous sight. it goes from right to there, left to right, and all other stuff! hope you enjoy and about!