I don't understand Subtraction via Addition in computing

Factual Questions
21

Aha! Of all the reasons given in the thread for 2’s-complement superiority, this is the one that makes excellent sense to me. In particular it makes it easy to implement, for example, 64-bit arithmetic on a 32-bit machine. (You use a carry flag which, BTW, CDC6600 did not have.) IIRC, such chained arithmetic was seldom done on the CDC6600. (There was a double-precision multiply, but I don’t even remember the details.)

Other than CDC’s historic machine and its close relatives, what other computers have used 1’s complement?

ETA: With 1’s comp, u = s (mod 2^k - 1), for signed/unsigned “equivalence”, so that may not be key. It’s the ability to chain additions together which is often a big win.

22

There’s a very familiar mechanical model for this, that a great many people should be familiar with: Just think of the odometer in a car – specifically, the mechanical odometer found in all older cars. Or any similar mechanical counter.

What happens after it reaches 999…999 and you then add 1 more? It rolls over to become 000…000 again.

And what happens if you start with 000…000 and roll it backwards by 1 (that is, subtracting 1)? It becomes 999…999

And what happens if, say, you have 000…005 and you roll it backwards (that is, subtract) 8? You get 999…997, which can be interpreted as -3. This is exactly how “nine’s-complement” arithmetic would work.

And now suppose you have a binary counter instead. After it reaches 111…111 and you add one more, it rolls over to become 000…000 again. And if you start at, say, 000…101 (that is, 5[sub]10[/sub]) and roll it backwards (subtract) 1000 (that is, 8[sub]10[/sub]), you get 111…101, which can be interpreted as -3[sub]10[/sub]. This is none other than two’s-complement arithmetic.

23

The (mod 2^k) happens automatically when you truncate, but (mod 2^k - 1) would take extra logic. That’s closely related to your observation that two’s complement makes the “natural” implementation of 64-bit math on a 32-bit ALU (and conversion between types of different size in general) work correctly.

24

Nitpick: Tens-complement.

25

:smack: Right, of course.

Chalk that blunder up to one who never learned to count past 10[sub]2[/sub]

26

Another, equivalent way to look at it is that the expression “-x” is defined to mean, the number, which when added to x gives 0*. For natural numbers (i.e. 0,1,2,3…) and conventional addition, no two non-zero numbers produce zero when added together, so (other than zero) we have to invent “new” numbers to be the negatives of the natural numbers.

But with computer-represented integers, we don’t uses “conventional addition”, we use this special addition that rolls over. Basically it is “perform conventional addition, and then take the remainder after division by 2^N, where N is the number of bits in the representation”. Using this addition, we can still define “-x” as the number which when added to x gives 0, but we no longer have to invent new numbers to do this. If we are using 8 bits, say, -1 = 255 not because of any “take the not of all of the bits and add 1 rule”, but just because 1 + 255 = 0. And similarly 2 + 254 = 0, 3 + 253 = 0, &c.

Computer people get hung up on “this bit pattern represents a negative number, and this bit pattern doesn’t”, but abstract algebra people would simply say “in this situation, the additive inverse of 5 is 251”. Or even, “the additive inverse of the bit string 00000101 is 11111011 under the abstract operation we have chosen to represent addition”.

(* and “0” is defined as that thing when when added to x produces x, but we don’t need to worry about that right now).

27

In fact, under that way of looking at it, one could even say that -5 and 251 are just two different ways of representing the same number. As, for that matter, are 507 and 763 and…

Though I suppose that you still have to deal with comparators like “less than”.

28

There’s a partial analogy between twos-complement arithmetic and negative-temperature systems, particularly to certain spin-1/2 systems.

29

[from the tedious trivia table]
The System/360 opcodes AR (Add Register to Register) and ALR (Add Logical Register to Register) produce identical results. The difference lies in how the 2-bits of condition code are set: for the AR (resp. ALR) opcode the condition code is set usefully for addition of signed (resp. unsigned) numbers.

More often than not, the programmer doesn’t care how the condition code is set. Perfectionists may therefore prefer the ALR opcode which executes 1-cyle faster on some models of S360/370 — the condition code is easier to set in this case.

30

