Method of complements

File:Complement numbering gnangarra.JPG

Complement numbers on an adding machine c. 1910. The smaller numbers, for use when subtracting, are the nines' complement of the larger numbers, which are used when adding.

In mathematics and computing, the method of complements is a technique used to subtract one number from another using only addition of positive numbers. This method was commonly used in mechanical calculators and is still used in modern computers.

The nines' complement of a number is formed by replacing each digit with nine minus that digit. To subtract a decimal number y (the subtrahend) from another number x (the minuend) two methods may be used:

In the first method the nines' complement of x is added to y. Then the nines' complement of the result obtained is formed to produce the desired result.

In the second method the nines' complement of y is added to x. If the result is positive, a leading digit '1' appears and is an end-around carry and brought to the least significant place and added. Discarding or carrying around the initial '1' is especially convenient on calculators or computers that use a fixed number of digits: there is nowhere else for it to go so it is otherwise simply lost during the calculation. The nines' complement plus one is known as the tens' complement.

The method of complements can be extended to other number bases (radix(ces)); in particular, it is used on most digital computers to perform subtraction, represent negative numbers in base 2 or binary arithmetic and test underflow and overflow in calculation.

Numeric complements

The radix complement of an n digit number y in radix b is, by definition, $b^n-y$. The radix complement is most easily obtained by adding 1 to the diminished radix complement, which is $(b^n-1)-y$. Since $(b^n-1)$ is the digit $b-1$ repeated n times (because $b^n-1 = b^n-1^n = (b-1)(b^{n-1}+b^{n-2}+...+b+1)=(b-1)b^{n-1}+...+(b-1)$; see also binomial numbers). The diminished radix complement of a number is found by complementing each digit with respect to $b-1$ (that is, subtracting each digit in y from $b-1$).

The subtraction of y from x may be performed as follows. Adding the diminished radix complement of x to y results in the value $b^n-1-x + y$ or $b^n -1-(x-y)$ which is the diminished radix complement of $x-y$, except for possible padding digits $b-1$. The diminished radix complement of this is the value $x-y$. Alternatively, adding the radix complement of y to x results in the value $x+b^n-y$ or $x-y+b^n$. Assuming y ≤ x , the result will always be greater or equal to $b^n$ and dropping the initial '1' is the same as subtracting $b^n$, making the result $x-y+b^n-b^n$ or just $x-y$, the desired result.

In the decimal numbering system, the radix complement is called the ten's complement and the diminished radix complement the nines' complement. In binary, the radix complement is called the two's complement and the diminished radix complement the ones' complement. The naming of complements in other bases is similar. Some people, notably Donald Knuth, recommend using the placement of the apostrophe to distinguish between the radix complement and the diminished radix complement. In this usage, the four's complement refers to the radix complement of a number in base four while fours' complement is the diminished radix complement of a number in base 5. However, the distinction is not important when the radix is apparent (nearly always), and the subtle difference in apostrophe placement is not common practice. Most writers use one's and nine's complement, and many style manuals leave out the apostrophe, recommending ones and nines complement.

Decimal example

Digit	Nines' complement
0	9
1	8
2	7
3	6
4	5
5	4
6	3
7	2
8	1
9	0

The nines' complement of a decimal digit is the number that must be added to it to produce 9; the complement of 3 is 6, the complement of 7 is 2, and so on, see table. To form the nines' complement of a larger number, each digit is replaced by its nines' complement.

Consider the following subtraction problem:

  873  (x, the minuend)
- 218  (y, the subtrahend)

The proper use of nines' complement requires no ambiguity in the sign of a written number. Ones' complement is the analogous system for binary and always has a signed bit to tell if the encoded number is positive or not. In decimal, this rule is a little different, since the most significant place has ten possible states instead of only two:

If the most significant digit of the number is less than 5, then the number is positive.

The number zero is not positive or negative, and the above rule says that the representation for zero doesn't begin with zero, which is not entirely true. Nines' complement, again in analogy with ones' complement for binary, has two representations of zero. Zero can be written as is, with only 0s as digits (0, 0.0, etc.), or where all the digits are 9s. 9, 9.9, 99, and even ...999.999... all represent zero; this is why negating a number by subtracting all of its digits from 9s makes sense, because 0 is represented by the 9s. Negative numbers have the appearance of "subtracting from infinity."

The significance of the rule about the most significant digit can be seen if one simply writes down a number with a leading digit that is not less than 5, such as 83. The rule says that 83 must represent a negative number. When one does the nines' complement of 83, it is:

  99 
- 83 
====
  16

