Jan 29 2017

The Method of Complements

Binary NumbersAbraham Lincoln once famously said, “Everybody loves a compliment.”  I suspect that if he had been a mathematician he would have loved complements, too. We’ve already seen what complements are and talked about the two most prolific: the radix complement and the diminished radix complement. Now it’s time to explore how we can leverage complements to do some really interesting integer arithmetic. Using complements we can subtract one positive integer from another or add a negative integer to a positive one by simply performing addition with two positive integers. The algorithm behind this black magic is called the Method of Complements.

The Method of Complements, it turns out, is a slight misnomer. It really should be called the Methods of Complements since there are two different ways we can use complements to achieve the same goal.

Method 1

Supposed we have two positive n-digit, radix b integers x and y, and we would like to subtract y from x. If we actually want to do subtraction, the answer is straightforward, simply calculate x – y. As I stated above, however, the method of complements allows us to calculate the same answer using addition alone.

First, we calculate the diminished radix complement of x:

    \[b^n - 1 - x\]

Now, instead of subtracting y from x, add y to the diminished radix complement of x:

    \[(b^n - 1 - x) + y\]

Using the the associative property of addition and subtraction we can rearrange our parenthesis:

    \[b^n - 1 - x + y\]

    \[b^n - 1 - (x -y)\]

In this form, we now have the diminished radix complement of the value we trying to solve for: x – y.

One important issue I haven’t mentioned previously about complements is the fact that taking a compliment or diminished radix compliment of a number is an involutory function, a function that is in an inverse of itself.  Put another way the radix compliment of the radix compliment of a number x is x itself.

So, if b^n - 1 - (x -y) is the diminished radix complement of x - y, then to find the value of x - y, we need to calculate the diminished radix complement of b^n - 1 - (x - y).

To summarize: in order to calculate the difference x - y using this method:

  1. Calculate the diminished radix complement of x.
  2. Add the diminished radix complement of x to y.
  3. Calculate the diminished radix complement of the sum from #2.

Method 2

Again, we have two positive n-digit, radix b integers x and y, and we want to calculate the difference x - y. This time, we first calculate the radix complement of y:

    \[b^n - y\]

Next add the radix complement of y to x:

    \[x + b^n - y\]

We can rearrange this to resemble the value we are looking to solve for:

    \[x - y + b^n\]

So we see this is our difference, x - y, plus b^n. It is actually very easy to solve this for x - y if we think about the value of b^n and how it relates to x, y, and their difference.

As initially stated, x and y are n-digit numbers with radix b. For such an n-digit number, the place values from left to right are: b^{n-1}, b^{n-2}, b^{n-3}, \ldots, b^2, b, 1. b^n, therefore, is one more than the largest number that can be represented by an n-digit number. Because of this, b^n is a 1 followed by n 0s – regardless of the radix, the smallest (n + 1)-digit number. This is important.

Back to x and y. x and y are both positive, n-digit numbers. Assuming that y \leq x, and since y is positive, the difference x - y has to be at most an n-digit number. Even it’s got fewer digits, we can consider it an n-digit number by adding leading 0s.

If we add b^n to this difference, ala x - y + b^n, what we get is an (n + 1)-digit number where the first digit is 1 and the remaining n digits are the value of the difference x - y. Remember, b^n is n + 1 digits beginning with a 1 followed by n 0s.  Adding the n-digit value of x - y to the first n digits of b^n, 0s, just gives us x -y again.

So, to extract the value of x - y from the value of x - y + b^n all you need to do is drop the leading 1 from your solution. It is that simple.

Looking at these steps without the exposition reveals that this method is not nearly as confusing as it seems. To calculate the value of x - y using Method 2:

  1. Calculate the radix complement of y.
  2. Add the radix complement of y to x.
  3. Drop the leading 1 and any leading 0s from the result.

Since we know the easy method for calculating the radix complement, the steps above should really be written:

  1. Calculate the diminished radix complement of y and add 1.
  2. Add the radix complement of y to x.
  3. Drop the leading 1 and any leading 0s from the result.

Decimal Example

Lets’s look at the decimal subtraction problem 737 - 234 using both methods.

Method 1

We first calculate the diminished radix complement of the minuend, 737, by subtracting each digit from 9, ie., b - 1 to get 262.

Next, add the diminished radix complement of the minuend, 262, to the subtrahend, 234:

\begin{tabular}{ccccc} & 2 & 6 & 2 & \text{(diminished radix complement of 737)}\\ + & 2 & 3 & 4 & \\ \cline{2-4} & 4 & 9 & 6 & \\ \end{tabular}

Calculate the diminished radix complement of the sum, 496, to get the answer to the original subtraction problem, 503.

Method 2

First calculate the radix complement of the subtrahend, 234. The diminshed radix complement is calculated by subtracting each digit of 234 from 9 and is found to be 765. Add 1 to the dimished radix complement to find the radix complement, 766.

Next, add the radix complement of the subtrahend, 766, to the minuend, 737:

\begin{tabular}{cccccc} & & 7 & 3 & 7 &\\ + & & 7 & 6 & 6 & \text{(radix complement of 234)}\\ \cline{2-5} & 1 & 5 & 0 & 3 &\\ \end{tabular}

Drop the leading 1 from this sum to get the answer to original subtraction problem, 503.

Leading Zeros

Leading zeros can come into play in one of two places: one of which requires adding them while the other requires dropping them.

Scenario 1

If you are using method 2, and the subtrahend has fewer digits than the minuend, assuming you are calculating the radix complement via the diminished radix complement, then you need to right pad the subtrahend with 0s so that it has the same number of digits as the minuend before calculating the diminished radix complement.

Consider 1221 - 92:

\begin{tabular}{ccccc} & 1 & 2 & 2 & 1\\ - & & & 9 & 2\\ \cline{2-5} \end{tabular}

Before we can find the diminished radix complement of the subtrahend 92 we need to right pad it with two 0s so that it is four digits like the the minuend 1221. The diminished radix complement of 0092 is 9907 to which we add 1 to get the radix complement 9908. Now we can proceed with our addition:

\begin{tabular}{cccccc} & & 1 & 2 & 2 & 1\\ - & & 9 & 9 & 0 & 8\\ \cline{2-6} & 1 & 1 & 1 & 2 & 9\\ \end{tabular}

Drop the leading 1 from the sum, and 1129 is the answer to the subtraction problem 1221 - 92.

Note that if you are finding the radix complement of the subtrahend 92 the hard way, by calculating 10^4 - 92, then you don’t need to bother with leading 0s.

Scenario 2

The other place where leading zeros are an issue, regardless of the method you choose, are in the sum. Using the first method, it is possible that when you calculate the dimished radix complement of the sum that you end up with leading 0s. What do with them? Drop them. The same goes for the sum you get using method 2. We are already dropping the leading 1 as per the method, but the same goes for any 0s following the leading one. Drop them, too.

Consider calculating the difference 138 - 131 using method 1. First we calculate the diminished radix complement for the minuend 138, which turns out to be 861. Then we add that value to our subtrahend 131:

\begin{tabular}{cccc} & 8 & 6 & 1\\ + & 1 & 3 & 1\\ \cline{2-4} & 9 & 9 & 2\\ \end{tabular}

The diminished radix complement of the sum, 992, is 007. (Cool, but that wasn’t on purpose.) Drop the leading 0s, and 7 is the answer.

Binary Example

The method of complements is a natural fit for working with binary numbers, and is ultimately responsible for why the twos complement representation is the representation of choice for binary signed integers.

In my post about the ones complement representation, I showed, but did not go into the detail that I do here, how easy it is to calculate the ones complement, or diminished radix complement of a binary number. All you need to do is flip every bit in your number. 1s become 0s and 0s become 1s. If you want the twos complement, or radix complement, just add 1 to this value.

Let’s look at the subtraction problem 10101101 - 01011111 (173 - 95).

Method 1

First we need to calculate the ones complement of the minuend, 10101101. To do this, we just flip its individual bits and get 01010010. Now we add the ones complement of the minuend to the subtrahend:

\begin{tabular}{ccccccccc} & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0\\ + & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1\\ \cline{2-9} & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1\\ \end{tabular}

The ones complement of our sum, 10110001, will be our difference. Flipping the bits gives us 01001110, or 78_{10}, the correct answer.

Method 2

The first step using this method is to calculate the twos complement of the subtrahend, 01011111. First we calculate the ones complement by flipping the bits to get 10100000. To that we add 1 to get the twos complement 10100001.

Now we add our minuend to the twos complement:

\begin{tabular}{cccccccccc} & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1\\ + & & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1\\ \cline{2-10} & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0\\ \end{tabular}

Dropping the leading 1 (and subsequent 0 if you are so inclined) gives us our answer 01001110.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.