Method of Complements

Posted by Jared Kipe on 25 October 2011 at 10:22am | 0 Comments

Tags: subtraction, algorithm

or subtraction using addition

Most people would agree that subtraction is more difficult, time consuming, and error prone than addition.

There is a way to complete a long subtraction problem using addition and the complement of the subtrahend (the number being subtracted).

9's Complement

9's complement is simply the number you would need to add to digit x to make that digit 9.  For numbers using more than 1 digit, you apply the complement to each digit.

8722 => 1277
9215 => 0784

Subtraction using 9's Complement

As you might have guessed, subtraction involves the addition of this 9's complement.

  9111
- 8722

 

  9111
+1277
10388

This can't be right, this is in fact bigger than the original numbers. Well there are two more simple rules to apply this algorithm correctly. Drop the left most digit completely, and add 1 to the answer.

0389 is in fact the correct answer. (I left the preceding 0 in place just to remind you what the left most digit was.)

This problem is a best case scenario as we replaced a subtraction problem that would have 3 'borrows' with an addition problem with 0 'carries'.

10's Complement

That business about adding the 1 at the end can, and should, be rolled into the complement itself, and leads to some simplification of the rules for finding the complement.  You can leave all the rightmost zeroes zero, and just add 1 to the rightmost non-zero digit after finding the 9's complement.

259000 =(via 9's)> 741999

See if you add 1 to that, all the 9's become 0's again.

259000 =(via 10's)> 742000

What about the "drop the leftmost 1 (digit)" part?

That part is central to the Method of Complements, and is part of what makes it so great when using fixed number of digits to do calculations (remember the bit lengths of the integer numbers in the Primitive Data Types?) The minuend and subtrahend need to have the same number of digits, thus any difference needs to be padded with extra 0's before finding the complement.

920-70 => 920-070 => 920+930 = 850

Here we did fixed-3-digit addition/subtraction where the extra thousands place digit overflows or dissapears.

In my next entry I will expand on this, specifically for digital computers.