The result, 16, is a smaller representation than 83. It would not make sense if 16 represented the negative of 83; in other words, 16 = -(83) is confusing if 16 represents a negative number. The leading digit of 16 is only a 1 so the rule again contradicts with this. 83 = -(16) is a much more reasonable conclusion. What, then, does positive 83 look like in nines' complement? To avoid the leading digit conundrum, a zero is simply added on the left. 083 is positive 83. Negating 083 provides more evidence:

  999
- 083
=====
  916

916 is very different from 16, the negation of 83. 916 represents -(083), or negative eighty-three, but 16 is just positive sixteen.

First method

Again, 873 has too large of a leading digit to be positive, but it is supposed to be positive, so a leading zero is needed. We compute the nines' complement of the minuend, 0873. Add that to the subtrahend, 218. 218 is positive so it has a zero in the same place as 0873 did.

  0873
- 0218

becomes

  9126  (nines' complement of x)
+ 0218  (y, the subtrahend)
=====
  9344

Because of the leading digit of 9, this answer is clearly negative, so its nines' complement needs to be calculated.

  9344 (result)
  0655 (nines' complement of result, the correct answer)

Note that the 0 can only be removed from 0655 if it is written in the traditional sign and magnitude notation, where the most significant digit rule is irrelevant.

Second method

We compute the nines' complement of 0218, which is 9781. Because 0218 is four digits long, this is the same as subtracting 0218 from 9999 (again, 9999 is a representation of zero). The 0 in front of 218 is not necessary to show that 218 is positive, but rather to keep track of the fourth place due to 0873 needing the 0 to avoid it being interpreted as -(126) instead.

Next, the sum of x and the nines' complement of y is taken:

  0873  (x)
+ 9781  (nines' complement of y)
=====
 10654

Because nines' complement in decimal is analogous to ones' complement in binary, the leading "1" is an end-around carry and must be moved to the least significant place and added to arrive at the correct result.

  0654
+    1
=====
  0655

The 0 that remains in the front correctly indicates that the answer is positive and not -(344).

Magnitude of numbers

In the following example the result of the subtraction has fewer digits than x:

   123410 (x, the minuend)
 - 123401 (y, the subtrahend)

Using the first method the sum of the nines' complement of x and y is

   876589 (nines' complement of x)
+  123401 (y)
=========
   999990

The nines' complement of 999990 is 000009. Removing the leading zeros gives 09, the desired result. Writing 9 would again just stand for zero.

If the subtrahend, y, has fewer digits than the minuend, x, leading zeros must be added in the second method. These zeros become leading nines when the complement is taken. For example:

  48032  (x)
-   391  (y)

can be rewritten

  48032  (x)
- 00391  (y with leading zeros)

Replacing 00391 with its nines' complement produces the sum:

  48032  (x)
+ 99608  (nines' complement of y)
=======
 147640

Doing the end-around carry with the leading 1 gives the right answer.

  47640
+     1
=======
  47641

Binary example

Binary digit	Ones' complement
0	1
1	0

The method of complements is especially useful in binary (radix 2) since the ones' complement is very easily obtained by inverting each bit (changing '0' to '1' and vice versa). And adding 1 to get the two's complement can be done by simulating a carry into the least significant bit. For example:

  01100100  (x, equals decimal 100)
- 00010110  (y, equals decimal 22)

becomes the sum:

  01100100  (x)
+ 11101001  (ones' complement of y)
+        1  (to get the two's complement)
==========
 101001110

Dropping the initial "1" gives the answer: 01001110 (equals decimal 78)

Negative number representations

Main article: Signed number representations

The method of complements normally assumes that the operands are positive and that y ≤ x, logical constraints given that adding and subtracting arbitrary integers is normally done by comparing signs, adding the two or subtracting the smaller from the larger, and giving the result the correct sign.

Let's see what happens if x < y. In that case, there will not be a "1" digit to cross out after the addition since $x-y+b^n$ will be less than $b^n$. For example, (in decimal):

  185  (x)
- 329  (y)

Complementing y and adding gives:

  185  (x)
+ 670  (nines' complement of y)
+   1
=====
  856

This appears to be the wrong answer; the expected answer is -144. But it isn't as far off as it seems; 856 happens to be the tens' complement of 144, so 856 represents -144. This can be addressed in three ways:

• Ignore the issue. This is reasonable if a person is operating a calculating device that doesn't support negative numbers since comparing the two operands before the calculation so they can be entered in the proper order, and verifying that the result is reasonable, is easy for humans to do.
• Represent negative numbers as radix complements of their positive counterparts. Numbers less than $b^n/2$ are considered positive; the rest are considered negative (and their magnitude can be obtained by taking the radix complement). This works best for even radices since the sign can be determined by looking at the first digit. For example, numbers in ten's complement notation are positive if the first digit is 0, 1, 2, 3, or 4, and negative if 5, 6, 7, 8, or 9. And it works very well in binary since the first bit can be considered a sign bit: the number is positive if the sign bit is 0 and negative if it is 1. Indeed, two's complement is used in most modern computers to represent signed numbers.
• Complement the result if there is no carry out of the most significant digit (an indication that x was less than y). This is easier to implement with digital circuits than comparing and swapping the operands. But since taking the radix complement requires adding 1, it is difficult to do directly. Fortunately, a trick can be used to get around this addition: Instead of always setting a carry into the least significant digit when subtracting, the carry out of the most significant digit is used as the carry input into the least significant digit (an operation called an end-around carry). So if y ≤ x, the carry from the most significant digit that would normally be ignored is added, producing the correct result. And if not, the 1 is not added and the result is one less than the radix complement of the answer, or the diminished radix complement, which does not require an addition to obtain. This method is used by computers that use sign-and-magnitude to represent signed numbers.....

Practical uses

File:Comptometer1920Model.jpg

Comptometer from the 1920s, with nines' complements marked on each key

The method of complements was used in many mechanical calculators as an alternative to running the gears backwards. For example:

• Pascal's calculator had two sets of result digits, a black set displaying the normal result and a red set displaying the nines' complement of this. A horizontal slat was used to cover up one of these sets, exposing the other. To subtract, the red digits were exposed and set to 0. Then the nines' complement of the minuend was entered. On some machine this could be done by dialing in the minuhend using inner wheels of complements (i.e. without having to mentally determine the nines' complement of the minuhend). In displaying that data in the complement window (red set), the operator could see the nines' complement of the nines' complement of the minuhend, that is the minuhend. The slat was then moved to expose the black digits (which now displayed the nines' complement of the minuhend) and the subtrahend was added by dialing it in. Finally, the operator had to move the slat again to read the correct answer.
• The Comptometer had nines' complement digits printed in smaller type along with the normal digits on each key. To subtract, the operator was expected to mentally subtract 1 from the subtrahend and enter the result using the smaller digits. Since subtracting 1 before complementing is equivalent to adding 1 afterwards, the operator would thus effectively add the ten's complement of the subtrahend. The operator also needed to hold down the "subtraction cutoff tab" corresponding to the leftmost digit of the answer. This tab prevented the carry from being propagated past it, the Comptometer's method of dropping the initial 1 from the result.
• The Curta calculator used the method of complements for subtraction, and managed to hide this from the user. Numbers were entered using digit input slides along the side of the device. The number on each slide was added to a result counter by a gearing mechanism which engaged cams on a rotating "echelon drum" (a.k.a. "step drum"). The drum was turned by use of a crank on the top of the instrument. The number of cams encountered by each digit as the crank turned was determined by the value of that digit. For example, if a slide is set to its "6" position, a row of 6 cams would be encountered around the drum corresponding to that position. For subtraction, the drum was shifted slightly before it was turned, which moved a different row of cams into position. This alternate row contained the nines' complement of the digits. Thus, the row of 6 cams that had been in position for addition now had a row with 3 cams. The shifted drum also engaged one extra cam which added 1 to the result (as required for the method of complements). The always present tens' complement "overflow 1" which carried out beyond the most significant digit of the results register was, in effect, discarded.

In computers

Use of the method of complements is ubiquitous in digital computers, regardless of the representation used for signed numbers. However, the circuitry required depends on the representation:

• If two's complement representation is used, subtraction requires only inverting the bits of the subtrahend and setting a carry into the rightmost bit.
• Using ones' complement representation requires inverting the bits of the subtrahend and connecting the carry out of the most significant bit to the carry in of the least significant bit (end-around carry).
• Using sign-magnitude representation requires only complementing the sign bit of the subtrahend and adding, but the addition/subtraction logic needs to compare the sign bits, complement one of the inputs if they are different, implement an end-around carry, and complement the result if there was no carry from the most significant bit.

Manual uses

The method of complements was used to correct errors when accounting books were written by hand. To remove an entry from a column of numbers, the accountant could add a new entry with the ten's complement of the number to subtract. A bar was added over the digits of this entry to denote its special status. It was then possible to add the whole column of figures to obtain the corrected result.

Complementing the sum is handy for cashiers making change for a purchase from currency in a single denomination of 1 raised to an integer power of the currency's base. For decimal currencies that would be 10, 100, 1,000, etc., e.g. a $10.00 bill.

In grade school education

In grade schools, students are sometimes taught the method of complements as a shortcut useful in mental arithmetic. Subtraction is done by adding the ten's complement of the subtrahend, which is the nines' complement plus 1. The result of this addition used when it is clear that the difference will be positive, otherwise the ten's complement of the addition's result is used with it marked as negative. The same technique works for subtracting on an adding machine.