Author 
Message 
Adria #1 / 8

Whence 2scomplement
Can anybody present illuminate for me the mysteryshrouded etymolgoy of the term twoscomplement, referring to the most widespread computer method of storing negative vs. positive binary numbers in memory? Please? As well as satisfying my curiosity, the answer will probably reveal an important part of the history of computer evolution (or not). If you can, reply to me email address, please, as I may not check all the comp newsgroups. The address is:
advTHANKSance

Wed, 23 Aug 2000 03:00:00 GMT 


Douglas A. Gwy #2 / 8

Whence 2scomplement
Quote: >Can anybody present illuminate for me the mysteryshrouded etymolgoy of the >term twoscomplement, ...
Yes, but surely it would be better to read about this in an elementary textbook on computer arithmetic than to flood the Internet at great expense. Quote: >If you can, reply to me email address, please, as I may not check all the >comp newsgroups. ...
Well, then, you shouldn't be posting to all the comp newsgroups, should you?

Sun, 27 Aug 2000 03:00:00 GMT 


Mike Albau #3 / 8

Whence 2scomplement
Note I trimmed the followups to what appeared to be a more relevant subset.
: Can anybody present illuminate for me the mysteryshrouded etymolgoy of the : term twoscomplement, referring to the most widespread computer method of : storing negative vs. positive binary numbers in memory? Not so "mystery shrouded", if you were a "New Math Victim", _or_ stayed awake during a collegelevel "Foundations of Arithmetic" course. First you need to understand "complement arithmetic". The usual analogy is to the odometer on a car. If you have a fivedigit odometer, then adding "99999" is equivalent to subtracting "1". That's because "99999" is the "complement" of "1" for this system. Going back to your Latin class, you see that "complement" refers to "filling up" and is related to "completion". 99999+1 "completes" one trip around the entire set of numbers that the fivedigit odometer can represent. This sort of thing is wellknown to usedcar dealers like Mathilda's father (Roald Dahl, never mind) who know they can set _back_ the mileage on a car by using an electric drill to the run the odometer forward. You can easily get this sort of complement by subtracting '1' from 100000, but that rather begs the question, since we got here while trying to subtract. You can _also_ get it by taking the complement of each _digit_ ('00001' > '99998') and adding '1'. This is known in many math texts as "ten's complement", because the scheme works on radix (base) ten numbers, regardless of the number of digits so "onehundredthousands complement", while arguably more accurate in this particular case, is not helpful. Some folks are bothered by the "magic" implied by step: "and then add one". They like to treat each digit exactly the same. Unfortunately, this means they don't get the answers they expect. "Ah, but we can fix it". What we can do is take the "nines complement" ("00001" > "99998", I bet you can guess where the name comes from), do the addition and then, _if_ a "carry" falls off the end, feed it back into the leastsignificant digit. Example: "431" becomes "00043"+"99998" which is 00041 plus a carry out of the top. Add that carry in and it becomes 42, which is of course, the answer. Most computers today use binary, rather than decimal, arithmetic, but the two schemes of "radix complement" and "radix1" complement translate pretty naturally. "9's complement" becomes "one's complement" while "10's complement" becomes "two's complement". Each has its benefits and problems. Two's complement has the odd property that a given size of number can hold one more negative number than positive. For example, a 16bit number can hold any integer from 32768 to +32767. If you try to take the negative of 32768, you end up back at 32768. This mightily disturbs some folks. One's complement has the odd property that there are _two_ zeroes, "000...000" and "111...111". Not only that, but one of them is negative, which some _other_ people find even more disturbing than having an extra nonzero negative number. It gets even more annoying when you find that the usual "first cut" at building a one'scomplement adder is _far_ more likely to yield the negativezero than the positive one, and some one's complement machines don't count their own "0" as "zero" for purposes of some tests. The benefits of the two systems mainly lie in the lack of the problems of the other system. The one "killer" benefit of two's complement is that it is just slightly easier to do "multiprecision" arithmetic in. That term refers to the use of "small" arithmetic circuitry to do larger problems (such as when we add numbers a digit at a time for as many digits as we need). On the original computers with rather large words, this was no big deal, but as minicomputers and then microprocessors came out, pretty much _any_ reasonablesized numbers (over 2 digits) required multipleprecision arithmetic (e.g. using an 8bit adder twice to generate a 16bit result). Of course, rare is the programmer under 40 who even remembers the days when not all computers were binary, two'scomplement machines with wordsize an even power of two (4,8,16,32...) One place where one's complemnt turns up, to the bafflement of younger programmers, is in the checksums used in TCP/IP. There are some advantages in having a method which "dosn't care" whether the least significant byte of a 16bit number is stored before or after the most significant byte, but I suspect the fact that it is easier to "fake" one'scomplement on a two'scomplement machine than viceversa had something to do with it too. Even machines whose "native tongue" was "signmagnitude" (as we use on paper) tended to support some form of complemnet arithmetic too. : Please? As well as : satisfying my curiosity, the answer will probably reveal an important part : of the history of computer evolution (or not). There is not much truly useless knowledge, at least at this basic level. I'd claim that knowing this sort of thing will still be slightly useful long after the ability to debug a CONFIG.SYS has gone the way of knowing the names of the Lares and Penates or the exchange rate for Green Stamps. Mike

