Complementary Arithmetic Content from the guide to life, the universe and everything

Complementary Arithmetic

2 Conversations

This entry explains complementary arithmetic in the familiar context of decimal numbers, demonstrating that this arithmetic is not just a special technique used by binary machines. It also describes how this arithmetic is adapted for binary machines, incidentally revealing why the range of binary signed numbers is unsymmetrical, and biased in favour of negative values.

Why Use Complementary Arithmetic?

Addition of two single digit numbers is easy, unless the numbers are signed. In the four sums below, for which the answers are obvious, try to consider how the answer is actually obtained in each case.

  • (+3) + (+5) = +8

  • (–3) + (+5) = +2

  • (–3) + (–5) = –8

  • (+3) + (–5) = –2

The general rule that applies in every case (the rule a machine would need to follow) is quite complicated. Something along the lines:

  • Compare the signs of the numbers. If they're the same, that is the sign of the result, and the magnitudes of the numbers are to be added.

  • Otherwise, subtraction is required. Compare the magnitudes of the two numbers, and the result sign is the sign of the larger. Swap the numbers if need be, to subtract the smaller magnitude from the larger (perhaps doing something special if they are equal).

It would be so much easier, and quicker, if the signed numbers could just simply be added. Complementary arithmetic is designed to allow exactly that.

What is Complementary Arithmetic?

Complementary arithmetic uses a simple process: if the given problem (addition) is too difficult, adjust the problem to make it easier. In this case, the specific manoeuvre is to eliminate negative numbers.

Let's suppose that the largest magnitude we'll need to deal with is 49. We have to be able to perform two-digit arithmetic, and therefore have 100 values at our disposal, which are 0 to 99. We can use these values for the 49 numbers +1 to +49, the 49 numbers –49 to –1, the number 0, and one other number. In other words, we can use the values to encode the numbers.

It would be most convenient if the results of encoding could be added using arithmetic rules that are little changed. There are actually two reasonably simple methods to encode numbers in the range –49 to +49 as two digit values.

Nines Complement Arithmetic

The numbers 0 to +49 are unmodified, but the negative numbers –49 ≤ –n ≤ –1 are encoded as 99 – n, which is known as the Nines Complement of n. This subtraction is very easy to do, because no borrowing among digits is possible, since 9 is the largest decimal digit. In this system, all numbers are usually referred to as Nines Complement values, even if they represent positive quantities, and so have not been modified by complementation.

Addition of Nines Complement values is identical to the addition of ordinary decimal numbers, except for one extra step. If adding the two leftmost digits results in a carry, this is added in the rightmost digit position, a procedure known as end-around carry. Although this step is rather unfamiliar, even possibly mysterious, it is very easy to do, and cannot result in a further carry at the left.

The basic sums given above are performed again, by translating to Nines Complement values, and carrying out the addition as described, using c to denote any end-around carry.

  • (+3) + (+5) encodes as (03) + (05) giving (08), representing +8

  • (–3) + (+5) encodes as (96) + (05) giving (c01) and then (02), representing +2

  • (–3) + (–5) encodes as (96) + (94) giving (c90) and then (91), representing –8

  • (+3) + (–5) encodes as (03) + (94) giving (97), representing –2

As desired, we have added signed values by direct addition, but this method has a snag. The codes 00 to 49 represent 0 to +49, and codes 50 to 98 represent –49 to –1; but, what does code 99 represent?

Code 99 is unchanged by adding zero. If any other value is added, the result will exceed 100, and cause an end-around carry. This causes the result to be equal to the number added, for example 99 + 03 = c02, which becomes 03. Thus, code 99 acts rather like zero, and is the Nines Complement of 00. The ingenious convention sometimes used is that 00 represents +0 and 99 represents –0, but the awkwardness of two different zeroes and the need for end-around carry are just two reasons that Nines Complement arithmetic was rarely used.

The given example can be generalised, so that any required integer can be represented. Instead of using only two decimal digits, one can use as many as are required. The Nines Complementing operation just involves a number with as many nines as there are digits.

Tens Complement Arithmetic

The numbers 0 to +49 are unmodified, but the negative numbers –49 ≤ –n ≤ –1 are encoded as 100 – n, which is known as the Tens Complement of n. This subtraction appears to require an extra digit, but this is avoidable. The value 100 – n is formed as ( 99 – n ) + 1, that is by incrementing the Tens Complement of n. As noted above, the subtraction needed to form the Nines complement is easy to perform because no borrows can occur.

