I don't understand Subtraction via Addition in computing

Factual Questions
1

Please see this MinutePhysics video to see what I am talking about:


And this forum thread on math.stackexchange:

Normally when we do long form subtraction we do it this way (apologies in advance for ugly/disjointed math. I don’t know how to make pretty tables line up) (wow, ps, extra spaces are erased to line up with the left margin, and the chat box is not equal to the eventual message length it is about 2 1/4 chatbox lines to 1 true messageboard post, what a mess it was to preview this and remake it at the end)

1492
1066 _

1 4 8 12
^ ^ ^ ^
1 4 9 2
1 0 6 6 -

(1-1)=0 (4-0)=4 (8-6)=2 (12-6)=6 == 426
Which, as I see it, is a piecemeal version of how subtraction by adding does it. To quote MinutePhysics 0:15-0:38 “first we just need to replace each digit of the smaller number with 9 minus that digit, except the final digit gets replaced by 10 minus that digit. So 1066 becomes 9-1 (8) 9-0 (9) 9-6 (3) 10-6 (4). Adding that to 1492 (8934+1492) equals 10426, and if we ignore the first digit we get the answer (X0426=426)”

Great, but if I am told that I can subtract by adding, or that an adding machine can only subtract via this method, then how come there exist all these interim states that require subtraction in and of themselves? (9-n for every place in the smaller # until 10-n) How do the adding machines do those smaller subtracting steps? Is there a “true” subtraction by addition that never, in any of it’s smaller steps, does subtraction? Is there also a division by multiplication? How would an adding machine tackle division or any other form of math that we would not really think about? Because so far this machine way of doing math is easier than how we are taught in school. I wonder how far that goes.

But isn’t subtraction just the “difference” between two numbers? If I or a computer wants to know 100-42 we could brute force “count down” from 100 to 42 and note how many numbers are in between them, or we could count up from 42 to 100, or we could use shorter hand mathematics tricks on the 10’s and 100’s place of borrowing and remainders and junk. But at the end of the day isn’t all of that subtraction? Just finding the amount of numbers in between two other numbers, no matter how it is done?

Why can’t an adding machine do math the way we do with pencil and paper? I see that the machine way is faster and easier, I will use that subtraction by addition method myself whenever I can, but perhaps I am just hung up on semantics. If someone says that a device can’t subtract, to me that says that it cannot find the “difference” between numbers.

Sorry for my rambling and disjointed paragraphs. Thank you in advance for your time and help.

(is there any way that this forum could have an innate spellcheck inside its chat message box? A good number of places already do that. Is importing the code easy or too hard or what?

2

For modern digital computers doing the equivalent of “9-n” is very easy. Because they work in binary, it is really “1-x”, and for a single bit x, “1-x” is just “not x”.

For an analog adding machine that works in decimal, the values of “9-n” can just be tabulated: 9->0, 8->1, 7->2, … , 1->8, 0->9.

Yes, in some cases. But you have to replace the “forget about the last digit” step with “take the remainder after division by p, where p is some fixed prime larger than any of the numbers we are concerned about”. It is not as practical for day to day division on computers, but it is important for cryptography.

Yes. The technique in the video is just a way to do it that is efficient for computers and analogue adding machines since they don’t need separate circuits/gears for subtraction.

3

So, the real reason is complicated and comes down to the way that computers actually represent numbers internally. You see, at the electronic level, computers don’t deal with numbers like “4” or “7”. Instead, they deal in discrete electronic states: either electrical current is flowing or not flowing. If it’s not flowing, that’s a 0. If it is flowing, that’s a 1.

So, with only 0s and 1s to deal with, how does a computer represent a larger number? To answer that, you need to understand how numbers as you understand them are represented. We humans are use a number system that only has symbols for the numbers 0 through 9, and yet we can represent any finite number with them. Compare that to say, roman numerals, where that’s not really possible. How do you write the number 6,000,000? Write 6,000 Ms?

The key trick is the use of positional notation in numbers – the position of a digit relative to others is significant. So when I write 379, you know that’s 3 * 100 + 7 * 10 + 9 * 1. Only, that’s actually a circular definition, as you need to know how to interpret the number “100” to know the value of 379. Let’s write that in another, equivalent way: 3 * 10[sup]2[/sup] + 7 * 10[sup]1[/sup] + 9 * 10[sup]0[/sup]. Now, I still have to define “10” as the integer coming after 9, and give the definition of the exponentiation function. Once I’ve done that, I’ve now taught you how to interpret any number (well, I haven’t explained decimals, but that’s not really relevant).

Now here’s the interesting thing. Why does 10 show up everywhere in the definitions? There are 10 digits from 0-9, and numbers are all defined in terms of powers of 10. Suspiciously, humans have 10 fingers, and they make for useful things for counting on. What if we didn’t have 10 fingers? What if we only had, say, 8?

Well, we’d have the digits 0-7 still. After the last digit (7 now), we get the number 10. “Well, this is a silly system,” you’re probably tempted to say. “We can count to 10 but we can’t count to 8 or 9.” Ah, but now we’re living in this crazy 8-based world, so let’s denote the number a little bit differently to indicate that. Let’s write it as 10[sub]8[/sub], which is read as 10 (base 8). 10[sub]8[/sub] means 1 * 8[sup]1[/sup] + 0 * 8[sup]0[/sup], which is 8. Turns out we can count to 8. And if we want to count to ten? Well, 12[sub]8[/sub] =1 * 8[sup]1[/sup] + 0 * 8[sup]0[/sup] = 10. Take the number 573[sub]8[/sub]. That works out to 5 * 8[sup]2[/sup] + 7 * 8[sup]1[/sup] + 3 * 8[sup]0[/sup], and if you do the math, it works out to 379. As it turns out, any integer that you can represent with our base 10 system, you can represent in base 8. Or in almost any other integer base (base 1 and base 0 don’t really work very well).

Now, let’s get back to the computer. It only knows about the numbers 0 and 1. So now let’s look at base two. 10[sub]2[/sub] = 2.

101111011[sub]2[/sub] = 1 * 2[sup]8[/sup] + 0 * 2[sup]7[/sup] + 1 * 2[sup]6[/sup] + 1 * 2[sup]5[/sup] + 1 * 2[sup]4[/sup] + 1 * 2[sup]3[/sup] + 0 * 2[sup]2[/sup] + 1 * 2[sup]1[/sup] + 1 * 2[sup]0[/sup] = 256 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 379.

As you can see, base two makes for much longer numbers. The important thing is that we have a system that can translate electrical “on” and “off” signals into numbers. Adding them is a lot easier, too. To add base 10 numbers you have to memorize that 5 + 7 = 12 and 1 + 6 = 7 and a hundred other combinations. The addition table for base 2 is has just four combinations to memorized:



+ |  0 |  1 |
-------------
0 |  0 |  1 |
1 |  1 | 10 |

Now, what about negative numbers? To do a negative number in base 10, we just stick a - sign in front. But the computer just has 0s and 1s to work with. You could decide that the first digit of an integer would be special, and represent the minus sign. So 00100[sub]2[/sub] would be +4 but 10100[sub]2[/sub] would mean -4. This works, but it makes both adding a subtracting numbers a painful chore. The addition table I showed above gets much larger, as you have to deal with cases where both numbers are positive, both are negative, the first is positive and the second positive, or the first is negative and the second is positive. The logic for adding two digits basically gets 4 times bigger.

Eventually, somebody came up with a clever way of representing negative numbers in such a way that the exact same addition table works for both positive and negative numbers. That’s the twos-complement system those links are describe. The key thing, as leahcim mentions, is that in base 2, instead of performing a 9-d calculation, you just reverse all of the digits so that 0s become 1s and 1s become 0s. That’s a very simple operation for a computer do.

4

dp.

5

I’m only a hobbyist, but basically, it has to do with the simplicity of the circuitry. To subtract in binary (or any other number system, but we’re talking computers here), you can just flip the bits of the subtractor (use a NOT gate, for instance), add one to it, and then just put it through your normal adder circuit. No fuss, no muss.

So, for example, 15-3 in binary is 1111 - 0011. Flip the bits of the subtractor (0011) and you get 1100. Add/increment it by 1: 1101. Now you can add 1111 + 1101 and ignore the carry bit:



1111
1101
-----
1100 (with carry flag set/ignored)

That works out to 12 in base 10, which is the correct answer for 15 -3.

6

Okay, now that we’re getting into the nitty-gritty of binary addition/subtraction, I have a question:

What are the advantages / disadvantages of two’s-complement arithmetic, versus one’s-complement?

My first exposure to a binary-arithmetic computer was the Control Data CDC-6400, in 1969. (Previously, I learned programming on an IBM-1620, which used decimal(ish) arithmetic.) The 6400 had a 60-bit word size, with integers recorded in one’s-complement. For positive integers, that’s the same as two’s-complement, but for negative integers, it’s slightly different: You complement all the bits and then don’t add one.

Addition and subtraction are almost the same, except: You add the numbers and then if there is a carry out of the high-order bit (the sign bit), you add that back in at the unit’s position. For subtraction, you just complement the subtrahend (as described just above) and add.

This system has a peculiar quirk that there are two zeros: Positive zero and negative zero (all one bits). This doesn’t seem to create any great problems with the arithmetic, overall. When doing arithmetic with this operand, it doesn’t affect the results (much). It’s a minor quirk, and requires only some minor specific programming steps to deal with it correctly (so, at the minimum, an assembly-language programmer has to know about it at least).

So my question is: Why did two’s-complement become the dominant standard in modern computers, while one’s-complement seems to have been relegated to the dustbin of computer history?

7

[hijack] I once programmed a square root function in assembly and made an interesting discovery. Some of you may recall learning to do it by hand in 8th grade. It was a mess. You tried a trial digit, multiplied it by the twice something (I have now forgotten it) until you got a digit that was definitely too large, then backed off by one. Well in binary there is only trial bit that need be tried: 1. If that is too large, then the next bit is 0. Repeat. The procedure is simplicity itself and very fast. Much faster than Newton approximation, at least using the very slow division on an 8088 chip (which is what I was doing it on more than 30 years ago).[/hijack]

I think the moral of this story is that when using binary you have to rethink your algorithms that were previously optimized for decimal.

8

Because it is a minor quirk, and it has to be dealt with every single time you do integer arithmetic, which is the very heart of the core of what CPU designers and low-level programmers want to make fast.

Fast floating-point is nice, but the OS itself doesn’t need FP. A good number of applications can get by with no FP, or with every single FP instruction faulting so the OS can emulate it in software. However, literally every single piece of code run on the CPU needs fast integer math, and special cases are the enemy of speed. It takes either extra hardware or extra software, both of which can fail and both of which are necessarily right in the fast path, where every clock cycle is at a premium.

Now that we can do twos-complement in hardware without any problems, we can ditch all of the special-casing stuff needed with ones-complement and just use the fastest possible twos-complement hardware everywhere.

9

The 8085 didn’t have multiply or divide instructions. I had to code those myself when I needed them.

The 8086/8088 had multiply and divide instructions, but the ALU couldn’t multiply or divide. Instead, what it did was break down multiply or divide instructions into loops of adds and shifts for multiply, or subtracts and shifts for divide (look up Booth’s algorithm if you want the gory details). While it was nice to actually have the instructions available, having the ALU sit there and loop really sucked up the clock cycles. It’s easy to see why your bit banging algorithm was so much faster than anything using a divide.

With two registers, a 2’s compliment circuit on one of the registers, a shift register, and a simple adder circuit, you can do a whole lot of math without a whole lot of logic gates. Since your adder circuit already contains AND and OR gates, you can be a bit creative with those circuits and end up with a bunch of logic in there too. Add in a few other registers and some control logic, and you’ve got a simple processor.

10

Maybe it would help to describe what “two’s compliment” actually does, using base 10 numbers.

Let’s say you have 7453 - 5321. To do a “ten’s compliment” you would subtract each digit from 9, and then add 1. So 5321 becomes 4678 + 1 = 4679. You add the two numbers, you get 12132. Chop off the 1, and you get 2132, which is also 7453 - 5321. Well, what number is four 9s? 9999. and you added 1. So you get 10000. But, then, at the end, you take away 10000.

So what you actually did was 7453 + (10000 - 5321) - 10000. Cancel out the 10000s, and you get 7432 - 5321.

Well, that’s the same concept in binary. Let’s use 11011 - 10010. You take 10010 and subtract each digit from 1. So you get 01101. Then you add 1, and get 01110. So you add 11011 + 01110 = 101001. Then you drop the 1, which makes it 01001 as your answer, which is also what you get if you just subtract the initial numbers. What is a number with all 1s for this? 11111. And you added 1 after subtracting from it, so you are actually subtractive from 100000. So what you actually did was 11011 + (100000 - 10010) - 100000. The 100000s cancel out, so it’s the same thing as 11011 - 10010.

Or, to put it algebraically, what you are doing in base 10 is
x + (9999 - y + 1) - 10000 = x + 10000 - y - 10000 = x - y.

And what you are doing in base 2 is
x + (11111 - y + 1) - 100000 = x + 100000 - y - 100000 = x - y

And, of course, you can do this with any number of digits. The number you add and then take away just gets bigger.

Edit: and, luckily, subtracting from 11111… in binary is really easy. It’s just the same thing as flipping every bit in the other number. That’s because there are only two options for any digit.

11

To add (heh!) to what Derleth just said, because two’s complement is simple and elegant. A great example is the 12-bit PDP-8 which had a total of 8 opcodes, of which 6 were memory reference instructions, one was an opcode for I/O, and one was an opcode for a “microprogrammed” class of instructions that did operations on the accumulator register. The point here being that this computer had just one arithmetic instruction, TAD, meaning two’s complement add the referenced memory location to the accumulator.

This one instruction accomplished all the machine’s arithmetic. If you wanted to subtract a number, you put the number into the accumulator and did a microprogram class instruction CMA IAC on it, which means “complement AC and increment”. This by definition makes the number negative, so a subsequent TAD is a subtraction.

Everything else – multiplication, division, and floating point if you needed it – was built up from this foundation with software subroutines. If you had the money you buy an Extended Arithmetic Element that gave you hardware multiply and divide instructions, and in later years you could even buy a Floating Point Processor. To put it in perspective, the FPP was an entire cabinet about the size of a refrigerator and cost tens of thousands of dollars, somewhere in the ballpark of maybe $100K today. The moral of the story, besides a bit of historical background, is that kids today are spoiled! :wink:

12

And, in case it isn’t obvious, subtracting 10000… when the number starts with 1 is just as simple as chopping off that digit, no matter what base you are in. So that’s really easy, too. Just don’t carry that last 1.

13

At this point, it should be mentioned that the PDP-8 was a budget system, with the base system originally selling for $18,500 in 1965, and was really cheap for its era; it helped usher in the age of the minicomputer, computer systems small companies and individual departments of larger companies could afford, to computerize tasks which previously would have been done by hand or not done at all. In fact, ruggedized PDP-8s were used as embedded systems, with BART (Bay Area Rapid Transit) famously keeping theirs in operation far longer than they were in production. (Fairly unremarkable for deeply embedded systems, I suppose, but an interesting fact nonetheless.) According to this, they were used for station signage, and were all gone by the early 2000s, replaced by x86 systems. The low end marches ever upwards.

Point is, other computers from the same time and before weren’t as gloriously weird as the PDP-8. They had more opcodes and more convenient ISAs. They also didn’t allow their manufacturers to rack up more than 50,000 sales, which was a record for the time.

Question: You’re designing a CPU built around the conceit that pipelining is good and pipeline stalls are bad. You’ve already swallowed the idea of the architectural delay slot, but you want to have integer multiply and divide in your ISA, despite the fact there’s no single-cycle algorithm for them in the general case. (Divide-by-two and multiply-by-two are not quite good enough.) How do you do it?

If you’re the design team for the original MIPS, you add two special registers, hi and lo, and specify that the multiply and divide opcodes will work in tandem with the normal pipeline and return their results in those two registers, such that code can issue a multiply opcode (for example) and the CPU will keep executing other opcodes while the multiplication logic is chugging along; hi and lo will be filled in when they’re ready. Trying to read them before the multiplication unit’s done will (horror of horrors) stall the pipeline, so compiler-writers are encouraged to program compilers to schedule accordingly. Or throw in a bunch of nops, that works too.

14

One’s complement is also simple and elegant; I’m not sure the reasons for predominance of 2’s complement are clearcut.

With 1’s complement, the boolean complement and arithmetic complement are identical! Also, you avoid the annoyance that the most negative number has no complement. (If -128 is the most negative number, you’d want to get +128 when you subtract it from zero — instead you get -128, an anomaly which doesn’t arise with 1’s complement.)

A main difference is that 1’s complement adders need to have end-around carry. However this needn’t actually slow down the adder — the carry rippling is done with combinatorial circuits whose delay is limited to N stages anyway. (If the end-around carry propagates, that implies the first carries did not.)

Finally, the bugaboo of having two different zero representations is avoided the way (“complement-recomplement”) arithmetic is actually implemented on the CDC6600. On that machine it is actually impossible to get a negative-zero sum unless both of the inputs were negative zero — if there’s no negative zero in any of the registers, you’ll need a non-arithmetic instruction just to generate one in the first place! (Nevertheless the machine’s test-for-zero logic did check for both forms of zero.)

15

This, mostly. The integer logic in the CDC 6000-series assured that a zero result was hardly ever a negative zero. That could happen only if you added (-0) + (-0). There were a few other obscure possibilities, IIRC. The “minor quirk” I mentioned above was in the branch instruction to test for a positive or negative number. In computers, 0 is a positive number, and a branch instruction to distinguish a positive number from a negative number will treat 0 as a positive. But in the CDC-6000’s, the Branch Positive and Branch Negative instructions would treat +0 as a positive and -0 as a negative! Logical, but definitely not what the programmer probably wants.

The usual solution was to start with a Branch Zero (or Non-Zero) instruction, which would catch +0 and -0 alike, followed by a Branch Zero/Nonzero instruction. The various high-level language compilers all knew to produce code like that. Assembly-language programmers needed to know that, as well as knowing the very limited cases where a -0 would ever occur in the first place.

I don’t know that this is really enough of a reason why one’s-complement should have become so disfavored.

16

Here’s a simple way to think of it: In base 10, if you take a number that ends in a bunch of zeroes, and you subtract 1 from it, what do you get? A number that ends in a bunch of 9s, right? Like, 100 - 1 = 99, and 10000 - 1 = 9999, and 10000000000 - 1 = 9999999999, and so on.

But what’s 000000000000 - 1? In the usual notation system we use, that’s -00000000001. But where are all the 9s? If we have a bunch of zeroes and subtract 1, shouldn’t we end up with a bunch of 9s?

I’m not sure that’s a big deal, really: Whenever you’re in the close vicinity of the largest integer you can represent or the smallest integer you can represent, you’re always going to get weird behavior of some sort or another. As a programmer, you should expect that and plan for it, and if you don’t, it’s going to bite you in the butt, no matter what number system you’re using.

17

Yeah- in my assembly course (IBM 360 assembly) it was ALL integer stuff even down to the point where you’re dealing with memory addresses, etc… while floating-point only came into play when the actual application called for it.

TL;DR- actually dealing with things (reading from memory, writing to memory, etc…) requires integer math, while floating point is something that’s more or less explicitly necessary for application reasons.

18

True, although unlike machines like the PDP-14, the PDP-8 was never conceived of as an embedded system and that only came later, in limited ways, when it became small and cheap enough. The PDP-8 was indeed designed for low cost, but it was also designed as a full-function general-purpose computer for lab, departmental, and later school computing. Many PDP-8s were configured in mainframe-sized cabinets like this and this so that peripherals like disk drives, DECtapes and full-fledged magnetic tape drives, the FPP, line printer controllers, etc. could be added. PDP-8s could run a PDP-10-like single-user operating system called OS/8 and a full-featured FORTRAN IV compiler. You could even run a limited kind of timesharing on it via TSS-8. It was not only a real computer in every sense, it could actually form the basis of a small departmental computing center.

So to call the PDP-8 (and its single arithmetic instruction, TAD) “gloriously weird” is misleading and, in view of its rather elegantly simple architecture, something akin to blasphemy! :wink: The ubiquitous PDP-11 that came later, for instance, might be considered elegant in many ways but in other ways strikes one as complex and powerful rather than possessing the Zen-like quality of the PDP-8. Its opcode and operand fields vary all over the place, everything is byte-addressable except for stuff that isn’t, instructions might be 16, 32, or 48 bits long (reflected in a messy-looking assembler listing), etc. The PDP-8 was a shining example of how much could be done with so little. Then Intel and Bill Gates came along and now I have computers with 250,000 times more memory than the PDP-8 that choke because they don’t have enough memory when all I’m trying to do is check the weather forecast. :mad:

I don’t think there’s any overwhelming reason beyond the points already stated. To many hardware designers, two’s complement just seemed cleaner.

19

By most people’s standards, two’s complement has significantly nicer mathematical properties than one’s complement; I don’t think it’s just historical accident that it won. Among those not already mentioned:

(a) Just as unsigned numbers are fully described by place value (the low bit is worth 2^0 = 1, the next is worth 2^1 = 2, then 2^2 = 4, then 2^3 = 8, then …), two’s complement numbers are as well. The only difference is that in a k-bit signed value, the high bit has place value -2^(k-1), not +2^(k-1).

(b) Consider a k-bit field. Let u equal the field’s value as an unsigned integer, and s equal the field’s value as a two’s complement signed integer. Then u = s (mod 2^k).

I think (b) is the best explanation of why two’s complement is important. Basically, it means that any operation that can be treated as an operation on integers modulo 2^k will be identical (and can used identical hardware) for signed and unsigned numbers. Only two’s complement has this property.

20

Nitpick: The Romans weren’t that constrained. One million in Roman numerals is (M-bar) My font won’t represent it but it’s an M with a bar over it, a bar multiplies the numeral beneath it by 1000 so 6000000 is simpy six M-bars.