Method of complements

In mathematics and computing, the method of complements is a technique to encode a symmetric range of positive and negative integers in a way that they can use the same algorithm (hardware) for addition throughout the whole range. For a given number of places half of the possible representations of numbers encode the positive numbers, the other half represents their respective additive inverses. The pairs of mutually additive inverse numbers are called "complements". Thus subtraction of any number is implemented by adding its complement. Changing the sign of any number is encoded by generating its complement, which can be done by a very simple and efficient algorithm. This method was commonly used in mechanical calculators and is still used in modern computers. The generalized concept of the "radix complement" (as described below) is also valuable in number theory, such as in Midy's theorem.
The "nines' complement" of a number given in decimal representation 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" and one is added to the sum. The leading digit '1' of the result is then discarded. Discarding the initial '1' is especially convenient on calculators or computers that use a fixed number of digits: there is nowhere for it to go so it is simply lost during the calculation. The nines' complement plus one is known as the "ten's complement."
The method of complements can be extended to other number bases (radices); 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, formula_1. The radix complement is most easily obtained by adding 1 to the diminished radix complement, which is formula_2. Since formula_3 is the digit formula_4 repeated "n" times (because formula_5; see also Geometric series Formula), the diminished radix complement of a number is found by complementing each digit with respect to formula_4 (that is, subtracting each digit in "y" from formula_4).
The subtraction of "y" from "x" may be performed as follows. 
Adding the diminished radix complement of "x" to "y" results in the value formula_8 or formula_9 which is the diminished radix complement of formula_10. The diminished radix complement of this is the value formula_11. Alternatively, adding the radix complement of "y" to "x" results in the value formula_12 or formula_13. Assuming "y ≤ x" , the result will always be greater or equal to formula_14 and dropping the initial '1' is the same as subtracting formula_14, making the result formula_16 or just formula_11, 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.
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]
First method.
We compute the nines' complement of the minuend, 873. Add that to the subtrahend 218, then calculate the nines' complement of the result.
 126 [nines' complement of x = 999 - x]
 + 218 [y, the subtrahend]
 344 [999 - x + y]
Now calculate the nines' complement of the result
 344 [result]
 655 [nine's complement of 344 = 999 - (999 - x + y) = x - y, the correct answer]
Second method.
We compute the nines' complement of 218, which is 781. Because 218 is three digits long, this is the same as subtracting 218 from 999.
Next, the sum of "x" and the nines' complement of "y" is taken:
 873 [x]
 + 781 [nines' complement of y = 999 - y]
 1654 [999 + x - y]
The leading "1" digit is then dropped, giving 654.
 1654
 -1000 [-(999 + 1)]
 654 [x - y - 1]
This is not yet correct. We have essentially added 999 to the equation in the first step. Then we removed 1000 when we dropped the leading 1 in the result 1654 above. This will thus make the answer we get (654) one less than the correct answer formula_18. To fix this, we must add 1 to our answer:
 654
 + 1
 655 [x - y]
Adding a 1 gives 655, the correct answer to our original subtraction problem.
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 9 the desired result.
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 and adding 1 produces the sum:
 48032 [x]
 + 99608 [nines' complement of y]
 + 1
 147641
Dropping the leading "1" gives the correct answer: 47641.
Binary method.
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). Adding 1 to get the two's complement can be done by simulating a carry into the least significant bit. For example:
 0110 0100 [x, equals decimal 100]
 - 0001 0110 [y, equals decimal 22]
becomes the sum:
 0110 0100 [x]
 + 1110 1001 [ones' complement of y = 1111 1111 - y]
 + 1 [to get the two's complement = 1 0000 0000 - y]
 10100 1110 [x + 1 0000 0000 - y]
Dropping the initial "1" gives the answer: 0100 1110 (equals decimal 78)
Negative 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 formula_19 will be less than formula_14. For example, (in decimal):
 185 [x]
 - 329 [y]
Complementing "y" and adding gives:
 185 [x]
 + 670 [nines' complement of y]
 + 1
 856
At this point, there is no "simple" way to complete the calculation by subtracting formula_14 (1000 in this case); one cannot simply ignore a leading 1. The expected answer is −144, which isn't as far off as it seems; 856 happens to be the ten's complement of 144. This issue can be addressed in a number of ways:
Practical uses.
The method of complements was used in many mechanical calculators as an alternative to running the gears backwards. For example:
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:
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.