teaching machines

CS 352 Lecture 11 – Subtracting

September 30, 2016 by Chris Johnson. Filed under cs352, fall 2016, lectures.

Dear students,

We have built a large chunk of the core arithmetic and logic hardware inside a computer. We have built AND, OR, NOT, and other boolean gates. We have built an adder. We’ve also designed some components for selecting out bytes from RAM. Things are coming together! One thing that we are not able to do yet is subtract numbers. As much as I’d like a bank whose computers can’t subtract, I don’t think they’d be in business very long. Let’s get subtraction working today.

Instead of operating in the less familiar world of binary, we’ll do our thinking in decimal. Our first attempt at making subtraction work will be by recasting it as addition of the nines complement, which can be computed without any carries. For three digit decimal numbers, the nines complement treatment turns the expression a - b into the equivalent expression a + (999 - b) + 1 - 1000.

Try determining the difference for these values of a and b:

• a = 602, b = 491
• a = 563, b = 199

Now let’s try doing this same operation with 7-digit binary numbers. Instead of using 999, we’ll use 1111111. Convert these to binary, and then compute the difference using the ones complement:

• a = 73, b = 59

What operation computes the ones complement of a binary number?

We didn’t really get rid of subtractions by introducing the nines complement. In fact, we removed one but added two! However, we have still gained something if those subtractions don’t incur any carries. But do they? We will prove that they do not—sometimes. Sadly, our proof only stands when a >= b. What happens with this expression?

• a = 22, b = 54

So, the trick to getting subtraction to work isn’t the nines (or ones) complement. But the ideas we just encountered will come into play in our working solution.

We start by introducing negative numbers into our numeric range. But instead of introducing a new symbol into our alphabet to represent negative, we will actually hijack a span of the positive numbers. For example, we can represent values in [-5, 4] in the following way:

The way we split this range was no accident. The values form a cycle, and we can lay them out in a ring. Adding one shifts us clockwise. Subtracting one shifts us counterclockwise.

Suppose we’re sitting at 2. What happens when we add 10? What happens when we subtract 10? Nothing, on both accounts. We just wheel around right back to the 2. What does this mean for us? It means that the pesky second subtraction from the nines complement expression has absolutely no effect here. It won’t introduce a carry because we can eliminate it altogether!

So, here’s our new way to calculate a - b for 1-digit decimal numbers:

• a - b
• a - b + 10 - 10 (effectively adds 0)
• a - b + 10 (removes the second subtraction, which does nothing)
• a - b + 9 + 1 (decomposes 10)
• a + (9 - b) + 1 (commutes and reassociates)

The remaining subtraction needs to stay, but it won’t carry because the minuend is as large as possible. b can’t be larger.

(9 - b) + 1 is called the tens complement, which is the nines complement plus one. It is our means of performing subtraction, but it comes at the cost of forcing our numbers into a cycle and therefore being subject to wraparound.

Let’s try this out on some binary numbers in various ranges:

• a = 5, b = 8 (4-bits)
• a = 120, b = 127 (8-bits)

The takeaway from all this is that when we want to compute a - b, we recast it as a + nComplement(b), where:

def nComplement x
  max - x + 1

This works because the way we’ve mapped our numbers, the ns complement of a number works out to be the negation. Let’s verify this.

In binary, computing the twos complement of a number x means 1111...1111 - x + 1. The subtraction can just be computed as negation, so we really just have ~x + 1.

See you next class!

Sincerely,

P.S. It’s Haiku Friday!

My life is machines
I was not surprised to learn
I do less with more