Infinite-precision ten’s complement
Imagine the odometer of an automobile. It has a certain number of wheels, each with the ten digits on it. When one wheel goes from 9 to 0, the wheel immediately to the left of it, advances by one position. If that wheel already showed 9, it too goes to 0 and advances the wheel to its left, etc. Suppose we run the car backwards. Then the reverse happens, i.e. when a wheel goes from 0 to 9, the wheel to its left decreases by one.

Now suppose we have an odometer with an infinite number of wheels. We are going to use this infinite odometer to represent all the integers.

When all the wheels are 0, we interpret the value as the integer 0.

A positive integer n is represented by an odometer position obtained by advancing the rightmost wheel n positions from 0. Notice that for each such positive number, there will be an infinite number of wheels with the value 0 to the left.

A negative integer n is represented by an odometer position obtained by decreasing the rightmost wheel n positions from 0. Notice that for each such positive number, there will be an infinite number of wheels with the value 9 to the left.

In fact, we don’t need an infinite number of wheels. For each number only a finite number of wheels is needed. We simply assume that the leftmost wheel (which will be either 0 or 9) is duplicated an infinite number of times to the left.

While for each number we only need a finite number of wheels, the number of wheels is unbounded, i.e., we cannot use a particular finite number of wheels to represent all the numbers. The difference is subtle but important (but perhaps not that important for this particular course). If we need an infinite number of wheels, then there is no hope of ever using this representation in a program, since that would require an infinite-size memory. If we only need an unbounded number of wheels, we may run out of memory, but we can represent a lot of numbers (each of finite size) in a useful way. Since any program that runs in finite time only uses a finite number of numbers, with a large enough memory, we might be able to run our program.

Now suppose we have an addition circuit that can handle nonzero integers with an infinite number of digits. In other words, when given a number starting with an infinite number of 9s, it will interpret this as an infinitely large positive number, whereas our interpretation of it will be a negative number. Let us say, we give this circuit the two numbers …9998 (which we interpret as -2) and …0005 (which we interpret as +5). It will add the two numbers. First it adds 8 and 5 which gives 3 and a carry of 1. Next, it adds 9 and the carry 1, giving 0 and a carry of 1. For all remaining (infinitely many) positions, the value will be 0 with a carry of 1, so the final result is …0003. This result is the correct one, even with our interpretation of negative numbers. You may argue that the carry must end up somewhere, and it does, but in infinity. In some ways, we are doing arithmetic modulo infinity.

Some implementations of some programming languages with arbitrary precision integer arithmetic (Lisp for instance) use exactly this representation of negative integers.

Let us finish this section by giving a simple method for computing the absolute value of a negative integer in our representation. It suffices to take each individual digit, replace it by 9 minus its original value, and then at the end, add 1 to the number obtained. So for instance, the number …9998 becomes 1 plus …0001 which is …0002. This method works both ways, i.e. you can also use it to negate a positive number.

Finite-precision ten’s complement
What we have said in the previous section works almost as well with a fixed bounded number of odometer wheels. The only problem is that we have to deal with overflow and underflow.

Suppose we have only a fixed number of wheels, say 3. In this case, we shall use the convention that if the leftmost wheel shows a digit between 0 and 4 inclusive, then we have a positive number, equal to its representation. When instead the leftmost wheel shows a digit between 5 and 9 inclusive, we have a negative number, whose absolute value can be computed with the method that we have in the previous section.

We now assume that we have a circuit that can add positive three-digit numbers, and we shall see how we can use it to add negative numbers in our representation.

Suppose again we want to add -2 and +5. The representations for these numbers with three wheels are 998 and 005 respectively. Our addition circuit will attempt to add the two positive numbers 998 and 005, which gives 1003. But since the addition circuit only has three digits, it will truncate the result to 003, which is the right answer for our interpretation.

A valid question at this point is in which situation our finite addition circuit will not work. The answer is somewhat complicated. It is clear that it always gives the correct result when a positive and a negative number are added. It is incorrect in two situations. The first situation is when two positive numbers are added, and the result comes out looking like a negative number, i.e, with a first digit somewhere between 5 and 9. You should convince yourself that no addition of two positive numbers can yield an overflow and still look like a positive number. The second situation is when two negative numbers are added and the result comes out looking like a nonnegative number, i.e, with a first digit somewhere between 0 and 4. Again, you should convince yourself that no addition of two negative numbers can yield an underflow and still look like a negative number.

We now have a circuit for addition of integers (positive or negative) in our representation. We simply use a circuit for addition of only positive numbers, plus some circuits that check:

* If both numbers are positive and the result is negative, then report overflow.
* If both numbers are negative and the result is positive, then report underflow.