Method of complements

Last updated
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. 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 to encode a symmetric range of positive and negative integers in a way that they can use the same algorithm (or mechanism) 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.

Contents

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 leftmost digit '1' of the result is then discarded. Discarding the leftmost '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 tens' 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 overflow in calculation. [1]

Numeric complements

The radix complement of an -digit number in radix is defined as . In practice, the radix complement is more easily obtained by adding 1 to the diminished radix complement, which is . While this seems equally difficult to calculate as the radix complement, it is actually simpler since is simply the digit repeated times. This is because (see also Geometric series Formula). Knowing this, the diminished radix complement of a number can be found by complementing each digit with respect to , i.e. subtracting each digit in from .

The subtraction of from using diminished radix complements may be performed as follows. Add the diminished radix complement of to to obtain or equivalently , which is the diminished radix complement of . Further taking the diminished radix complement of results in the desired answer of .

Alternatively using the radix complement, may be obtained by adding the radix complement of to to obtain or . Assuming , the result will be greater or equal to and dropping the leading from the result is the same as subtracting , making the result or just , 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

DigitNines'
complement
09
18
27
36
45
54
63
72
81
90

The nines' complement of a decimal digit is the number that must be added to it to produce 9; the nines' complement of 3 is 6, the nines' 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

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  [nines' complement of 344 = 999 - (999 - x + y) = x - y, the correct answer]

Second method

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 and the nines' complement of 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  [-(999 + 1) + 999 + x - y]

This is not yet correct. In the first step, 999 was added to the equation. Then 1000 was subtracted when the leading 1 was dropped. So, the answer obtained (654) is one less than the correct answer . To fix this, 1 is added to the answer:

  654 +   1 —————   655  [x - y]

Adding a 1 gives 655, the correct answer to our original subtraction problem. The last step of adding 1 could be skipped if instead the ten's complement of y was used in the first step.

Magnitude of numbers

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

  123410  [x, the minuend] - 123401  [y, the subtrahend]

Using the first method the sum of the nines' complement of and 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, , has fewer digits than the minuend, , 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

Binary
digit
Ones'
complement
01
10

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 yx, 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 will be less than . 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 (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

Comptometer from the 1920s, with nines' complements marked on each key 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:

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. [3] Subtraction is done by adding the ten's complement of the subtrahend, which is the nines' complement plus 1. The result of this addition is 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.

See also

Related Research Articles

<span class="mw-page-title-main">Floating-point arithmetic</span> Computer approximation for real numbers

In computing, floating-point arithmetic (FP) is arithmetic that represents subsets of real numbers using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. Numbers of this form are called floating-point numbers. For example, 12.345 is a floating-point number in base ten with five digits of precision:

<span class="mw-page-title-main">Addition</span> Arithmetic operation

Addition is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or sum of those values combined. The example in the adjacent image shows two columns of three apples and two apples each, totaling at five apples. This observation is equivalent to the mathematical expression "3 + 2 = 5".

<span class="mw-page-title-main">Subtraction</span> One of the four basic arithmetic operations

Subtraction is one of the four arithmetic operations along with addition, multiplication and division. Subtraction is an operation that represents removal of objects from a collection. For example, in the adjacent picture, there are 5 − 2 peaches—meaning 5 peaches with 2 taken away, resulting in a total of 3 peaches. Therefore, the difference of 5 and 2 is 3; that is, 5 − 2 = 3. While primarily associated with natural numbers in arithmetic, subtraction can also represent removing or decreasing physical and abstract quantities using different kinds of objects including negative numbers, fractions, irrational numbers, vectors, decimals, functions, and matrices.

A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method for representing numbers that uses only two symbols for the natural numbers: typically "0" (zero) and "1" (one). A binary number may also refer to a rational number that has a finite representation in the binary numeral system, that is, the quotient of an integer by a power of two.

The quater-imaginary numeral system is a numeral system, first proposed by Donald Knuth in 1960. Unlike standard numeral systems, which use an integer as their bases, it uses the imaginary number 2i as its base. It is able to uniquely represent every complex number using only the digits 0, 1, 2, and 3. Numbers less than zero, which are ordinarily represented with a minus sign, are representable as digit strings in quater-imaginary; for example, the number −1 is represented as "103" in quater-imaginary notation.

Two's complement is the most common method of representing signed integers on computers, and more generally, fixed point binary values. Two's complement uses the binary digit with the greatest value as the sign to indicate whether the binary number is positive or negative; when the most significant bit is 1 the number is signed as negative and when the most significant bit is 0 the number is signed as positive. As a result, non-negative numbers are represented as themselves: 6 is 0110, zero is 0000, and -6 is 1010. Note that while the number of binary bits is fixed throughout a computation it is otherwise arbitrary.

Balanced ternary is a ternary numeral system that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the standard (unbalanced) ternary system, in which digits have values 0, 1 and 2. The balanced ternary system can represent all integers without using a separate minus sign; the value of the leading non-zero digit of a number has the sign of the number itself. The balanced ternary system is an example of a non-standard positional numeral system. It was used in some early computers and has also been used to solve balance puzzles.

The IEEE Standard for Floating-Point Arithmetic is a technical standard for floating-point arithmetic originally established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in the diverse floating-point implementations that made them difficult to use reliably and portably. Many hardware floating-point units use the IEEE 754 standard.

<span class="mw-page-title-main">Positional notation</span> Method for representing or encoding numbers

Positional notation usually denotes the extension to any base of the Hindu–Arabic numeral system. More generally, a positional system is a numeral system in which the contribution of a digit to the value of a number is the value of the digit multiplied by a factor determined by the position of the digit. In early numeral systems, such as Roman numerals, a digit has only one value: I means one, X means ten and C a hundred. In modern positional systems, such as the decimal system, the position of the digit means that its value must be multiplied by some value: in 555, the three identical symbols represent five hundreds, five tens, and five units, respectively, due to their different positions in the digit string.

Excess-3, 3-excess or 10-excess-3 binary code, shifted binary or Stibitz code is a self-complementary binary-coded decimal (BCD) code and numeral system. It is a biased representation. Excess-3 code was used on some older computers as well as in cash registers and hand-held portable electronic calculators of the 1970s, among other uses.

<span class="mw-page-title-main">Mental calculation</span> Arithmetical calculations using only the human brain

Mental calculation consists of arithmetical calculations using only the human brain, with no help from any supplies or devices such as a calculator. People may use mental calculation when computing tools are not available, when it is faster than other means of calculation, or even in a competitive context. Mental calculation often involves the use of specific techniques devised for specific types of problems. People with unusually high ability to perform mental calculations are called mental calculators or lightning calculators.

Casting out nines is any of three arithmetical procedures:

In computing, signed number representations are required to encode negative numbers in binary number systems.

A divisibility rule is a shorthand and useful way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits. Although there are divisibility tests for numbers in any radix, or base, and they are all different, this article presents rules and examples only for decimal, or base 10, numbers. Martin Gardner explained and popularized these rules in his September 1962 "Mathematical Games" column in Scientific American.

<span class="mw-page-title-main">Elementary arithmetic</span> Numbers and the basic operations on them

Elementary arithmetic is a branch of mathematics involving addition, subtraction, multiplication, and division. Due to its low level of abstraction, broad range of application, and position as the foundation of all mathematics, elementary arithmetic is generally the first branch of mathematics taught in schools.

In mathematics, 0.999... denotes the smallest number greater than every number in the sequence (0.9, 0.99, 0.999, ...). It can be proved that this number is 1; that is,

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.

In electronics, a subtractor – a digital circuit that performs subtraction of numbers – can be designed using the same approach as that of an adder. The binary subtraction process is summarized below. As with an adder, in the general case of calculations on multi-bit numbers, three bits are involved in performing the subtraction for each bit of the difference: the minuend, subtrahend, and a borrow in from the previous bit order position. The outputs are the difference bit and borrow bit . The subtractor is best understood by considering that the subtrahend and both borrow bits have negative weights, whereas the X and D bits are positive. The operation performed by the subtractor is to rewrite as the sum .

A negative base may be used to construct a non-standard positional numeral system. Like other place-value systems, each position holds multiples of the appropriate power of the system's base; but that base is negative—that is to say, the base b is equal to −r for some natural number r.

As with other spreadsheets, Microsoft Excel works only to limited accuracy because it retains only a certain number of figures to describe numbers. With some exceptions regarding erroneous values, infinities, and denormalized numbers, Excel calculates in double-precision floating-point format from the IEEE 754 specification. Although Excel allows display of up to 30 decimal places, its precision for any specific number is no more than 15 significant figures, and calculations may have an accuracy that is even less due to five issues: round off, truncation, and binary storage, accumulation of the deviations of the operands in calculations, and worst: cancellation at subtractions resp. 'Catastrophic cancellation' at subtraction of values with similar magnitude.

References

  1. Florida Tech
  2. Easy Instructions for Operation the Controlled Key Comptometer, Comptometer Division, Felt and Tarrant Mfg. Co., Chicago, 1917, p. 12
  3. Carl Barnett Allendoerfer (1971). Principles of Arithmetic and Geometry for Elementary School Teachers. Macmillan.