I prefer to think of it as: here are some bit patterns and some operations I can apply to them – deciding which integers they “represent” is a concern of the bourgeoisie. :slight_smile:

In order to do that we arbitrarily decide that bit patterns where the highest bit is set to 1 are “negative”. Then a < b iff a - b (= a + (-b)) is “negative”.

31

It seems like it would take fewer operations to do comparisons by going bit by bit, until you reach a bit where the numbers differ. Except that if they’re signed, for the first bit, 0 > 1 and for all subsequent bits, 1 > 0. That’d be at most one operation per bit of the numbers, and typically less. By comparison, looking at the sign bit of a - b would require one operation per bit to complement b, then at least one operation per bit to add a and -b (plus probably some carries).

32

I don’t know what actual processors do to do the comparison, but I agree that it is probably not explicit subtraction. Last I read about x86 assembly there was this CMP instruction that “sets the flags as if you had subtracted its two operands”, and then the subsequent jump instruction acts on the flags.

33

It’s become standard in all modern mainstream CPU architectures that every arithmetic operation (and many others) set four flags indicating things about the result: Z (zero); N (negative); O (overflow); and C (carry) (with some minor variations from one architecture to another).

It’s also understood that the bit-patterns in a computer word can be interpreted as signed integers (where the high-order bit, if 1, means the number is negative), or as unsigned integers. Thus, an 8-bit byte might have signed values of -128…+127, or unsigned values of 0…255.

Testing the values of these numbers is done indirectly: Not by looking at a number itself, but by testing the state of these flags after a prior operation (possibly the CMP operation described above).

Two numbers can be compared by any one of these comparisons: EQ, NE, LT, LE, GT, GE; also one can test for carry, no-carry, overflow, no-overflow, zero, or non-zero, negative or positive.

AND FURTHERMORE, there must be TWO complete sets of comparisons: For comparing signed integers, and for comparing unsigned integers.

At least one computer that I’ve programmed in assembly language (I forget if it was the x86 or the VAX or the Modcomp) had an extensive set of assembly-language op-codes for all of these tests – But it turned out, if you examined the actual hexadecimal op-codes, that a lot of these were synonyms for one another. It turns out that you don’t need a separate set of add or subtract instructions for signed or unsigned numbers in order to get the flags set for correct comparisons (as septimus described for the IBM 360). You can accomplish exactly the same thing simply by testing various combinations of the flag bits.

I don’t know the exact formulas anymore (and in fact I never did know a lot of them). But it turns out that some of the branch instructions test a single flag bit, while some others test some obscure boolean combination of the flag bits. This scheme is sufficient to provide the entire set of comparisons for signed as well as unsigned numbers. And the assembler provided handy mnemonic op-codes for a whole lot more tests than the machine language actually had, since various of those tests were actually synonyms.

34

Don’t forget about comparing a signed integer to an unsigned integer.

35

It is probably pretty close to explicit subtraction. Processors often use the same ALU for addition, subtraction, and comparison. For example, for the ARM processor, CMP is identical to SUBS, except that CMP ignores the ALU output (vs. SUBS, which writes it to the destination register).

For a further restatement:

  1. The easiest (i.e., least logic) way to add or subtract two k-bit inputs for a k-bit output is just to ignore the high bit adder’s carry out, truncating the result. If you do this, then you are performing arithmetic modulo 2^k.

  2. Two’s complement is the only representation where the signed and unsigned value of a bit field are equal (mod 2^k).

36

Its so that the inputs can be presented to a bunch of logic gates, with the output sent to a register (or RAM address,but same thing ) on the tick of a clock… and take the least clocks.

When I said register, it means AX,BX, DX … AND in the the flags…

That is, it might be A - B … and then you might have some intermediate result in R1 and then a second in R2 and a third in R3…

So on the first clock tick, R1 = function1 (A,B )
So on the second clock tick, R2 = function2 (A,B, R1 ) … well actually two of those three.

So on the third clock tick, R3 = function3 (A,B, R1,R2 ) … well actually two of those four…
etc

I say etc because this could be a 1024 bit subtraction…

So how many clock ticks does it take ?

