Large Numbers and base(-2) – WTF?

Introduction

Recently, I was asked to solve a puzzle using numbers encoded in base(-2). Most programmers are familiar with the binary system which encodes numbers in base(+2). When I first came across this strange concept, I thought “WTF?”, which of course means What’s This For? At first, I thought it was simply a contrived way to create puzzles to stump programmers, but as I solved the puzzle, I realized that there may be some practical use for such a bizarre concept.

Numbers encoded in base(-2) have some interesting properties. In this particular scenario, the numbers were represented by arrays of bits, each representing a different power of -2.

Background

In the familiar binary system, each bit represents the presences or absence of a different power of 2 in an integer. For example, the number 12 can be represented as:

To represent 12 in base(-2), we can do the same thing:

In fact, you can use any number, other than 0, 1 or -1, as a base to encode any other number. One can even use negative numbers. From the above, you would expect that base(-2) takes more bits to encode the same numbers as binary. Your perspective may change when we look at the encoding of the number -12:

And this is only for 32-bit integers. It takes twice as many bits for 64-bit integers. The reason for this is that modern computers don’t know how to subtract. Instead, they subtract by adding and ignoring the carry bit. To do this, they represent negative number in a format called “2’s complement”. To subtract a number, the computer takes the 2s complement of the number and adds it, then ignores the carry. You can do the same thing with decimal numbers using a 10s complement. The 10s complement of 6 is 10-6=4. So 4 is the same as “-6” in 10s complement and if we add them, we get 10 then ignoring the carry the answer is 0, which is what you expect when you add 6+(-6). Similarly 7+4=11, ignoring carry gives 1. This is complicated for decimal numbers, but really simple for binary numbers because the 2s complement is simply (~N)+1 or the bitwise not plus 1, which are quick and simple operations in the computer’s registers.

So, subtraction of normal integers relies on numbers rolling over. Hence, the upper limit to your favorite integer type. Let’s look at -12 in base(-2):

This representation does take more bits to represent -12 but only 1 more. Also note that we don’t need to rely on the “word size” or the number of bits in the data type to represent negative numbers. The cool thing here is that using this representation, we are no longer limited by the machine’s word size! We could use numbers of any size and never have to worry about roll over!

Unlimited Numbers

So could this representation be used to work with very large numbers? Yes, it can! But first, we have to come up with a concrete representation that is practical.

In a practical representation, we would want to have a variable number of digits, or bits in this case. We could start with the most significant (left-most) bit like we are used to in normal numbers, but it works out being a bit more practical to start with the least significant bit (2⁰) first and expand outward. This means we can use conventional list and array containers to hold our bits and tack things on to the end as the number gets bigger. Using such structures does put a practical limit on the size of the number we can represent since we can’t have more than 2³¹ bits in our lists, but that’s still a pretty huge number.

From this point forward, I will be writing our base(-2) number in ascending powers of -2. Thus 12 becomes 00111 and -12 becomes 001011.

Now you might ask “how easy is it to work with numbers represented this way?” Well, let’s take a look at some basic mathematical operations. First, let’s look at simply negating a number (changing its sign). This was pretty simple for conventional numbers. Is there a simple algorithm to get from 12 (00111) to -12 (001011)? It looks like a daunting task until you notice a simple property of these numbers:

The bit to the right (higher order) is always TWICE the value and OPPOSITE the sign of whatever bit you start with. This is true if you are a positive or negative bit.

So the algorithm to change the sign of a number is simple:

For each 1 bit, toggle the bit to the right and move on to the next 1 bit (skipping any bit you toggled).

This remarkably simple procedure can be done iteratively avoiding any costly recursion. It is not going to be as fast as the hardware based 2s compliment of conventional integers, but theoretically one could build hardware that does this, machine word by word. Generally, arbitrary precision math like this is not very efficient, but if you need it, you really don’t have many alternatives.

There is a Negate() method in the code that does this and returns a new negated HugeNumber from a given HugeNumber.

OK, well what about serious math like + and -? Are there simple algorithms for them too?

Well yes, there are. Adding and subtracting such strange bit strings does look like it could be very complicated at first. Once again, we have to look at the properties of the representation and what we have learned from our negation algorithm. One of the things we learned from negation is that we may need to work in pairs of bits, a negative and positive or positive and negative pair. So if we consider all possible pairs of bits, we see there are only 4 possible configurations and if we think that starting on a positive bit might be different than starting on a negative bit, we would only have 8 possible scenarios to deal with. This is tractable, but writing out all the scenarios reveals some simplifications. Let’s consider adding a bit to a pair of bits in the middle of the number:

Additions – Add One Bit