Addition of Tens Complement values is extremely easy, and identical to normal addition. The basic sums given above are performed again, by translating to Tens Complement values. This time carries at the left are simply ignored.

  • (+3) + (+5) encodes as (03) + (05) giving (08), representing +8

  • (–3) + (+5) encodes as (97) + (05) giving (02), representing +2, with carry ignored

  • (–3) + (–5) encodes as (97) + (95) giving (92), representing –8, with carry ignored

  • (+3) + (–5) encodes as (03) + (95) giving (98), representing –2

As required, we have added signed values by direct addition. The codes 00 to 49 represent 0 to +49, and codes 51 to 99 represent –49 to –1; but, what does code 50 represent?

A case can be made for code 50 to represent the number +50, by encoding the sum (+49) + (+1) = +50. An equally valid case can be made for –50, by encoding (–50) + (+1) = –49. The simple rule that a leading digit of 4 or less signifies a positive value (or zero), and a leading digit of 5 or more signifies a negative value, is a strong bias toward choosing –50. As code 50 is its own Tens Complement, this value (alone) cannot sensibly be complemented, whichever choice is made1.

The Tens Complement technique can be extended to as many digits as required, just as the Nines Complement can. The Tens Complement is found by incrementing a Nines Complement of suitable length. This is why, for two digits, it is not called a Hundreds Complement, as the formula 100 – n might suggest.

The advantage of using the Tens Complement encoding for addition is obvious, but it makes subtraction just as easy. To subtract a number, instead add its Tens Complement! Only one example of this is given. (–5) – (–3) encodes as (95) – (97), which converts to (95) + (03) giving (98), representing –2. (The Tens complement of 97 can be formed, even though +97 is not one of the numbers that can be encoded.)

Better yet, Tens Complement-encoding works for multiplication, if the resulting products are truncated

  • (+3) x (+5) encodes as (03) x (05) giving (0015), becoming (15) representing +15

  • (–3) x (+5) encodes as (97) x (05) giving (0485), becoming (85) representing –15

  • (–3) x (–5) encodes as (97) x (95) giving (9215), becoming (15) representing +15

  • (+3) x (–5) encodes as (03) x (95) giving (0285), becoming (85) representing –15

Double precision products2 can also be formed with a small adjustment. If an encoding represents a negative number, add the Tens Complement of the other factor at the left of the four digit product, thus:

  • (+3) x (+5) is (03) x (05) giving (0015), representing +15

  • (–3) x (+5) is (97) x (05) giving (0485), adding (95--) gives (9985) representing –15

  • (–3) x (–5) is (97) x (95) giving (9215), adding (05--) and (03--) gives (c0015) representing +15

  • (+3) x (–5) is (03) x (95) giving (0285), adding (97--) gives (9985) representing –15

In summary, Tens Complement arithmetic works exceedingly well for addition, subtraction and multiplication. Additionally, double precision products can be obtained with only a modest extra effort. Division, however, is considerably more difficult.

Binary Machines

Few computers today use decimal arithmetic, as binary arithmetic requires much less hardware. The complementary arithmetic methods given above for decimal values are easily adapted for this purpose.

Instead of Nines Complements, Ones Complements are used, because one is the largest binary digit. Instead of Tens Complements, Twos Complements are used, because two is one greater than one, as ten is one greater than nine. Twos Complement arithmetic is as easy (or as difficult) as the underlying binary arithmetic.

Some hardware implementations use a few tricks, which should be mentioned. Firstly, Ones Complementing is very easy indeed: zero digits become one, and one digits become zero, which is just logical complementation. As in Nines Complementing, no carries occur from digit to digit, which in binary means bit to bit. Each bit can be handled separately.

The incrementing needed to form a Twos complement from a Ones complement is often performed by subterfuge. In adding most bits, a carry from lower order bits must also be handled, so a bit adder really takes three bits to give a result bit and a carry bit. The carry in is not really needed for the lower order bit; but, if it happens to be provided, adding a Twos Complement can be achieved by adding a Ones Complement and forcing a carry into the first bit.

In Tens Complement arithmetic, the digits are 'big' enough to contain a sign if the leading digit of the signed representation is four or less. In Twos Complement arithmetic, that is no longer true, and the sign occupies a whole bit. For this reason, the choice corresponding to the value assigned to code 50 in the decimal examples is invariably made one way: the sign bit is always one for negative values3.

Twos Complement arithmetic allows signed numbers to be handled as unsigned numbers, by an encoding trick. That's all there is to it.

1 This problem is of minor importance in practice.2 Products with twice as many digits as given for the factors.3 Roughly corresponding to choosing -50 in decimal.

Bookmark on your Personal Space

Edited Entry


Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry

Categorised In:

Written by

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more