Method of complements
From Wikipedia, the free encyclopedia
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. To subtract a number y (the subtrahend) from another number x (the minuend), the radix complement of y is added to x and the initial '1' of the result is 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 method of complements is now recommended by many educators for use in teaching grade school arithmetic, since it more closely resembles what people actually do. For example, in doing a problem such as 30 - 16, most people think "16 and 4 makes 20 and 10 more makes 30 so the answer is 14", while grade school children are taught the much harder method called "borrowing". In the language of complements, we would say that you begin by adding 4 because 4 is the ten's complement of 6.
While the complements method involves one more step than borrowing, it reuses rote knowledge already learnt for addition whereas to do borrowing efficiently requires learning another set of number pairings like 16-7=14 the unit (7 in this case)borrows 1.
Contents |
[edit] Numeric complements
The radix complement of an n digit number y in radix b is bn − y. Adding this to x results in the value x + bn − y or x − y + bn. Assuming y ≤ x, the result will always be greater than bn and dropping the initial '1' is the same as subtracting bn, making the result x − y + bn − bn or just x − y, the desired result.
The radix complement is most easily obtained by adding 1 to the diminished radix complement, which is (bn − 1) − y. Since (bn − 1) is the digit b − 1 repeated n times, 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). Adding 1 to obtain the radix complement can be done separately, but is most often combined with the addition of x and the complement of y.
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.
[edit] Decimal example
To subtract a decimal number y from another number x using the method of complements, the nines' complement of y is first obtained by determining the complement of each digit. The complement of a decimal digit in the nines' complement system 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. Given a subtraction problem:
873 (x) - 218 (y)
The nines' complement of y (218) is 781. Because y is three digits long, this is the same as subtracting y from 999. (The number of 9's is equal to the number of digits of y.)
Next, the sum of x, the complement of y, and 1 is taken:
873 (x) + 781 (complement of y) + 1 (to get the ten's complement of y) ===== 1655
The first "1" digit is then dropped, giving 655, the correct answer.
If the subtrahend has fewer digits than the minuend, leading zeros must be added which will become leading nines when the nines' complement is taken. For example:
48032 (x) - 391 (y)
becomes the sum:
48032 (x) + 99608 (nines' complement of y) + 1 (to get the ten's complement) ======= 147641
Dropping the "1" gives the answer: 47641
[edit] Binary example
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)
[edit] 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 + bn will be less than bn. For example (in decimal):
185 (x) - 329 (y)
Complementing y and adding gives:
185 (x) + 670 (nines' complement of y) + 1 ===== 856
This is obviously the wrong answer; the expected answer is -144. But it isn't as far off as it seems; 856 happens to be the ten's complement of 144. This issue 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 bn / 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.
[edit] Practical uses
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 results 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 subtrahend (yes, the number being subtracted) was dialed in. The slat was then moved to expose the black digits (which now displayed the nines' complement of the subtrahend) and the minuend was added by dialing it in. Finally, the operator had to mentally add 1 and ignore the leftmost 1 to obtain 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 slides along the sides of the device. When the crank was turned, that number was added to the result counter by cams on the "echelon drum" as it turned. The number of cams encountered by each digit was determined by the value of that digit; for example the row on the drum corresponding to a digit in the "6" position had 6 cams. For subtraction, the crank was lifted before it was turned, moving an alternate set of cams into position containing the nines' complement of the digits. So the input position that had 6 cams for addition now had a row with 3 cams. Also, lifting the crank engaged a mechanism to add an additional 1 to the result as required for the method of complements. The initial 1 was discarded simply by ignoring the carry from the most significant digit.
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 the 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.
[edit] The method of complements in elementary education
In more mathematically advanced grade schools, after the class is taught borrowing, they are sometimes taught the method of complements as a short cut useful in mental arithmetic. For example, they can use this short cut to make change for a dollar.
To teach subtraction by the method of complements, first the class must learn the ten's complement and the nine's complement of each digit. To work a problem such as 1000 - 280, you write the nine's complement of each digit in the subtrahend except the rightmost non-zero digit, for which you write the ten's complement. The answer is thus 720. If you are subtracting a number from 1000 that has fewer than three digits, you add lead 0's to fill the number out to three digits. You can also use the method of complements for a problem such as 83 - 24. Think: "the ten's complement of 4 is 6". Add 6 to both 83 and 24 to get 89 - 30 = 59". These are just two of the many mental math "tricks" that involve the method of complements.
The definition of complements used in computer science has been extended, so that in elementary education we say that the n's complement of k is n - k. Thus, for example, in working with fractions, we can say that the 1's complement of 2/5 is 3/5.