After reviewing the table, we see that the same pattern results regardless of whether we start on a positive or negative bit. Also the case where we add a bit to a 0 bit is trivial and doesn’t depend on the bit to the right. In only one case do we have to worry about carrying to the next highest position which is 2 bits up (the next pair). Again, we want to design this so it can be implemented as an iteration and not a recursion. In the code, you will see the AddBit private method which is called repeatedly until no carry is required. Once again, some hardware could be designed to do this, machine word by word.

What about subtraction? Well, like traditional computers, we could simply negate and add, but that’s inefficient here. Considering the simplicity of the add algorithm, we could code a direct subtraction method that avoids the extra step. Again looking at the patterns of pairs of bits, we see some simplifications:

Subtraction – Subtract One Bit

Again, we see a pattern similar to addition where the starting position doesn’t matter and the 1 bit cases are trivial. Also, only the 01 case results in a borrow, so similar logic results.

Multiplication and division can be built up from these operations, but there are more efficient algorithms than brute force. For example, a division or multiplication by powers of 2 can be done with a bit shift and a negate for odd powers of 2. I won’t go into those in this little adventure into the strange world of base(-2).

Using the Code

The code for this project is available at GitHub: https://github.com/bitzblitz/HugeNumber. You can build it in the free version of Visual Studio 2015.

It is a C# project with a simple console program to demonstrate some of the things you can do with the library. The library is a single class called HugeNumber that contains some simple constructors and operator overloads. You should be able to use HugeNumbers like regular integers. This demo project does not include multiplication, division or operators beyond +, - and negate. I could add these if anyone sees a point to it.

The HugeNumber class inherits from List<bool> and has operators for +, -, >, <, ==, >=, and <=.

Here is the code for the negate operation:

/// <summary> 
/// Change the sign of the number. 
/// </summary> 
/// <returns>A new HugeNumber with the opposite sign.</returns> 
public HugeNumber Negate() 
    { 
    HugeNumber negated = new HugeNumber(); 
    for(int b = 0;b < Count;++b) 
        { 
        if(this[b]) 
            { 
            negated.Add(true); 
            if(Count <= ++b) 
                negated.Add(true); // insert a bit 
            else 
                negated.Add(!this[b]); // compliment the next highest bit 
            } 
        else 
            negated.Add(false); // 0 stays 0 
        } 
    return negated.Trim(); 
    }

The addition operation is a bit more complicated, but all the heavy lifting is done by the AddBit method:

/// <summary> 
/// Adds a bit at bit position B. Note that this is and iterative approach to 
/// avoid the deep recursion that might occur in long carry scenarios. 
/// It should also be faster by avoiding function calls for simple operations. 
/// </summary> 
/// <param name="B">The bit position at which to increment.</param> 
/// <returns>true if a carry is required. Carries happen 2 bit positions up.</returns> 
protected bool AddBit(int B) 
    { 
    int pad = B - Count + 1; 
    while(pad-- > 0) 
        Add(false); 
    if(!this[B]) 
        { 
        this[B] = true; // increment this bit 
        return false; // no carry. 
        } 
    else 
        { 
        if(Count == B + 1) 
            Add(false); 
        if(this[B + 1]) 
            { 
            this[B] = false; // remove +bit_value 
            this[B + 1] = false; // also remove -2*bit_value 
            return false; // no carry 
            } 
        else 
            { 
            this[B] = false; // remove +bit_value 
            this[B + 1] = true; // add -2*bit_value 
            if(Count == B + 2) 
                { 
                Add(true); // make room for carry 
                return false; // no need to carry 
                } 
            return true; // need to carry on B+2 position to add +4*bit_value 
            } 
        } 
    } 
/// <summary> 
/// Adds this HugeNumber another to produce a third which is the mathematical sum 
/// of this and the other. 
/// </summary> 
/// <param name="Other">The number to add to our value.</param> 
/// <returns>A new HugeNumber with the value of us plus the other.</returns> 
public HugeNumber Add(HugeNumber Other) 
    { 
    HugeNumber result = new HugeNumber(this); 
    for(int b = 0;b < Other.Count;++b) 
        { 
        if(Other[b]) 
            { 
            int bit = b; 
            while(result.AddBit(bit)) 
                bit += 2; // carry required. 
            } 
        } 
    return result.Trim(); 
}

Points of Interest

This demonstration project used .NET and List<bool>, which stores actual bool objects. As such, it is not space efficient. In C++ the vector<bool> template has a specialization that uses actual bits for its underlying storage. In this case, the C++ implementation becomes space efficient and of potential practical use. If you really did need to do a lot of large number computations very fast, you could consider using an FPGA to do the bitwise operations discussed here in hardware, which would be another interesting project.