The point is to do as much in parallel in one clock tick … eg for N bit cpu, it can do the N bit add/subtract, etc in one clock tick, mostly, but then do a quick test in the 2nd clock tick (which can be paralleled with other ops in 2000’s CPU … ) and then hopefully only take the third clock cycle to clean up sometimes.
But the OP’s question may be about how to do mathematics with a rudimentary ALU , to consider what sort of flags are needed to

37

Two’s complement is just so much better for a variety of reasons over one’s complement. Seymour Cray didn’t use twos complement in the old CDC machines simply because he hadn’t heard of it!

Note that you can to multiplication/division involving negative numbers represented in twos complement quite easily as well.

A simple addition only circuit is composed of a half-adder for the LSB and full-adders for the rest. Making the LSB adder a full adder and inputing a “carry” of 1 into it makes subtraction easier: Flip the subtractor and add the two numbers with a carry in of 1.

You could build a separate subtraction circuit, but you save transistors re-using the addition circuit.

(Note that there are faster circuits for addition such as carry save adders which take log n time rather than n, but the concept is the same as far as twos complement goes.)

You can do multiplication via division (actually inverse) easily and division using multiplication with a bit more work. These methods show that the running time of both operations are more or less the same. Got a wonder algorithm for multiplication that’s better than Fürer’s*? Great, you also have one for division.

The easy way (division -> inverse -> squaring -> multiplication):

Given int p, note that 1/(1/p - 1/(p+1)) - 1 = p[sup]2[/sup]. So you can square a number using inverse.

If you can square, you can multiply: (a+b)[sup]2[/sup] - (a-b)[sup]2[/sup] = 4ab. Just shift right 2.

(Things like addition/subtraction/mult or div by powers of 2 are considered cheaper operations and don’t matter much in the total.)

To go from multiplication to division, it’s a form of Newton-Raphson (with divisions only by powers of two) where you double the number of bits/iteration. Assuming that multiplying 2 n/2 bit numbers is at most a constant times multiplying 2 n bit numbers, the total work comes out to a constant times the last multiplication.

When time doesn’t matter but transistors due, really lame methods can be used. E.g., in early electronic calculators, shift and add methods were used for multiplication. Not fast, but it still got the answer before you lifted your finger off the “=” key.

  • Hello, Martin!
38

“Shift and add” methods would be similar to the methods taught in school to do multiplication by pencil and paper, yes?

39

That is an option of your browser/OS – it doesn’t have to be programmed in the webpage at all. (There is an HTML attribute to turn it on or off – it defaultes to on on textarea & textinput fields.)

Mine works that way now. (Chrome on Windows Vista Business.) But when I was using Firefox, it only defaulted to on for multi-line text fields – for a single line or input field, you had to change the Firefox parameter SpellcheckDefault.

40

Kind of, but simpler because you only have to deal with two cases: Is there a 1 or a 0 in the lowest-order position of the multiplier?

Simply, you move the multiplicand to a scratchpad, zero out the result, and loop through the multiplier like so: If the lowest-order bit of the multiplier is zero, left-shift the scratchpad by one. If the lowest-order bit of the multiplier is one, add the scratchpad to the result. Either way, right-shift the multiplier by one, and loop back. When the multiplier is zero, you’re done. It’s common to have a result twice the size of a common integer register, which leads to returning the result of a multiplication opcode in two registers, as in the MIPS design I mentioned above. This dovetails nicely with the division opcode, which typically computes both the integer division and the remainder (called mod in opcode-land) at the same time and returns one of them in one register and the other in the second register.

Anyway, it’s a complicated algorithm and there’s no way to do it in a single cycle, like you can with addition and shifting. (Yes, you can shift by arbitrary amounts in a single cycle; the hardware is called a barrel shifter, and it’s a multiplexer at heart.) These days, CPU designers can throw enough transistors at the problem to allow CPUs to re-schedule opcodes to some extent and paper over the inherent delay, but in the old days you had to eat the cycles the processor would be stuck in that opcode, or, as engineer_comp_geek said, hack up some ad hoc code which you think will beat the hardware. Various compilers have had peephole optimizations to replace multiplication and division baked into them; some, like shifting to replace multiplication or division by a power of two, are done by hand by some programmers, especially if they’re in low-level bitfield-hacking mode.