Sun, 27 Aug 2000 03:00:00 GMT 


David D. Smi #4 / 8

Whence 2scomplement
Quote:
> Can anybody present illuminate for me the mysteryshrouded etymolgoy of the > term twoscomplement, referring to the most widespread computer method of > storing negative vs. positive binary numbers in memory? Please? As well as > satisfying my curiosity, the answer will probably reveal an important part > of the history of computer evolution (or not).
The 2's Complement is formed by taking the Boolean Complement, or 1's Complement and adding 1. The 3's Complement is the 2's Complement + 1, etc. The 9's Complement, used to do subtraction in BCD, is the 1's Complement + 8. ***** 1's complement was used in some machines (e.g. CDC) because it is (was) faster to compute. You don't have to propagate the carries. ***** 2's complement is much more elegant. There is really no such thing as a "sign bit" in 2's Complement. The high order bit simply has a negative "place value". I.e. In 16 bit 2's Complement the place values are from lowest to highest: 2**0 (1) 2**1 (2) 2**2 (4) ... 2**14 (16384) (2**15) (32768) This makes addition "insensitive" (there is a mathematical term for this) to the sign of the arguments. Arithemetic overflow occurs when the Carry into the high order bit is not equivalent to the Carry out of the high order bit. ***** In the language Common LISP, integers have arbitrary precision (the may be huge in magnitude). There are also a number of functions for bit manipulation, such as testing the value of a bit, or extracting bits; while the language doesn't specify what REAL arithemetic is used for the implementation, it does require that the implementation return results from these bit accessing instructions AS IF the implementation were 2's complement. d

Fri, 15 Sep 2000 03:00:00 GMT 


Neil Ricke #5 / 8

Whence 2scomplement
Quote:
>> Can anybody present illuminate for me the mysteryshrouded etymolgoy of the >> term twoscomplement, referring to the most widespread computer method of >> storing negative vs. positive binary numbers in memory? Please? As well as >> satisfying my curiosity, the answer will probably reveal an important part >> of the history of computer evolution (or not). >The 2's Complement is formed by taking the Boolean Complement, or 1's >Complement and adding 1. >The 3's Complement is the 2's Complement + 1, etc. >The 9's Complement, used to do subtraction in BCD, is the 1's Complement + 8.
That is a little confused. The nines complement of a decimal number is formed by subtracting each digit from 9. The tenscomplement is formed by adding 1 to the nines complement. In general for a base N number representation, we can talk of the (N1)s complement, formed by subtracting each digit from N1, and the Ns complement formed by adding 1 to the (N1)s complement. Back in prehistoric times (or precomputer times), some mechanical calculators represented negative numbers as nines complement, some as tens complements, and some as sign magnitude. If you take the odometer on your car, and say it is set to 0. Then if you wind it backwards by 1 count, that would result in 999999, which is the nines complement way of representing 1. So nines complement is relatively natural way of representing negative decimal numbers, by analogy with winding a counter backwards. Similarly, twos complement is a relatively natural way of representing negative binary numbers. [Please don't actually wind the odometer backwards  it might be against the law.]

Fri, 15 Sep 2000 03:00:00 GMT 


Tom Wats #6 / 8

Whence 2scomplement
<<<deletia regareding 8's complement... among other things>>> Quote: > That is a little confused. The nines complement of a decimal number > is formed by subtracting each digit from 9. The tenscomplement is > formed by adding 1 to the nines complement. In general for a base N > number representation, we can talk of the (N1)s complement, formed > by subtracting each digit from N1, and the Ns complement formed by > adding 1 to the (N1)s complement. > Back in prehistoric times (or precomputer times), some mechanical > calculators represented negative numbers as nines complement, some as > tens complements, and some as sign magnitude. > If you take the odometer on your car, and say it is set to 0. Then > if you wind it backwards by 1 count, that would result in 999999, > which is the nines complement way of representing 1. So nines > complement is relatively natural way of representing negative decimal > numbers, by analogy with winding a counter backwards. Similarly, > twos complement is a relatively natural way of representing negative > binary numbers. [Please don't actually wind the odometer backwards  > it might be against the law.]
Actually the odometer uses 10's complement, not 9's complement. In a base 10 system, one gets 9's complement by subtracting the original number from an all 9's number of equal number of digits. This can be done on a digit by digit basis, as NO carry is involved. Thus 9's complement of '31' is '99'  '31', or '68'. This system leads to a numbering system that has two zeros ('00' and '99'). To get 10's complement, which has a continuous range, one needs to add back in the 1. Then the 10's complement to '31' is '69', and their sum is '100' (zeros in the digits, with a single carry out). This is similar to 1's and 2's complement for binary numbers. It has many of the same properties, like more negative numbers than positive (nonzero) numbers. In the two digit system, '50' is a full scale negative number (value of 50), and has no positive partner. Commonly BCD machines (like the IBM 1620) used signmagnitude arithmetic with a seperate sign "flag". While this was pleasing to the eye, arithmetic has strange consequences. With differing signs, it was possible to effect a 'recomplement' sequence that changed the (preliminary) result with the wrong sign from 10's complement back to the proper signmagnitude form. This made the operation last longer, and wasn't always welcome. Adding a negative number could take longer than subtracting a positive number (basically equivalent operations) if one needed the 'recomplement' operation. In some software floating point operations, the exponent was expressed as 'excess 50' notation, which is basically 10's complement with the sign reversed. This allowed a range of exponents (50 to +49) to be expressed without the use of a 'flag' bit and allowed the sign of the number number to use the flag. Today, IBM floating point numbers do a similar goodie in their excess 64 exponents (but in binary). Some of this belongs in folklore groups, given the historical reference. 

