Rainbow tables (number systems)

I just finished a discrete mathematics class here at UCSD, and part of the course was on number systems.  I want to share a very interesting technique I invented for taking the complements of numbers, which I and my classmates have found immensely helpful.

Why number complements?  Number complements are important because they allow us to do subtraction through addition. This makes computers cheaper because they eliminate the need for extra hardware to perform subtraction.  If you already know what complements are or just want to see the magic rainbow table in action, feel free to skip to the Rainbow Table section.

Number Complements

There are two complements for binary numbers: ones’ complement and two’s complement.

Ones’ Complement

Ones’ complement is defined as 2k - x - 1, where k is the number of digits and x is the positive number you want the negative version of. Interestingly, this can be easily found by “flipping” all the digits in the original positive binary number.  (We’ve known this for years.)  Make all 1s become 0s, and all the 0s become 1s.  For example, the ones’ complement of 0101 (5) is 1010 (-5 in ones’ comp).  Ones’ complement is nice since it allows us to subtract through addition, but there are a few small problems with it.  First, if you take the binary representation of 0 (0000 if we have 4 digits) and take its one’s complement, you get 1111, or -0.  This doesn’t really make sense, since there is no negative zero.  Second, the addition is a bit more involved than we optimally would like, because you have to add the carry-out digit back on the other side.  For example, let’s say you want to subtract 2 from 3 in ones’ complement binary with 4 bits.  You have:

 111
 0011 (3)
+1101 (-2, one's complement of 2 in binary: 0010)
10000

Everything has to happen inside the 4 digits, so the extra digit on the end is ignored in the final result, but in order to get the proper result in ones’ complement, the carry out digit has to be added back on the other side of the number.  That gives us:

 0000
+   1
 0001

0001 is 1 in binary, which is what we would expect since 3-2=1.

Two’s Complement

Two’s complement is the most widely used way to represent negative numbers in computers. The way you get two’s complement is by taking the value of ones’ complement and adding 1 to it.  For example, the two’s complement of 0101 (5 in binary) is 1010 + 1, or 1011 (-5 in two’s comp).  Two’s complement is better than one’s complement because it allows us to merely add numbers together and not worry about adding the carry out digit back on the other side. It does not have the problem of negative zero. 0000 flipped is 1111 + 1. Adding that gets us 10000, but we ignore the 1 since the number has to fit inside 4 digits. Let’s use the example of subtracting 2 from 3 again to demonstrate two’s complement.  This time, you have:

 11
 0011 (3)
+1110 (-2, two’s complement of 2 in binary: 0010)
10001

We ignore the carry out digit on the left and get 0001 as our answer, as expected.

The generalized version of binary’s ones’ complement is called the diminished radix complement, and the generalized version of binary’s two’s complement is called the radix complement.  This comes from the fact that binary is a base 2, because radix is another word for a number system base.

The Rainbow Table

As it turns out, this idea of number complements goes beyond binary.  In fact, it works with regular decimal numbers too!  The only problem is, how do we “flip” the digits to get the complements for regular decimal numbers?

Enter my invention, the Rainbow Table.
(Not to be confused with the cryptographic rainbow table.)

List all the digits for the base you are working with (in the case of decimal, 0-9) vertically and divide it through the middle horizontally.

partial rainbow tableNow, start at the middle and draw lines between pairs of numbers until there are no more numbers.  This is what it ends up looking like:

The full rainbow tableYou can begin to see why it was aptly named The Rainbow Table by my friend, Vincent Romo. (Hint: it looks like a rainbow turned sideways).

This rainbow table makes complements easy.  To flip a digit, just find the digit in the table and follow its line to the corresponding flipped value.  This gets you nines’ complement (the equivalent of binary’s ones’ complement).  To get ten’s complement, just add 1 like we did earlier for binary’s two’s complement.  Let’s look at the example of 60 – 40 to see ten’s complement in action:

At minimum, we need 3 digits (one digit needs to carry the sign of the number), so let’s pad the numbers with 0‘s.

 060
-040

Now, let’s transform -040 into ten’s complement using the rainbow table.

0 becomes 9
4 becomes 5
0 becomes 9

This gives us 959 as the 3 digit nines’ complement representation of -40. Adding 1 gives us 960 as the 3 digit ten’s complement representation.

Now, we can finally do the subtraction through addition.

 1
 060 (3)
+960
1020

Since we are only working in 3 digits, we ignore the 1 on the end. This gives us 020 (20) as the result, which is what we expected from 60 – 40! How cool is that?

Rainbow Tables and Other Number Bases

Flipping 0s and 1s in binary is just a specialized case of a rainbow table with only 0 and 1:

Binary Rainbow TableIn fact, Rainbow Tables work for all bases.  Hexadecimal, octal, ternary…you name it.  Just list out the digits for that base starting from 0, draw a line through the middle, and draw the rainbow.

Odd Bases

All the number bases discussed so far have been even (i.e. base 2 and base 10).  Base 3 (ternary) is an example of an odd base.  Rainbow Tables for odd bases are pretty much the same as before, with one slight difference – the middle digit stays fixed in the flipping process.  For example, this is a base 3 Rainbow Table:

Ternary Rainbow TableWhen you flip a ternary number, the 1s stay 1′s but everything flips the same way as before – just find the digit and follow the rainbow.  If you aren’t convinced, try some examples.

Conclusion

While you’re not likely to find yourself needing to take the complements of numbers regularly (you’re probably faster at doing regular subtraction), it is still an interesting topic to explore.  Rainbow tables make taking complements quite easy.  Another interesting topic to think about is how to determine the sign of a number in a base other than binary.  (It’s easy in binary, just look at the leftmost digit.  If it is a 1, it’s negative.  If it’s a 0, it’s positive.)  But enough for this post – that would make a good subject for another time.

This entry was posted in academic, computer science, mathematics and tagged , , , , . Bookmark the permalink.

One response to Rainbow tables (number systems)

  1. Nice post Zach. Rainbow Tables are also insanely helpful when breaking WPA2 encryption too.

    Dilanka

Leave a reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>