Fri, 15 Sep 2000 03:00:00 GMT 


David D. Smi #7 / 8

Whence 2scomplement
Quote:
> >> Can anybody present illuminate for me the mysteryshrouded etymolgoy of the > >> term twoscomplement, referring to the most widespread computer method of > >> storing negative vs. positive binary numbers in memory? Please? As well as > >> satisfying my curiosity, the answer will probably reveal an important part > >> of the history of computer evolution (or not). > >The 2's Complement is formed by taking the Boolean Complement, or 1's > >Complement and adding 1. > >The 3's Complement is the 2's Complement + 1, etc. > >The 9's Complement, used to do subtraction in BCD, is the 1's Complement + 8. > That is a little confused. The nines complement of a decimal number
Actually I said Binary Coded Decimal number, but it is confused, since I can't remember how to do it. Quote: > ... and the Ns complement formed by > adding 1 to the (N1)s complement.
... or 2 to the (N2)s complement, etc. I think this is what I said. i.e. adding 8 to the (98)s complement. d

Fri, 15 Sep 2000 03:00:00 GMT 


Lawrence Kir #8 / 8

Whence 2scomplement
Quote:
>> >> Can anybody present illuminate for me the mysteryshrouded etymolgoy of the>> >> term twoscomplement, referring to the most widespread computer method of >> >> storing negative vs. positive binary numbers in memory? Please? As >well as >> >> satisfying my curiosity, the answer will probably reveal an important part >> >> of the history of computer evolution (or not). >> >The 2's Complement is formed by taking the Boolean Complement, or 1's >> >Complement and adding 1. >> >The 3's Complement is the 2's Complement + 1, etc. >> >The 9's Complement, used to do subtraction in BCD, is the 1's Complement + 8.>> >> That is a little confused. The nines complement of a decimal number >Actually I said Binary Coded Decimal number, but it is confused, since I >can't remember how to do it.
As far as complements are concerned you should consider it as a decimal system. Quote: >> ... and the Ns complement formed by >> adding 1 to the (N1)s complement.
That's only valid for base N numbers. Quote: >... or 2 to the (N2)s complement, etc. I think this is what I said.
No, that is incorrect. For base N it is only meaningful to talk about N1's complement and N's complement. N2's complement is meaningless. In binary you can talk about 1's complement and 2's complement. In base 10 you can talk about 9's complement and 10's complement. Talking about 2's complement in base 10 is meaningless nonsense. Quote: >i.e. adding 8 to the (98)s complement.
Except that this doesn't work.  


Sun, 17 Sep 2000 03:00:00 GMT 


